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) }.

 
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 Z_n, 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 Z_n, 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 Z_n, or units of Z_n.

 
Proposition 1.4.5. Let n be a positive integer.

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

(b) A nonzero element of Z_n 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) Z_n has no divisors of zero, except [0]_n.

(3) Every nonzero element of Z_n 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 = p₁^m₁ p₂^m₂ · · · p_n^m_n , then

(n) = n(1-1/p₁)(1-1/p₂) · · · (1-1/p_k).

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

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

 
The following theorem shows that raising any congruence class in Z_n^× 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 ⁽ⁿ⁾ 1 (mod n).

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

§ 1.4 Integers modulo n: Solved problems

ax b (mod n)

[a]_n [x]_n = [b]_n .

ax b (mod n)

[a]_n [x]_n = [b]_n

It is well worth your time to learn about the sets Z_n and Z_n^×. 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 Z_n. If gcd (a,n) = 1, then the smallest positive integer k such that [a]^k = [1] is called the multiplicative order of [a] in Z_n^×. The set Z_n^× is said to be cyclic if it contains an element of multiplicative order (n). This is equivalent to saying that Z_n^× is cyclic if it has an element [a] such that each element of Z_n^× is equal to some power of [a]. Finally, the congruence class [a] is said to be idempotent if [a]² = [a], and nilpotent if [a]^k = [0] for some k.

30. Find the multiplicative inverse of each nonzero element of Z₇.     Solution

31. Find the multiplicative inverse of each nonzero element of Z₁₃.     Solution

32. Find [91]₅₀₁^-1, if possible (in Z₅₀₁^×).     Solution

33. Find [3379]₄₀₆₁^-1, if possible (in Z₄₀₆₁^×).     Solution

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

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

36. Show that Z₁₇^× is cyclic.     Solution

37. Show that Z₃₅^× is not cyclic but that each element has the form
[8]₃₅ⁱ [-4]₃₅^j, for some positive integers i,j.     Solution

38. Solve the equation [x]₁₁² + [x]₁₁ - [6]₁₁ = [0]₁₁.     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 a^k 1 (mod n), then k | (n).     Solution

40. Prove that [a]_n is a nilpotent element of Z_n 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