Fermat's Last Theorem

Wednesday, February 22, 2006

Euler's Identity

One of the simplest and most elegant equations is Euler's Identity:
e^πi + 1 = 0.

It states that Euler's number e (which is equal to roughly 2.718...) to the power of i*π (taken at roughly 3.14...) is equal to -1. This equation is used to derive cyclotomic integers which are used in Kummer's proof for Fermat's Last Theorem for regular primes.

To be fair, for many people, xⁱ does not have a clear value. What does it mean to put an exponent to an imaginary power? In mathematics, it is ok if the details are not intuitive as long as they are logically consistent. The Maclaurin Series, for example, can be used to define exponents to a complex power (see here). Newton did something similar when he generalized the Binomial Theorem to include complex powers (see here for details)

Theorem: Euler's Identity is the equation: e^πi = -1

This equation derives directly from Euler's Formula:
e^ix = cos x - isin x [See here for proof]

We get:
e^πi = cos(π) + isin(π) = -1 + i(0) = -1. [Review of e (see here), sin and cos (see here), i (see here), and π (see here)]

QED

Corollary: e^πi + 1 = 0

This directly follows from above.

QED

Friday, February 17, 2006

Cyclotomic Integers

In Ernst Kummer's groundbreaking partial proof on Fermat's Last Theorem, he used cyclotomic integers.

Cyclotomic integers are based the equation xⁿ = 1 (they get their name from this equation which is known as the cyclotomic equation). The solutions to this equation are known as the Roots of Unity. The solutions to n=1 and n=2 are well known (1, -1). What is less well known is that as n increases, there are complex solutions that also solve this equation (these are also known as DeMoivre Numbers).

For some, it may seem strange that complex numbers emerge out of x³ = 1. The insight to why this is so comes from considering Euler's Identity:

e^iπ=-1

In my next blog, I will go into the details behind this equation. Still, using this equation, we can see that three solutions to x³ = 1 are:
1, e^(2iπ)/3, e^(4iπ)/3

Since (e^(2iπ)/3)³ = e^2iπ = (-1)² = 1.

The solution then for any value of n is e^(2iπ)/n and this solution is by convention represented by the Greek symbol zeta ζ. The set of integers then is Z[ζ] where each integer can be constructed from the rational integers a,b using a + bζ. This construction follows the same pattern as what Euler did for Z[√-3] (see here) and what Gauss did for Z[i] (see here).

For any value n, there are n different roots of unity which can be generated by e^(2iπk)/n where k is any integer 0, 1, 2, ..., up to n-1. For this reason, one speaks about the value ζ (equal to e^2iπ/n) as a primitive root of unity.

One might reasonably ask if all cyclotomic integers created in this way are characterized by unique factorization. In using quadratic integers, Euler made a mistake by assuming that Z[√-3] has unique factorization which it does not. Gabriel Lame assumed that all cyclotomic integers where characterized by unique factorization when he presented his proof of Fermat's Last Theorem. This assumption turns out to be the major flaw in Lame's proof.

This then becomes the major question which Kummer sought to resolve. Under what circumstances are cyclotomic integers characterized by unique factorization? The answer to this question led Kummer to his important partial proof of Fermat's Last Theorem. He showed that Fermat's Last Theorem holds for a certain set or primes which he called "regular primes." I talk more about the properties of cyclotomic integers here.

References

Roots of Unity, Wikipedia
Cyclotomic Equation, MathWorld

Wednesday, February 15, 2006

Quadratic Reciprocity: Last Step

We see that:
(a) R is the set of all points PxQ = [(p-1)/2][(q-1)/2] = (p-1)(q-1)/4

(b) μ + ν = R ∩ S

(c) A = the area of PxQ that falls above S

(d) B = the area of PxQ that falls below S

(2) We can further define α, β such that:

α = the number of points ∈ A
β = the number of points ∈ B

(3) From this, we see that the number of points R ∩ S is:
(p-1)(q-1)/4 - (α + β)

(4) Now we can show that α = β or in other words that there is a one-to-one mapping between elements in α with elements in β by the following:

(a) We can do this using the following rotation p(x,y):

p(x,y) = (x',y') = ( [p+1]/2 - x, [q+1]/2 - y )

