Exercise 2.11. Show that for any positive integer n, and any integer k,

the residue classes [k + a]n , for a = 0, . . . , n ’ 1, are distinct and therefore

include all residue classes modulo n.

Exercise 2.12. Verify the following statements for Zn :

(a) There is only one element of Zn that acts as an additive identity; that

is, if ± ∈ Zn satis¬es ± + β = β for all β ∈ Zn , then ± = [0]n .

(b) Additive inverses in Zn are unique; that is, for all ± ∈ Zn , if ± + β =

[0]n , then β = ’±.

(c) If ± ∈ Z— and γ, δ ∈ Zn , then there exists a unique β ∈ Zn such that

n

±β + γ = δ.

Exercise 2.13. Verify the usual “rules of exponent arithmetic” for Zn . That

is, show that for ± ∈ Zn , and non-negative integers k1 , k2 , we have

(±k1 )k2 = ±k1 k2 and ±k1 ±k2 = ±k1 +k2 .

Moreover, show that if ± ∈ Z— , then these identities hold for all integers

n

k1 , k2 .

2.4 Euler™s phi function

Euler™s phi function φ(n) is de¬ned for positive integer n as the number

of elements of Z— . Equivalently, φ(n) is equal to the number of integers

n

between 0 and n ’ 1 that are relatively prime to n. For example, φ(1) = 1,

φ(2) = 1, φ(3) = 2, and φ(4) = 2.

A fact that is sometimes useful is the following:

Theorem 2.11. For any positive integer n, we have

φ(d) = n,

d|n

where the sum is over all positive divisors d of n.

Proof. Consider the list of n rational numbers 0/n, 1/n, . . . , (n ’ 1)/n. For

any divisor d of n and for any integer a with 0 ¤ a < d and gcd(a, d) = 1, the

fraction a/d appears in the list exactly once, and moreover, every number in

the sequence, when expressed as a fraction in lowest terms, is of this form.

2

2.5 Fermat™s little theorem 25

Using the Chinese remainder theorem, it is easy to get a nice formula

for φ(n) in terms for the prime factorization of n, as we establish in the

following sequence of theorems.

Theorem 2.12. For positive integers n, m with gcd(n, m) = 1, we have

φ(nm) = φ(n)φ(m).

Proof. Consider the map

Znm ’ Zn — Zm

ρ:

[a]nm ’ ([a]n , [a]m ).

First, note that the de¬nition of ρ is unambiguous, since a ≡ a (mod nm)

implies a ≡ a (mod n) and a ≡ a (mod m). Second, according to the Chi-

nese remainder theorem, the map ρ is one-to-one and onto. Moreover, it is

easy to see that gcd(a, nm) = 1 if and only if gcd(a, n) = 1 and gcd(a, m) = 1

(verify). Therefore, the map ρ carries Z— injectively onto Z— — Z— . In par-

nm n m

— | = |Z— — Z— |. 2

ticular, |Znm n m

Theorem 2.13. For a prime p and a positive integer e, we have φ(pe ) =

pe’1 (p ’ 1).

Proof. The multiples of p among 0, 1, . . . , pe ’ 1 are

0 · p, 1 · p, . . . , (pe’1 ’ 1) · p,

of which there are precisely pe’1 . Thus, φ(pe ) = pe ’ pe’1 = pe’1 (p ’ 1). 2

As an immediate consequence of the above two theorems, we have:

Theorem 2.14. If n = pe1 · · · per is the factorization of n into primes, then

r

1

r r

pi i ’1 (pi

e

’ 1) = n (1 ’ 1/pi ).

φ(n) =

i=1 i=1

Exercise 2.14. Show that φ(nm) = gcd(n, m) · φ(lcm(n, m)).

2.5 Fermat™s little theorem

Let n be a positive integer, and let a ∈ Z with gcd(a, n) = 1. Consider the

sequence of powers of ± := [a]n ∈ Z— :

n

[1]n = ±0 , ±1 , ±2 , . . . .

26 Congruences

Since each such power is an element of Z— , and since Z— is a ¬nite set, this

n n

sequence of powers must start to repeat at some point; that is, there must

be a positive integer k such that ±k = ±i for some i = 0, . . . , k ’ 1. Let

us assume that k is chosen to be the smallest such positive integer. We

claim that i = 0, or equivalently, ±k = [1]n . To see this, suppose by way of

contradiction that ±k = ±i , for some i = 1, . . . , k ’ 1. Then we can cancel

± from both sides of the equation ±k = ±i , obtaining ±k’1 = ±i’1 , and this

contradicts the minimality of k.

From the above discussion, we see that the ¬rst k powers of ±, that is,

[1]n = ±0 , ±1 , . . . , ±k’1 , are distinct, and subsequent powers of ± simply

repeat this pattern. More generally, we may consider both positive and

negative powers of ± ”it is easy to see (verify) that for all i, j ∈ Z, we have

±i = ±j if and only if i ≡ j (mod k). In particular, we see that for any

integer i, we have ±i = [1]n if and only if k divides i.

This value k is called the multiplicative order of ± or the multiplica-

tive order of a modulo n. It can be characterized as the smallest positive

integer k such that

ak ≡ 1 (mod n).

Example 2.6. Let n = 7. For each value a = 1, . . . , 6, we can compute

successive powers of a modulo n to ¬nd its multiplicative order modulo n.

i 1 2 3 4 5 6

1i mod 7 1 1 1 1 1 1

2i mod 7 2 4 1 2 4 1

3i mod 7 3 2 6 4 5 1

4i mod 7 4 2 1 4 2 1

5i mod 7 5 4 6 2 3 1

6i mod 7 6 1 6 1 6 1

So we conclude that modulo 7: 1 has order 1; 6 has order 2; 2 and 4 have

order 3; and 3 and 5 have order 6. 2

Theorem 2.15 (Euler™s Theorem). For any positive integer n, and any

integer a relatively prime to n, we have aφ(n) ≡ 1 (mod n). In particular,

the multiplicative order of a modulo n divides φ(n).

Proof. Let ± := [a]n ∈ Z— . Consider the map f : Z— ’ Z— that sends β ∈ Z—

n n n n

to ±β. Observe that f is injective, since if ±β = ±β , we may cancel ± from

both sides of this equation, obtaining β = β . Since f maps Z— injectively

n

— is a ¬nite set, it must be the case that f is surjective

into itself, and since Zn

2.5 Fermat™s little theorem 27

as well. Thus, as β ranges over the set Z— , so does ±β, and we have

n

(±β) = ±φ(n)

β= β. (2.6)

β∈Z— β∈Z— β∈Z—

n n n

β ∈ Z— from the left- and right-hand

Canceling the common factor β∈Z— n