Euler's Theorem

In today's blog I continue the proof for the Principle of Quadratic Reciprocity. If you are not familiar with the concepts of quadratic reciprocity, quadratic residues, or the Legendre Symbol start here.

If you would like to start this proof at the beginning, start here.

If you are not familiar with the Legendre Symbol, you should review here.

Today's proof is taken from Gareth A. Jones and J. Mary Jones' Elementary Number Theory.

Definition 1: Reduced Set of Residues mod n

R is a reduced set of residues mod n if it contains each of the congruence classes in U_n [See here for a definition of U_n]

Examples:

Reduced set of residues mod (8) = { 1, 3, 5, 7 }

(1)(1) ≡ 1 (mod 8)

(3)(3) ≡ 1 (mod 8)

(5)(5) ≡ 1 (mod 8)

(7)(7) ≡ 1 (mod 8)

Lemma 1: if p is an odd prime, φ(p) = p-1

This is clear since all items 1..p-1 are relatively prime to p. [See here for definition of φ(p)]

QED

Lemma 2: There are exactly φ(n); elements in the reduced set of residues mod n.

(1) φ(n) ≤ the number of elements in the reduced set of residues mod n.

(a) φ(n) counts the number of integers a where gcd(a,n)=1.

(b) By Bezout's Identity, there exists u,v au + nv = 1

(c) But then au-1 = -nv which means that au ≡ 1 (mod n)

(d) So each integer a counted by φ(n) is a unit. [See here for definition of modular units]

(2) But, also, the total number of elements in the reduced set of resides ≤ φ(n)

In other words, if gcd(a,n) is greater than 1, then a is not a unit since:

(a) Let us suppose that gcd(a,n)=d which is greater than 1 and n divides ab-1. [n divides ab-1 since we ab ≡ 1 (mod n) ]

(b) By definition of gcd, there exists an integer a' such that a = da'

(c) Since n divides ab-1, there exists b' such that ab-1 = nb'

(d) Now, since d divides ab and d divides nb', it must divide 1 which is impossible.

(e) So we have a contradiction.

(3) So if the reduced set is ≤ φ(n) and φ(n) ≤ the reduced set, it follows that the reduced set = φ(n).

QED

Lemma 3: if R is a reduced set of residues mod (n) and gcd(a,n)=1, then the set aR is also a reduced set of residues mod (n).

(1) Since R is a reduced set, we know that each of its elements are units. [See Definition of Reduced Set above]

(2) Since gcd(a,n)=1 and since r ∈ R → gcd(r,n)=1 [See Lemma 2 above], we know that gcd(ar,n)=1.

(3) So, each of the aR are also units [See the reasoning in Lemma 2 above to see how gcd(ar,n)=1 proves that it is a unit]

(4) Let r,r' be elements of the reduced set R.

(5) ar ≡ ar' (mod n) → r ≡ r' (mod n) [See here for review of modular arithmetic]

(6) Likewise r not ≡ r' → ar is not congruent to ar' since:

(a) Assume that r not ≡ r' (mod n) but ar ≡ ar' (mod n)

(b) From the reasoning in #5, ar ≡ ar' (mod n) tells us that r ≡ r' which is a contradiction so we reject our assumption (a).

(7) If all the elements aR are units and r not ≡ r' → ar not ≡ ar' tells us that there is a one-to-one correspondence between R and aR.

(8) And this tells us that aR is also a reduced set of residues modulo n.

QED

Theorem: Euler's Theorem

If gcd(a,n)=1, then a^φ(n) ≡ 1 (mod n)

(1) We know that φ(n) is between 1 and n-1. [See here for definition of φ(n)]

(2) We can set R = the set { 1, 2, ... φ(n) }

(3) Since gcd(a,n)=1, we know that (see Lemma 3 above):
aR has a one-to-one correspondence with R in terms of congruences.

(4) This gives us that:
a*2a*..*φ(n)a ≡ 1*2*...*φ(n) (mod n)

(5) But then we get:
a^φ(n)*(1*2*...*φ(n)) ≡ 1*2*...*φ(n) (mod n)

(6) Dividing both sides by 1*2*...*φ(n) gives us (see here for a review of modular arithmetic)

a^φ(n) ≡ 1 (mod n)

QED