(b) So, for example, the corners of R before the rotation are: (1,[q-1]/2), ([p-1]/2,[q-1]/2), (1,1), and ([p-1]/2, 1).

(c) After the rotation, the corners of R' are: ([p-1]/2,1), (1,1), ([p-1]/2,[q-1]/2), and (1,[q-1]/2).

(d) So, we see that R' has the same corners as R.

(e) By Lemma 2, we see that there is a one-to-one correspondence between A and B.

(5) So, this means that α + β ≡ 2*α ≡ 0 (mod 2).

(6) But this means that the α + β does not change the result since:
(-1)^{μ + ν} = (-1)^{μ + ν}*(-1)^2α

So:
(-1)^{μ + ν} = (-1)^{μ + ν + 2*α} = (-1)^(p-1)(q-1)/4

QED

Monday, February 13, 2006

Quadratic Reciprocity: Expanding on Gauss's Lemma

(b) P = set of integer = {1, 2, ... (p-1)/2 }

(c) Q = set of integers = {1, 2, ... (q-1)/2 }

(d) μ + ν = the number of pairs (x,y) ∈ P x Q such that -p/2 is less than (qx-py) which is less than q/2.

Proof:

(1) We can start out with the observation that:

where μ is the number of pairs (x,y) ∈ PxQ such that (-p/2) is less than qx-py which is less than 0 since:

(a) From Gauss's Lemma (see here), we have:

where μ is the number if elements in qP ∩ N where N = of integers -P, that is, {-1, -2, ... -(p-1)/2}

