Excerpted from Beachy/Blair, Abstract Algebra, 2nd Ed. © 1996

Forward to §2.1 | Back to §1.3 | Up | Table of Contents | About this document


§ 1.4 Integers Modulo n

 
Definition 1.4.1. Let a and n > 0 be integers. The set of all integers which have the same remainder as a when divided by n is called the congruence class of a modulo n, and is denoted by [a]n, where

[a]n = { x in Z | x a (mod n) }.

The collection of all congruence classes modulo n is called the set of integers modulo n, denoted by Zn.

 
Proposition 1.4.2. Let n be a positive integer, and let a,b be any integers. Then the addition and multiplication of congruence classes given below are well-defined :

[a]n + [b]n = [a+b]n     and     [a]n[b]n = [ab]n.

 
Definition 1.4.3. If [a]n belongs to Zn, and [a]n[b]n = [0]n for some nonzero congruence class [b]n, then [a]n is called a divisor of zero, modulo n.

 
Definition 1.4.4. If [a]n belongs to Zn, and [a]n[b]n = [1]n, for some congruence class [b]n, then [b]n is called a multiplicative inverse of [a]n and is denoted by [a]n-1.
    In this case, we say that [a]n and [b]n are invertible elements of Zn, or units of Zn.

 
Proposition 1.4.5. Let n be a positive integer.

(a) The congruence class [a]n has a multiplicative inverse in Zn if and only if (a,n)=1.

(b) A nonzero element of Zn either has a multiplicative inverse or is a divisor of zero.

 
Corollary 1.4.6. The following conditions on the modulus n > 0 are equivalent :

(1) The number n is prime.

(2) Zn has no divisors of zero, except [0]n.

(3) Every nonzero element of Zn has a multiplicative inverse.

 
Definition 1.4.7. Let n be a positive integer. The number of positive integers less than or equal to n which are relatively prime to n will be denoted by (n). This function is called Euler's phi-function, or the totient function.

 
Proposition 1.4.8. If the prime factorization of n is n = p1m1 p2m2 · · · pnmn , then

(n) = n(1-1/p1)(1-1/p2) · · · (1-1/pk).

 
Definition 1.4.9. The set of units of Zn, the congruence classes [a]n, such that (a,n)=1, will be denoted by
Zn×.

 
Proposition 1.4.10. The set Zn× of units of Zn is closed under multiplication.

 
The following theorem shows that raising any congruence class in Zn× to the power (n) yields the congruence class of 1. It is possible to give a purely number theoretic proof at this point, but in Example 3.2.12 there is a more elegant proof using elementary group theory.

 
Theorem 1.4.11. [Euler] If (a,n) = 1, then a (n) 1 (mod n).

 
Corollary 1.4.12. [Fermat] If p is prime, then ap a(mod p), for any integer a.



§ 1.4 Integers modulo n: Solved problems

The ideas in this section allow us to work with equations instead of congruences, provided we think in terms of equivalence classes. (So just when you got used to congruences, we're going back to equations.) To be more precise, any linear congruence of the form

ax b (mod n)

can be viewed as an equation in Zn, written

[a]n [x]n = [b]n .

This gives you one more way to view problems involving congruences. Sometimes it helps to have various ways to think about a problem, and it is worthwhile to learn all of the approaches, so that you can easily shift back and forth between them, and choose whichever approach is the most convenient. For example, trying to divide by a in the congruence

ax b (mod n)

can get you into trouble unless gcd (a,n) = 1. Instead of thinking in terms of division, it is probably better to think of multiplying both sides of the equation

[a]n [x]n = [b]n

by the multiplicative inverse of [a]n, provided [a]n-1 exists.

It is well worth your time to learn about the sets Zn and Zn×. They will provide an important source of examples in Chapter 3, when we begin studying groups.

The exercises for Section1.4 of the text contain several definitions for elements of Zn. If gcd (a,n) = 1, then the smallest positive integer k such that [a]k = [1] is called the multiplicative order of [a] in Zn×. The set Zn× is said to be cyclic if it contains an element of multiplicative order (n). This is equivalent to saying that Zn× is cyclic if it has an element [a] such that each element of Zn× is equal to some power of [a]. Finally, the congruence class [a] is said to be idempotent if [a]2 = [a], and nilpotent if [a]k = [0] for some k.


30. Find the multiplicative inverse of each nonzero element of Z7.     Solution

31. Find the multiplicative inverse of each nonzero element of Z13.     Solution

32. Find [91]501-1, if possible (in Z501×).     Solution

33. Find [3379]4061-1, if possible (in Z4061×).     Solution

34. In Z20 : find all units (list the multiplicative inverse of each); find all idempotent elements; find all nilpotent elements.     Solution

35. In Z24 : find all units (list the multiplicative inverse of each); find all idempotent elements; find all nilpotent elements.     Solution

36. Show that Z17× is cyclic.     Solution

37. Show that Z35× is not cyclic but that each element has the form
[8]35i [-4]35j, for some positive integers i,j.     Solution

38. Solve the equation [x]112 + [x]11 - [6]11 = [0]11.     Solution

39. Let n be a positive integer, and let a in Z with gcd (a,n) = 1. Prove that if k is the smallest positive integer for which ak 1 (mod n), then k | (n).     Solution

40. Prove that [a]n is a nilpotent element of Zn if and only if each prime divisor of n is a divisor of a.     Solution


Solutions to the problems | Forward to §2.1 | Back to §1.3 | Up | Table of Contents