(b) qP ∩ N → qx ≡ n (mod p) where n ∈ N, x ∈ P. [See Gauss's lemma for details if needed, see here for review of modular arithmetic]

(c) There exists y such that (-p/2) is less than qx - py which is less than 0. [By Lemma 1 above]

(d) We know that y is greater than 0 [See Lemma 2 above]

(e) Also, y is less than (q+1)/2. [See Lemma 3 above]

(f) So, y ≤ (q-1)/2 [ since there is no integer greater than (q-1)/2 and less than (q+1)/2 ]

(g) So, y ∈ Q since (d) gives us y ≥ 1 and (f) gives us y ≤ (q-1)/2.

(h) Since x ∈ P from assumption, we have (x,y) ∈ PxQ [see here if you need a review of PxQ notation]

(2) We can use the same reasoning as (#1) to get a value ν such that:

where ν is the number of pairs (y,x) ∈ QxP such that (-q/2) is less than py-qx which is less than 0 .

(3) Combining (1) and (2) gives us:

where if x,y are taken from (#1), we have:

(x,y) ∈ PxQ such that (-p/2) is less than qx-py which is less than 0

If x,y are taken from (#2), then we have:

(y,x) ∈ QxP such that (-q/2) is less than py-qx which is less than 0

(4) Combining both possibilities, we have:

(x,y) ∈ PxQ, (-p/2) is less than qx-py which is less than (q/2).

QED

Sunday, February 12, 2006

Euler's Criterion

Proof:

This is true by the the definition of the Legendre Symbol (see here)

QED

Lemma 2: if p is an odd prime and g is a primitive root for U_p, then gⁱ ∈ Q_p if and only if i is even.

Proof:

(1) if i is even, then g^i/2 ∈ U_p [See here for definition of primitive root]

(2) But g^i/2 ∈ U_p, then gⁱ ≡ (g^i/2)² (mod p) and therefore gⁱ ∈ Q_p [See above for definition of Q_p]

(3) if gⁱ ∈ Q_p, then there exists j such that gⁱ ≡ (g^j)² (mod p) [Based on definition of Q_p]

(4) so, i ≡ 2j (mod φ(p)) since:

(a) φ(p) is the order of g. [See detail here]

(b) There exists q,r such that [from the Division Algorithm, see here]:
i = q(φ(p)) + r
0 ≤ r which is less than φ(p)

(c) And, i ≡ r (mod φ(p))

(d) So, gⁱ ≡ g^q(φ(p))+r ≡ (g^φ(p))^q*g^r ≡ (1)^q*g^r ≡ g^r (mod p)

(e) There exists, q', r' such that:
2j = q'(φ(p)) + r'
0 ≤ r' which is less than φ(p)

2j ≡ r' (mod φ(p))

(f) Now it follows that r = r' since:
g^2j ≡ (1)^q'*g^r' ≡ g^r' ≡ g^r (mod p)

(g) Putting this all together, gives us:
2j ≡ i ≡ r (mod p)

(5) Now φ(p) is even. [since φ(p) = p-1 and p is an odd prime -- see here for details.]

(6) So i is even since:

(a) There exists a such that φ(p) = 2a [Since φ(p) is even]

(b) There exists b such that i - 2j = (2a)b [By definition of modular arithmetic, see here]

(c) So, 2 must divide i.

QED

Lemma 3: If p is an odd prime and g is a primitive root mod p, then:

Proof:

(1) Both values are either equal to 1 or -1. [See here for definition of Legendre Symbol]

(2) So, I will prove that:

In other words, it is 1 only if i is even.

(3) In order for it to be 1, gⁱ must be an element of Q_p. [See Lemma 1 above]

(4) From Lemma 2, we know that gⁱ ∈ Q_p if and only if i is even.

QED

Theorem 1: Euler's Criterion: if p is an odd prime and a is any integer then:

Proof:

(1) We can assume that p does not divide a since if it did:

and

which proves the conclusion.

(2) Now, if p doesn't divide a, then gcd(p,a)=1 since p is a prime.

(3) Also, there exists a' such that a ≡ a' (mod p) and a' is a unit mod p since:

(a) gcd(p,a)=1 → there exists u,v such that au + pv = 1 (By Bezout's Identity, see here for proof)

(b) So, au - 1 = pv → au ≡ 1 (mod p)

(c) But then a is a unit mod p (see here for definition of a unit mod p)

(4) The set of units mod p is cyclic (see here for proof)

(5) Then, there exists an element g such that g is the primitive root for the set of units mod p. (see here for definition of cyclic)

(6) So, there exists i such that a ≡ gⁱ (mod p) (see here for definition of primitive root)

(7) Let h ≡ g^(p-1)/2 (mod p)

(8) h² ≡ g^p-1 (mod p) [See here for a review of exponents if needed]

(9) φ(p) = p-1 [See here for details.]

(10) g^p-1 ≡ g^φ(p) ≡ 1 (mod p) [See Euler's Theorem]

(11) So p divides g^p-1-1 → p divides h² - 1 → p divides (h-1)(h+1)

(12) So, h ≡ 1 or h ≡ -1 (mod p)

(13) But h cannot be ≡ 1 (mod p) since (p-1)/2 is less than p-1 and p-1 is the order [See here for the definition of order]

(14) So h ≡ -1 (mod p)

(15) From (#6), we have: a^(p-1)/2 ≡ (gⁱ)^(p-1)/2 ≡ (g^(p-1)/2)ⁱ ≡ hⁱ ≡ (-1)ⁱ (mod p)

(16) Now from Lemma 3 above:

(17) Since a ≡ gⁱ (mod p), we also have:

(18) Finally, since a^(p-1)/2 ≡ (-1)ⁱ (mod p) from#15, we have:

QED

Saturday, February 11, 2006

Euler's Theorem

Wednesday, February 08, 2006

Units for Modular Arithmetic

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. U_p: Set of units modulo p.

x ∈ U_p if and only if there exists y such that xy ≡ 1 (mod p).

As should be clear, in all the cases above, both x,y ∈ U_p

Definition 2. Primitive Root Modulo p

x is a primitive root for a set S if for any y ∈ S, y ≡ xⁱ (mod p) where i ≥ 1.

Example: 2 is a primitive root for U₃

By Definition 1, U₃ = { 1, 2 } since (1)(1) ≡ 1 (mod p) and (2)(2) ≡ 1 (mod p).

But then:
1 ≡ 2² (mod p)
2 ≡ 2¹ (mod p)

Definition 3: Cyclic set

A set is cyclic if there exists at least one element that is a primitive root.

Example: U₃ is cyclic since it has a primitive root of 2.

Definition 4: Order of an element of U_p

The order of x ∈ U_p is the least element i such that xⁱ ≡ 1 (mod p).

Example:
1 has an order of 1 in U₃ [See Definition 2 example for details]
2 has an order of 2 in U₃
Definition 5: Euler's Function: φ(n)

φ(n) = the number of elements a such that gcd(a,n)=1

Example:

φ(2) = 1 since gcd(1,2)=1
φ(3) = 2 since gcd(1,3)=1 and gcd(2,3)=1
φ(4) = 2 since gcd(1,4)=1 and gcd(3,4)=1

etc.

Lemma 1: If p is an odd prime, the order of each element of U_p divides p-1.

(1) Let a be an element of U_p

(2) a^p-1 ≡ 1 (mod p) [By Fermat's Little Theorem, see here]

(3) Now we can assume that the order is less than p-1.

If order(a) = p-1, then we are done since p-1 divides p-1.

It cannot be greater than p-1 since the order is the smallest number greater than 0 and p-1 is greater than 0.

(4) Let d be the order for this element a.

(5) Assume that d does not divide p-1.

(6) Using the Division Algorithm (see here), we know that there exists q,r such that:
p-1 = qd + r
r is greater than 0 (by step #5)
r is less than d (by the Division Algorithm)

(7) So, a^p-1 ≡ a^{qd + r} ≡ a^qd * a^r [See here if you need a review of exponents]

(8) Now, since a^qd ≡ (a^d)^q, we have:
a^qd ≡ 1 (mod p)

(9) Combining (#8) with (#7) gives us:
a^p-1 ≡ (1)*a^r ≡ a^r

(10) But a^p-1 ≡ 1 (mod p) so a^r ≡ 1 (mod p)

(11) And this is a contradiction since r is less than d but d is the lowest value where a^d ≡ 1 (mod p).

(12) So we reject our assumption at #5.

QED

Lemma 2: if a ≠ 0 and a is a positive integer less than p odd prime p, then a ∈ U_p.

(1) gcd(a,p)=1

(2) There exists u,v such that au + pv = 1. [Bezout's Identity, see here]

(3) Then, au - 1 = -pv

(4) Then au ≡ 1 (mod p) [See here for review of modular arithmetic]

(5) Then a is a unit mod p [By definition of unit mod p above]

QED

Corollary 2.1 There are p-1 elements in U_p

This follows directly from Lemma 2 above.

Lemma 3: if gcd(a,n)= n/d and a = (n/d)a', then gcd(a',d) = 1

(1) Assume gcd(a',d) = g which is greater than 1.

(2) g divides a' and g divides d

(3) There exists u,v such that gu=a', gv=d

(4) (ng)/d is greater than (n)/d since g is greater than 1.

(5) a = (n/d)*a' = (n/d)*gu = (ng/d)*u

(6) n = (n/d)*d = (n/d)*gv = (ng/d)*v

(7) But then (ng)/d divides a and (ng)/d divides n and (ng/a) is greater than (n/d)

(8) But (n/d) is gcd(a,n) so we have a contradiction.

(9) Therefore, we reject our assumption in #1.

QED

Lemma 4: The sum of φ(n) such that (d divides n) = n.

(1) Let S be a set = { 1, 2, 3, ..., n }

(2) Let S_d = the set of elements a in S where gcd(a,n) = n/d.

For example, let's consider n=8.

S₂ = elements a where gcd(a,8) = 8/2 = 4 = { 4 }

S₄ = elements a where gcd(a,8) = 8/4 = 2 = { 2 }

S₈ = elements a where gcd(a,8) = 8/8 = 1 = { 1, 3, 5, 7}

Another example, let's consider n = 12

S₂ = elements a where gcd(a,12) = 12/2 = 6 = { 6 }

S₃ = elements a where gcd(a,12) = 12/3 = 4 = {4, 8}

S₄ = elements a where gcd(a,12) = 12/4 = 3 = {3, 9}

S₁₂ = elements a where gcd(a,12) = 12/12 = 1 = { 1, 5, 11}

(3) We note that the total # of all S_d = n since:

(a) Let b = gcd(a,n)

(b) By definition b divides n [otherwise, n ≠ gcd(a,n)]

(c) There exists c such that n = bc and we see that b = n/c

(d) So we see that b ∈ S_c

(e) We also note that each element is only in 1 S_d since d = n/gcd(a,n)

(4) Let a' = (ad)/n for any integer a in S_d

(5) a' is an integer since:

(a) d=n/gcd(a,n)

(b) a' = (ad)/n = (a)[n/gcd(a,n)]/n = (an)/(gcd(a,n)n) = a/gcd(a,n)

(c) We know that gcd(a,n) divides a by definition of gcd (see here if more info needed)

(6) gcd(a',d) = 1 since a = (n/d)*a' [From Lemma 3 above]

(7) Now, we see for each S_d there is a one-to-one correspondence between this element and the value a' where:

(a) a' is between 1 and d [since a' = ad/n and a is between 1 and n]

(b) gcd(a',d)=1 [from #6]

(c) the total number of elements a' = φ(d) [By definition of φ(d) ]

(8) So, #7 gives us that the total number of elements for any S_d = φ(d)

(9) By Step #3, we can put this all together to give us: the sum of φ(d) for d that divide n = n.

QED

Lemma 5: if a is an element of U_p and order(a)=d, then a¹, a², ..., a^d are distinct modulo p.

(1) Let k = order of a.

(2) We can assume that k is greater than 2.

If k=1, then we are done since there is only 1 element a¹

If k=2, then we are done since we have 2 distinct elements a¹ and a².

(3) Let's assume that that the set of elements is not distinct.

(4) Then, there exists some u,v such that:

1 ≤ u is less than k
1 ≤ v is less than k
u ≠ v
a^u ≡ a^v (mod p)

We can assume that u,v are less than k since a^k ≡ 1 (mod p) and order(a)=k implies that no other aⁱ = 1 (by definition of order).

(5) Let's assume that u is less than v

Since u ≠ v, we can assume label the smaller one u and the larger one v.

(6) We know that there exists t such that t = k - v and t ≥ 1 so that k = t + v

(7) a^t*a^v ≡ a^k ≡ 1 (mod p)

(8) But since a^u ≡ a^v (mod p), then we have:
a^t*a^u ≡ a^t+u ≡ 1 (mod p)

(9) But u + t is less than k since u is less than v and since k = t + v.

(10) And this is impossible since k is the order. So we have a contradiction and we reject our asusmption in #3.

QED

Lemma 6: x - h divides xⁱ - hⁱ

(1) Case i = 1, 2, 3

x - h divides x¹ - h¹

x² - h² = (x + h)(x - h)

x³ - h³ = (x - h)(x² + h² + hx)

(2) Assume that x-h divides up to some value xⁿ - hⁿ such that x ≥ 3.

(3) hxⁿ - hⁿx = hx(x^n-1 - h^n-1)

(4) Now x-h divides x^n-1 - a^n-1 by our assumption in #2.

(5) So x-h divides hxⁿ - hⁿx

(6) Now xⁿ⁺¹ - hⁿ⁺¹ = (xⁿ + hⁿ)(x - h) + hxⁿ - hⁿx.

(7) Since x-h divides hxⁿ - hⁿx, using (#6), we find that it must also divide xⁿ⁺¹ - hⁿ⁺¹.

(8) So, we apply the principle of induction and we are done.

QED

Lemma 7: Lagrange's Theorem

Let a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀ ≡ 0 (mod p) where a_i is not divisible by p for some i, then there are at most n roots that satisfy this equation.

(1) Case n = 0

If n=0, then there is only a₀ which is not divisible by p. Therefore, there are no solutions.

(2) Now assume that it is true up to n-1 so for each equation a_n-1x^n-1 + ... + a₁x¹ + a₀ ≡ 0 (mod p), there are at most n-1 solutions.

(3) Let f(x) = a_nxn + ... + a₁x + a₀

(4) We can assume that there is at least one solution h such that f(h) ≡ 0 (mod p)

If there was no solution, then we have shown that the total number of solutions is ≤ n.

(5) So f(x) - f(h) =

NOTE: We switch i to 1 since x⁰ - h⁰ = 0.

(6) From Lemma 6, we know that x - h divides xⁱ - hⁱ

(7) So for each i in (#5), we have:
xⁱ - hⁱ = (x - h)(x^i-1 + hx^i-2 + ... + h^i-2x + h^i-1)

(8) Let g(x) = the sum of all equations created by #7. This then gives us:
f(x) - f(h) = (x-a)g(x)

(9) By our assumption in #2, we can assume that g(x) has at most n-1 solutions whereby g(x) ≡ 0 (mod p) since:

(a) g(x) has integer coefficients (from Lemma 6)

(b) p cannot divide all the coefficients of g(x) since;

If it did, it would divide g(x) and it would divide f(h), and this would mean that it would divide f(x).

But it cannot divide f(x) since by assumption it does not divide all the a_i.

Therefore, p cannot divide all the coefficients.

(10) For each solution of f(x), we know that it must divide f(x) - f(h) and therefore, it must divide (x-h)g(x).

(11) This means that for each solution of f(x), p either divides (x-h) or p divides g(x).

(12) Now, there is only one solution that solves for x-h.

(13) And, there are at most n-1 solutions that solve for g(x).

(14) So, there are a total of n solutions that solve for (x-h)g(x).

QED

Lemma 8: if a is an element of U_p with order(a) = d, then there exists b,i such that a ≡ bⁱ (mod p) and 1 ≤ i ≤ d and gcd(i,d)=1.

(1) By Lemma 5 above, the set of elements in U_p with order=d consist of b¹, b², ..., b^d.

(2) But we note that all elements of order=d solve the equation x^d - 1 ≡ 0 (mod p) [By the definition of Order]

(3) From Lemma 7 above, we know that there are at most d solutions to x^d - 1 ≡ 0 (mod p) so we know that the items lists in #1 are the complete set.

(4) So, there must exist a value i such that a ≡ bⁱ (mod p).

(5) Let j = gcd(i,d)

(6) a^d/j ≡ b^(id/j) ≡ (b^d)^i/j ≡ 1^i/j ≡ 1 (mod p)

(7) But if j is greater than 1, then d/j is less than d which is impossible since d is the order [see definition of order above]

(8) So, j = 1.

QED

Lemma 9: If w(d) is the number of elements in Up that have order = d, then w(d) ≤ φ(d)

(1) We can assume that w(d) ≥ 1.

If there are no elements with order d, then we have w(d)=0 which is less than φ(d).

(2) From (#1), for each order, we know that there exists an element a such that order(a)=d.

(3) We also know each value a¹, a², ... a^d are distinct mod p. [See Lemma 5]

(4) Each value aⁱ in (#3) solves the polynomial a^d ≡ 1 (mod p) since:

(aⁱ)^d ≡ a^di ≡ (a^d)ⁱ ≡ 1 (mod p) [By the definition of order, see above]

(5) Now, a^d - 1 has at most d roots. [See Lemma 7]

(6) So, the elements in #3 are the complete set of roots.

(7) Now, if we take the set of all elements a that have order(a)=d, there exists some b,i such that a ≡ bⁱ (mod p), then 1 ≤ i ≤ d and gcd(i,d)=1. [See Lemma 8]

(8) From (#7), we know that there is a one-to-one correspondence between the number of elements that have order(a) = d and the value bⁱ where i is between 1 and d and gcd(i,d)=1.

(9) So that, from (#8), we know that the total number of elements a that have order(a)=d is none other than φ(d).

QED

Lemma 10: If p is a prime, then U_p has φ(d) elements of order d for each d that divides p-1.

(1) Let w(d) = the number of elements in U_p that have the order = d.

(2) The order of each element divides p-1. [See Lemma 1]

(3) The total of all w(d) such that (d divides p-1) = p-1.

There are p-1 elements that make up U_p. [See Corollary 2.1 above]

Each element has a unique order. [See definition of Order above]

Each order must divide p-1 [by Lemma 1]

So, all elements have an order that divides p-1, so the total w(d) = p-1.

(4) The sum of all φ(d) such that (d divides p-1) = p-1. [See Lemma 4]

(5) The total for each d that divides n of (φ(d) - w(d)) = p-1 - (p-1) = 0.

(6) Now w(d) ≤ φ(d). [See Lemma 9]

(7) So w(d) = φ(d) [By combining #5 and #6]

QED

Theorem 1: If p is an odd prime, then U_p is cyclic with order p-1.

(1) There exists an integer d such that d = p-1.

(2) There are φ(p-1) elements of order p-1 in U_p [See Lemma 10]

(3) Since φ(p-1) ≥ 1 (see definition of φ(x) above), the group contains at least one element of order=p-1. Let's call this element a. [See Lemma 10]

(4) But we also know that a¹, a², ... a^p-1 are distinct. [By Lemma 5 above]

(5) So, by definition, a is a primitive root for U_p and U_p is cyclic [See Definition 3 and Definition 4 above]

QED