Today, it was announced that Lennart Carleson has won the Abel Prize for 2006 for his work on harmonic analysis and the theory of smooth dynamical systems.
You can check out the BBC story here. Here is the link to the Abel Prize web site.
The Abel Prize money is roughly $920,000. The prize is awarded by the Norwegian Academy of Sciences and Letters in recognition of "outstanding scientific work in the field of mathematics" (see here) . The prize will be presented in May by King Harald of Norway as part of a formal ceremony.
The prize is named in honor of the Norwegian mathematican Niels Henrik Abel.
Thursday, March 23, 2006
Saturday, March 11, 2006
Taylor Series
The Taylor Series is one of the most useful results in all of mathematics. The method in all its generality was first presented by Brook Taylor. To see an application for Taylor's Series, check out Euler's Formula.
The proof for Taylor's Series depends on basic calculus.
For anyone who does not feel comfortable with the notation f(x) or the concept of a mathematical function, start here.
For anyone who does not know about derivatives or about the notation f'(x), f''(x), or fn(x), start here.
Theorem: Taylor Series
if
(a) f is a function with derivatives of all orders
(b) (lim n → inf)[f(n+1)(z)]/(n+1)!(x-a)n+1 = 0
then:
f(x) = f(a) + f'(a)(x-a) + [f''(a)/2!](x-a)2 + .... + [f(n)(a)/n!](x-a)n + ....
Proof:
(1) Let n be an arbitrary positive integer.
(2) From Taylor's Formula, we have:
f(x) = Pn(x) + Rn(x)
where:
Pn(x) = f(a) + f'(a)(x-a) + f''(a)[(x-a)2]/2! + ... + f(n)[(x-a)n]/n!
and
Rn(x) = [f(n+1)(z)]/(n+1)!(x-a)n+1
where z is between a and x.
(3) From assumption b, we see that:
lim (n → inf) Rn(x) = 0.
(4) Then it follows that:
f(x) = lim (n → inf) Pn(x) =
= f(a) + f'(a)(x-a) + [f''(a)/2!](x-a)2 + .... + [f(n)(a)/n!](x-a)n + ....
QED
References
The proof for Taylor's Series depends on basic calculus.
For anyone who does not feel comfortable with the notation f(x) or the concept of a mathematical function, start here.
For anyone who does not know about derivatives or about the notation f'(x), f''(x), or fn(x), start here.
Theorem: Taylor Series
if
(a) f is a function with derivatives of all orders
(b) (lim n → inf)[f(n+1)(z)]/(n+1)!(x-a)n+1 = 0
then:
f(x) = f(a) + f'(a)(x-a) + [f''(a)/2!](x-a)2 + .... + [f(n)(a)/n!](x-a)n + ....
Proof:
(1) Let n be an arbitrary positive integer.
(2) From Taylor's Formula, we have:
f(x) = Pn(x) + Rn(x)
where:
Pn(x) = f(a) + f'(a)(x-a) + f''(a)[(x-a)2]/2! + ... + f(n)[(x-a)n]/n!
and
Rn(x) = [f(n+1)(z)]/(n+1)!(x-a)n+1
where z is between a and x.
(3) From assumption b, we see that:
lim (n → inf) Rn(x) = 0.
(4) Then it follows that:
f(x) = lim (n → inf) Pn(x) =
= f(a) + f'(a)(x-a) + [f''(a)/2!](x-a)2 + .... + [f(n)(a)/n!](x-a)n + ....
QED
References
- Edwards & Penny, Calculus and Analytic Geometry
Friday, March 10, 2006
Taylor's Formula
In today's blog, I will go over Taylor's Formula. This is a theorem that can be used to establish the Taylor Series and the MacLaurin Series which I use in my proof of Euler's Identity.
If you are not familiar with continuous functions or closed intervals, start here.
If you would like a review of derivatives, start here.
Theorem: Taylor's Formula
Let f(x) be a continuous function over the closed interval [a,b] that has an (n+1) derivative which is referenced by f(n+1)(x) where n is a positive integer.
Then:
f(b) = f(a) + f'(a)(b-a) + ... + [f(n)(a)/n!](b-a)n + [f(n+1)(z)/(n+1)!](b-a)n+1)
for some number z which lies between a and b.
Proof:
(1) Let H = f(b) - f(a) - f'(a)(b-a) - [f''(a)/2!](b-a)2 - ... - [f(n)(a)/n!](b-a)n
(2) Let K = H/(b-a)n+1
(3) Let g(x) be a function such that:
g(x) = f(b) - f(x) - f'(x)(b-x) -[f''(x)/2!](b-x)2 - ... - [f(n)(x)/n!](b-x)n - K(b-x)n+1
(4) We can see that g(x) is a continuous function since:
(a) f(x) is continuous over [a,b] by the given.
(b) f(n) is a continuous function since by the given we know that f(x) has an (n+1) derivative and since f(x) is differentiable at x, then it is continuous at x (see here)
(c) (b-x)n is continuous over [a,b] since f(x) is continuous since:
Let h(x)=b-x
h(x) is continuous since it is the addition of two continuous functions i(x)=b and j(x)=-x [See here for proof of the Addition Law]
(b-x)n is continuous by the Multiplication Law [See here for proof of the Multiplication Law]
(b-x)n = (b - x)*(b-x)*... since n is a positive integer.
(d) f(b) is continuous since it is a constant. (See here)
(e) Each f(n)(x)/n! is continuous since (-1/n!) can be thought of as a constant function h(x)=(-1/n!) and the multiplication of two continuous functions is itself continuous (see here)
(f) Finally, g(x) is continuous because the addition of a set of continuous functions is itself continuous (see here)
(5) We can see that g(a) = 0 since:
g(a) = H - H/(b-a)n+1*(b-a)n+1 = H - H = 0
(6) We can also see that g(b) = 0 since:
g(b) = f(b) - f(b) - f'(b)(b-b) - [f''(b)/2!](b-b)2 - ... - [f(n)(b)/n!](b-b)n - K(b-b)n+1
(7) By Rolle's Theorem, since g(x) is continuous on [a,b], we know that there exists a value z such that z ∈ [a,b] and g'(z) = 0. [See here for Rolle's Theorem]
(8) If we differentiate on g(x), we get:
g'(x) = -f'(x) + f'(x) -f(2)(x)(b-x) + f(2)(x)(b-x) - (1/2!)f(3)(x)(b-x)2 + (1/2!)f(3)(x)(b-x)2 - (1/3!)f(4)(x)(b-x)3 + ... + [1/(n-1)!]f(n)(x)(b-x)n-1 - (1/n!)f(n+1)(x)(b-x)n + (n+1)K(b-x)n since:
(a) g(x) = f(b) - f(x) - f'(x)(b-x) -[f''(x)/2!](b-x)2 - ... - [f(n)(x)/n!](b-x)n - K(b-x)n+1
(b) By Lemma 3 here, we can differentiate each individual product in the sum.
(c) f(b) is a constant so d/dx(f(b)) = 0 [See here for Constant Rule]
(d) d/dx(-f(x)) = -f'(x) [See here for details]
(e) d/dx[-f'(x)(b-x)] = -f''(x)(b-x) - f'(x)(-1) = f'(x) -f''(x)(b-x) [See here for the Product Rule]
(f) d/dx[(-f''(x)/2!)(b-x)2] = (-f(3)(x)/2!)(b-x)2 + [-f''(x)/2!](2)(b-x)(-1)] =
= (-f(3)/2!)(b-x)2 + f''(x)(b-x) [See here for Generalized Power Rule]
(g) d/dx([-f(n)(x)/n!](b-x)n) = (-f(n+1)(x)/n!)(b-x)n + [-f(n)(n)/n!](n)(b-x)n-1*(-1) =
= (-f(n+1)(x)/n!)(b-x)n +[ f(n)/(n-1)!](b-x)n-1
(h) Since K is a constant
d/dx(-K(b-x)n+1) = (n+1)(-K)(b-x)n(-1) = (n+1)K(b-x)n
(9) We see that most of the terms cancel out so that we get:
g'(x) = (n+1)K(b-x)n - (1/n!)f(n+1)(x)(b-x)n
(10) Applying the fact that g'(z) = 0 from step #7 gives us:
g'(z) = (n+1)K(b-z)n - (1/n!)f(n+1)(z)(b-z)n = 0
(11) We can divide both sides by (b-z)n to get:
(n+1)K - (1/n!)f(n+1)(z) = 0
(12) Now we can rearrange (#11) to get:
K = [(1/n!)f(n+1)(z)]/(n+1) = [f(n+1)(z)]/(n+1)!
(13) Now, using (#12) and (#3) with x=a, we get:
g(a) = 0 = f(b) - f(a) - f'(a)(b-a) - [f''(a)/2!](b-a)2 - ... - [f(n)(a)/n!](b-a)n - [(b-a)n+1][f(n+1)(z)/(n+1)!]
(14) Now, if we move over all the elements after f(b), we get:
f(b) = f(a) + f'(a)(b-a) + [f''(a)/2!](b-a)2 + ... + [f(n)(a)/n!](b-a)n + [(b-a)n+1][f(n+1)(z)/(n+1)!]
QED
References
If you are not familiar with continuous functions or closed intervals, start here.
If you would like a review of derivatives, start here.
Theorem: Taylor's Formula
Let f(x) be a continuous function over the closed interval [a,b] that has an (n+1) derivative which is referenced by f(n+1)(x) where n is a positive integer.
Then:
f(b) = f(a) + f'(a)(b-a) + ... + [f(n)(a)/n!](b-a)n + [f(n+1)(z)/(n+1)!](b-a)n+1)
for some number z which lies between a and b.
Proof:
(1) Let H = f(b) - f(a) - f'(a)(b-a) - [f''(a)/2!](b-a)2 - ... - [f(n)(a)/n!](b-a)n
(2) Let K = H/(b-a)n+1
(3) Let g(x) be a function such that:
g(x) = f(b) - f(x) - f'(x)(b-x) -[f''(x)/2!](b-x)2 - ... - [f(n)(x)/n!](b-x)n - K(b-x)n+1
(4) We can see that g(x) is a continuous function since:
(a) f(x) is continuous over [a,b] by the given.
(b) f(n) is a continuous function since by the given we know that f(x) has an (n+1) derivative and since f(x) is differentiable at x, then it is continuous at x (see here)
(c) (b-x)n is continuous over [a,b] since f(x) is continuous since:
Let h(x)=b-x
h(x) is continuous since it is the addition of two continuous functions i(x)=b and j(x)=-x [See here for proof of the Addition Law]
(b-x)n is continuous by the Multiplication Law [See here for proof of the Multiplication Law]
(b-x)n = (b - x)*(b-x)*... since n is a positive integer.
(d) f(b) is continuous since it is a constant. (See here)
(e) Each f(n)(x)/n! is continuous since (-1/n!) can be thought of as a constant function h(x)=(-1/n!) and the multiplication of two continuous functions is itself continuous (see here)
(f) Finally, g(x) is continuous because the addition of a set of continuous functions is itself continuous (see here)
(5) We can see that g(a) = 0 since:
g(a) = H - H/(b-a)n+1*(b-a)n+1 = H - H = 0
(6) We can also see that g(b) = 0 since:
g(b) = f(b) - f(b) - f'(b)(b-b) - [f''(b)/2!](b-b)2 - ... - [f(n)(b)/n!](b-b)n - K(b-b)n+1
(7) By Rolle's Theorem, since g(x) is continuous on [a,b], we know that there exists a value z such that z ∈ [a,b] and g'(z) = 0. [See here for Rolle's Theorem]
(8) If we differentiate on g(x), we get:
g'(x) = -f'(x) + f'(x) -f(2)(x)(b-x) + f(2)(x)(b-x) - (1/2!)f(3)(x)(b-x)2 + (1/2!)f(3)(x)(b-x)2 - (1/3!)f(4)(x)(b-x)3 + ... + [1/(n-1)!]f(n)(x)(b-x)n-1 - (1/n!)f(n+1)(x)(b-x)n + (n+1)K(b-x)n since:
(a) g(x) = f(b) - f(x) - f'(x)(b-x) -[f''(x)/2!](b-x)2 - ... - [f(n)(x)/n!](b-x)n - K(b-x)n+1
(b) By Lemma 3 here, we can differentiate each individual product in the sum.
(c) f(b) is a constant so d/dx(f(b)) = 0 [See here for Constant Rule]
(d) d/dx(-f(x)) = -f'(x) [See here for details]
(e) d/dx[-f'(x)(b-x)] = -f''(x)(b-x) - f'(x)(-1) = f'(x) -f''(x)(b-x) [See here for the Product Rule]
(f) d/dx[(-f''(x)/2!)(b-x)2] = (-f(3)(x)/2!)(b-x)2 + [-f''(x)/2!](2)(b-x)(-1)] =
= (-f(3)/2!)(b-x)2 + f''(x)(b-x) [See here for Generalized Power Rule]
(g) d/dx([-f(n)(x)/n!](b-x)n) = (-f(n+1)(x)/n!)(b-x)n + [-f(n)(n)/n!](n)(b-x)n-1*(-1) =
= (-f(n+1)(x)/n!)(b-x)n +[ f(n)/(n-1)!](b-x)n-1
(h) Since K is a constant
d/dx(-K(b-x)n+1) = (n+1)(-K)(b-x)n(-1) = (n+1)K(b-x)n
(9) We see that most of the terms cancel out so that we get:
g'(x) = (n+1)K(b-x)n - (1/n!)f(n+1)(x)(b-x)n
(10) Applying the fact that g'(z) = 0 from step #7 gives us:
g'(z) = (n+1)K(b-z)n - (1/n!)f(n+1)(z)(b-z)n = 0
(11) We can divide both sides by (b-z)n to get:
(n+1)K - (1/n!)f(n+1)(z) = 0
(12) Now we can rearrange (#11) to get:
K = [(1/n!)f(n+1)(z)]/(n+1) = [f(n+1)(z)]/(n+1)!
(13) Now, using (#12) and (#3) with x=a, we get:
g(a) = 0 = f(b) - f(a) - f'(a)(b-a) - [f''(a)/2!](b-a)2 - ... - [f(n)(a)/n!](b-a)n - [(b-a)n+1][f(n+1)(z)/(n+1)!]
(14) Now, if we move over all the elements after f(b), we get:
f(b) = f(a) + f'(a)(b-a) + [f''(a)/2!](b-a)2 + ... + [f(n)(a)/n!](b-a)n + [(b-a)n+1][f(n+1)(z)/(n+1)!]
QED
References
- Edwards & Penny, Calculus and Analytic Geometry
Friday, February 24, 2006
Euler's Formula
Today's proof for Euler's Formula is based on the Taylor's Series. Euler's Formula is the equation:
eix = cosx + isinx
In a previous blog, I spoke about Euler's Identity which is derived from Euler's Formula. Richard Cotes was the first person to provide a proof but the great popularizer of this result was Leonhard Euler. Euler's Identity is used in the construction of cyclotomic integers which are used in Kummer's proof of Fermat's Last Theorem for regular primes.
Lemma 1: Maclaurin's Series
f(x) = f(0) + (x/1!)f'(0) + (x2/2!)f''(0) + (x3/3!)f'''(0) + ... + (xn/n!)fn(0)
(1) Taylor's series gives us:
f(x) = f(a) + f'(a)(x-a) + [f''(a)/2!](x-a)2 + .... + [f(n)(a)/n!](x-a)n + ....
[See here for its proof]
(2) Now, if a=0, then we have:
f(x) = f(0) + (x/1!)f'(0) + (x2/2!)f''(0) + (x3/3!)f'''(0) + ... + (xn/n!)fn(0).
QED
Lemma 2: ex = 1 + (x/1) + (x2/2!) + (x3/3!) + ....
(1) Let f(x) = ex
(2) From the properties of ex [See here for details]:
f(x) = ex → f(0) = e0 = 1
f'(x) = ex → f'(0) =e0 = 1
fn(x) = ex → fn(0) = e0 = 1
(3) We know that ex is continuous since it has a derivative at each point. [See here for details of why this is true]
(4) By Lemma 1 above, we have:
ex = 1 + (x/1!)(1) + (x2/2!)(1) + ... (xn/n!)(1)
QED
Lemma 3: sinx = x - (x3/3!) + (x5/5!) - (x7/7!) + ...
(1) Let f(x) = sin x
(2) From the properties of sin, we know:
f(0) = sin(0) = 0 [See here for details if needed]
f'(x) = cos x → f'(0) = 1 [See here for proof if needed]
f''(x) = -sin(x) → f'(0) = 0 [See here for proof if needed]
f'''(x) = -cos x → f'(0) = -1
(3) From this, we see that:
fn(0) = 0 if n is even.
fn(0) = 1 if (n-1)/2 is even
fn(0) = -1 if (n-1)/2 is odd
(4) Putting this all together gives us:
sin x = (x/1)(1) + (x2/2!)(0) + (x3/3!)(-1) + ...
QED
Lemma 4: cos x = 1 - (x2)/2! + (x4/4!) - (x6/6!) + ...
(1) Let f(x) = cos x
(2) From the properties of cos, we know:
f(0) = cos(0) = 1 [Details if needed are found here]
f'(x) = -sin x → f'(0) = 0 [Details if needed are found here]
f''(x) = -cos(x) → f'(0) = -1
f'''(x) = sin x → f'(0) = 0
(3) From this, we see that:
fn(0) = 0 if n is odd.
fn(0) = 1 if (n/2) is even
fn(0) = -1 if (n/2) is odd
(4) Putting this all together gives us:
cos x = 1 + (x2/2!)(-1) + (x3/3!)(0) + (x4/4!)(1) + ...
QED
Theorem: Euler's Formula
eix = cos x + isin x
(1) From Lemma 2, we have:
eix = 1 + ix + (ix)2/2! + (ix)3/3! + ...
(2) Since i2 = -1 and i4 = 1, this gives us: (for details on i, see here)
eix = (1 - x2/2! + x4/4! + ...) + i(x - x3/3! + x5/5! + ...)
(3) From Lemma 4 above, we see that:
cos(x) = (1 - x2/2! + x4/4! + ...)
(4) From Lemma 3 above, we see that:
isin(x) = i(x - x3/3! + x5/5! + ...)
(5) Combining step #2 with step #3 and step #4 gives us:
eix = cos x + i sin x.
QED
Corollary: De Moivre's Formula
(cos x + isin x)n = cos(nx) + isin(nx)
Proof:
(1) (eix)n = einx
(2) (cos x + i sin x)n = cos(nx) + isin(nx) [Applying Euler's formula above]
QED
eix = cosx + isinx
In a previous blog, I spoke about Euler's Identity which is derived from Euler's Formula. Richard Cotes was the first person to provide a proof but the great popularizer of this result was Leonhard Euler. Euler's Identity is used in the construction of cyclotomic integers which are used in Kummer's proof of Fermat's Last Theorem for regular primes.
Lemma 1: Maclaurin's Series
f(x) = f(0) + (x/1!)f'(0) + (x2/2!)f''(0) + (x3/3!)f'''(0) + ... + (xn/n!)fn(0)
(1) Taylor's series gives us:
f(x) = f(a) + f'(a)(x-a) + [f''(a)/2!](x-a)2 + .... + [f(n)(a)/n!](x-a)n + ....
[See here for its proof]
(2) Now, if a=0, then we have:
f(x) = f(0) + (x/1!)f'(0) + (x2/2!)f''(0) + (x3/3!)f'''(0) + ... + (xn/n!)fn(0).
QED
Lemma 2: ex = 1 + (x/1) + (x2/2!) + (x3/3!) + ....
(1) Let f(x) = ex
(2) From the properties of ex [See here for details]:
f(x) = ex → f(0) = e0 = 1
f'(x) = ex → f'(0) =e0 = 1
fn(x) = ex → fn(0) = e0 = 1
(3) We know that ex is continuous since it has a derivative at each point. [See here for details of why this is true]
(4) By Lemma 1 above, we have:
ex = 1 + (x/1!)(1) + (x2/2!)(1) + ... (xn/n!)(1)
QED
Lemma 3: sinx = x - (x3/3!) + (x5/5!) - (x7/7!) + ...
(1) Let f(x) = sin x
(2) From the properties of sin, we know:
f(0) = sin(0) = 0 [See here for details if needed]
f'(x) = cos x → f'(0) = 1 [See here for proof if needed]
f''(x) = -sin(x) → f'(0) = 0 [See here for proof if needed]
f'''(x) = -cos x → f'(0) = -1
(3) From this, we see that:
fn(0) = 0 if n is even.
fn(0) = 1 if (n-1)/2 is even
fn(0) = -1 if (n-1)/2 is odd
(4) Putting this all together gives us:
sin x = (x/1)(1) + (x2/2!)(0) + (x3/3!)(-1) + ...
QED
Lemma 4: cos x = 1 - (x2)/2! + (x4/4!) - (x6/6!) + ...
(1) Let f(x) = cos x
(2) From the properties of cos, we know:
f(0) = cos(0) = 1 [Details if needed are found here]
f'(x) = -sin x → f'(0) = 0 [Details if needed are found here]
f''(x) = -cos(x) → f'(0) = -1
f'''(x) = sin x → f'(0) = 0
(3) From this, we see that:
fn(0) = 0 if n is odd.
fn(0) = 1 if (n/2) is even
fn(0) = -1 if (n/2) is odd
(4) Putting this all together gives us:
cos x = 1 + (x2/2!)(-1) + (x3/3!)(0) + (x4/4!)(1) + ...
QED
Theorem: Euler's Formula
eix = cos x + isin x
(1) From Lemma 2, we have:
eix = 1 + ix + (ix)2/2! + (ix)3/3! + ...
(2) Since i2 = -1 and i4 = 1, this gives us: (for details on i, see here)
eix = (1 - x2/2! + x4/4! + ...) + i(x - x3/3! + x5/5! + ...)
(3) From Lemma 4 above, we see that:
cos(x) = (1 - x2/2! + x4/4! + ...)
(4) From Lemma 3 above, we see that:
isin(x) = i(x - x3/3! + x5/5! + ...)
(5) Combining step #2 with step #3 and step #4 gives us:
eix = cos x + i sin x.
QED
Corollary: De Moivre's Formula
(cos x + isin x)n = cos(nx) + isin(nx)
Proof:
(1) (eix)n = einx
(2) (cos x + i sin x)n = cos(nx) + isin(nx) [Applying Euler's formula above]
QED
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, xi 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:
eix = 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
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, xi 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:
eix = 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 xn = 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 x3 = 1. The insight to why this is so comes from considering Euler's Identity:
eiπ=-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 x3 = 1 are:
1, e(2iπ)/3, e(4iπ)/3
Since (e(2iπ)/3)3 = e2iπ = (-1)2 = 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 e2iπ/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
Cyclotomic integers are based the equation xn = 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 x3 = 1. The insight to why this is so comes from considering Euler's Identity:
eiπ=-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 x3 = 1 are:
1, e(2iπ)/3, e(4iπ)/3
Since (e(2iπ)/3)3 = e2iπ = (-1)2 = 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 e2iπ/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
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 would like to start with Gauss's Lemma, start here.
Today's proof is taken from Gareth A. Jones and J. Mary Jones' Elementary Number Theory.
Lemma 1:
(a) Let x' = (p+1)/2 - x
(b) Let y' = (q+1)/2 - y
Then
qx - py is greater than -(p/2) if and only if qx' - py' is less than q/2.
(1) Assume that qx - py is greater than (-p/2)
(2) (p/2) + qx - py is greater than 0
(3) (p +q-q+pq-pq)/2 + qx - py is greater than 0
(4) (p - q + pq - pq)/2 + qx - py is greater than (-q/2)
(5) -q(p+1)/2 + p(q+1)/2 + qx - py is greater than (-q/2)
(6) q(p+1)/2 - p(q+1)/2 - qx + py is less than (q/2)
(7) q[(p+1)/2 - x] - p[(q+1)/2 - y] is less than (q/2)
(8) qx' - py' is less than (q/2)
(9) We can use the same reasoning to show that:
if qx' - py is less than (q/2), then qx - py is greater than (-p)/2.
QED
Lemma 2: Given:
(a) Let P = { 1, 2, ... (p-1)/2 }
(b) Let Q = {1, 2, ... (q-1)/2 }
(c) Let A be the set of points PxQ such that qx-py is greater than (-p)/2. [See diagram in Lemma 3]
(d) Let B be the set of points PxQ such that qx-py is less than (q/2) [See diagram in Lemma 3]
(e) Let α be the number of points in A
(f) Let β be the number of points in B
Then:
There is a one-to-one mapping between α and β [So that, they both have the same number of points]
Proof:
(1) Let's define the following function:
p(x,y) = (x',y') = [ (p+1)/2 - x, (q+1)/2 - y ]
(2) p(A) = p(B) since qx - py is greater than (-p)/2 implies that qx' - py is less than (q/2). [See Lemma 1 above]
(3) p(B) = p(A) since qx - py is less than (q/2) implies that qx' - py' is greater than (-p)/2. [See Lemma 1 above]
QED
Lemma 3: Given
(a) p,q are distinct, odd primes
(b) P is a set = { 1, 2, ... (p-1)/2 }
(c) Q is a set = { 1, 2, ... (q-1)/2 }
(d) x,y are integers such that x ∈ P and y ∈ Q
(e) (-p/2) is less than qx - py which is less than (q/2).
(f) μ = the number of elements (x,y) ∈ P x Q where (-p/2) is less than qx - py which is less than -1.
(g) ν = the number of elements (y,x) ∈ Q x P where (-q/2) is less than py - qx which is less than -1.
Then:
(-1)μ + ν = (-1)[(p-1)(q-1)]/4
Proof:
(1) The set of assumptions can be represented as a graph:
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
If you would like to start this proof at the beginning, start here.
If you would like to start with Gauss's Lemma, start here.
Today's proof is taken from Gareth A. Jones and J. Mary Jones' Elementary Number Theory.
Lemma 1:
(a) Let x' = (p+1)/2 - x
(b) Let y' = (q+1)/2 - y
Then
qx - py is greater than -(p/2) if and only if qx' - py' is less than q/2.
(1) Assume that qx - py is greater than (-p/2)
(2) (p/2) + qx - py is greater than 0
(3) (p +q-q+pq-pq)/2 + qx - py is greater than 0
(4) (p - q + pq - pq)/2 + qx - py is greater than (-q/2)
(5) -q(p+1)/2 + p(q+1)/2 + qx - py is greater than (-q/2)
(6) q(p+1)/2 - p(q+1)/2 - qx + py is less than (q/2)
(7) q[(p+1)/2 - x] - p[(q+1)/2 - y] is less than (q/2)
(8) qx' - py' is less than (q/2)
(9) We can use the same reasoning to show that:
if qx' - py is less than (q/2), then qx - py is greater than (-p)/2.
QED
Lemma 2: Given:
(a) Let P = { 1, 2, ... (p-1)/2 }
(b) Let Q = {1, 2, ... (q-1)/2 }
(c) Let A be the set of points PxQ such that qx-py is greater than (-p)/2. [See diagram in Lemma 3]
(d) Let B be the set of points PxQ such that qx-py is less than (q/2) [See diagram in Lemma 3]
(e) Let α be the number of points in A
(f) Let β be the number of points in B
Then:
There is a one-to-one mapping between α and β [So that, they both have the same number of points]
Proof:
(1) Let's define the following function:
p(x,y) = (x',y') = [ (p+1)/2 - x, (q+1)/2 - y ]
(2) p(A) = p(B) since qx - py is greater than (-p)/2 implies that qx' - py is less than (q/2). [See Lemma 1 above]
(3) p(B) = p(A) since qx - py is less than (q/2) implies that qx' - py' is greater than (-p)/2. [See Lemma 1 above]
QED
Lemma 3: Given
(a) p,q are distinct, odd primes
(b) P is a set = { 1, 2, ... (p-1)/2 }
(c) Q is a set = { 1, 2, ... (q-1)/2 }
(d) x,y are integers such that x ∈ P and y ∈ Q
(e) (-p/2) is less than qx - py which is less than (q/2).
(f) μ = the number of elements (x,y) ∈ P x Q where (-p/2) is less than qx - py which is less than -1.
(g) ν = the number of elements (y,x) ∈ Q x P where (-q/2) is less than py - qx which is less than -1.
Then:
(-1)μ + ν = (-1)[(p-1)(q-1)]/4
Proof:
(1) The set of assumptions can be represented as a graph:
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
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 would like to start with Gauss's Lemma, start here.
Today's proof is taken from Gareth A. Jones and J. Mary Jones' Elementary Number Theory.
Lemma 1:
if
(a) p,q are odd primes
(b) P = the set of integers {1, 2, ..., (p-1)/2}
(c) N = the set of integers P = { -1, -2, ..., -(p-1)/2 }
(d) qx ≡ n (mod p) where n ∈ N, x ∈ P
then:
there exists a y such that (-p/2) is less than (qx - py) which is less than 0.
Proof:
(1) There exists y such that qx - n = py [Since qx ≡ n (mod p) -- see here for review of modular arithmetic]
(2) This then gives us: qx - py = n.
(3) qx - py is less than 0 since n is less than 0.
(4) qx - py is greater than (-p/2) since n ≥ -(p-1)/2 = (-p+1)/2 which is greater than -p/2.
QED
Lemma 2: if p,q,x,y are integers such that:
(a) p,q are positive, odd primes
(b) (-p/2) is less than qx - py
(c) qx - py is less than 0
(d) x,y are positive.
Then:
(a) there is only 1 value that y can have.
(b) 0 is less than qx/p which is less than y
(c) y is less than (qx/p) + 1/2.
Proof:
(1) Let y be any integer that satisfies the conditions (a),(b),(c)
(2) There is no value y' that y' is an integer and less than y which satisfies (a),(b),(c) since:
(a) qx - p(y-1) = qx - py + p
(b) We know that absolute(p) is greater than absolute(qx-py) since (-p/2) is less than (qx-py) which is less than 0.
(c) Since p is positive and qx-py is negative, we know that qx-py + p is greater than 0.
(3) There is no value y' such that y' is an integer and greater than y which satisfies (a),(b),(c) since:
(a) qx - p(y+1) = qx - py - p
(b) Since -p is greater than -p/2, we know that qx-py-p is less than (-p/2).
(4) From (a),(b),(c), we know that (p/2) is greater than (py-qx) which is greater than 0.
(5) Dividing (4) by p gives us:
(1/2) is greater than y - (qx/p) which is greater than 0.
(6) From (5), we know that y is greater than (qx/p).
(7) From (5), we also know that (1/2) + (qx/p) is greater than y.
(8) Since q,x,p are positive, we know that qx/p is greater than 0.
(9) By (#8),(#6), we know that y is greater than 0.
QED
Lemma 3: if q,p,x,y are integers such that:
(a) p,q are positive, odd primes
(b) (-p/2) is less than qx - py
(c) qx - py is less than 0
(d) x ∈ { 1, 2, ..., (p-1)/2 }
(e) y is a positive integer
Then:
y is less than (qx/p) + 1/2 ≤ [q(p-1)]/2p + 1/2 which is less than q+1/2
Proof:
(1) From Lemma 2, we know that:
0 is less than (qx/p) which is less than y which is less than (qx/p) + 1/2.
(2) From (d), we know that x ≤ (p-1)/2.
(3) Combining (1) and (2), we have:
(qx/p) + (1/2) ≤ [q(p-1)]/2p + (1/2)
(4) We can conclude that [q(p-1)]/2p + (1/2) is less than (q+1)/2 since:
(a) [q(p-1)]/2p + (1/2) = (qp - q + p)/2p = [(qp/p - q/p + p/p)]/2 =
= (q - q/p + 1)/2 = (q + 1 - q/p)/2
(b) q/p is greater than 0 since q,p are odd primes.
(c) From (a) and (b), we have:
(q + 1 - q/p)/2 is less than (q+1)/2 [ Since 1 - q/p is less than 1 ]
QED
Lemma 4: if q,p are odd primes, then there exist μ, ν where:
(a) Using the Legendre Symbol (see here):
(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
If you would like to start this proof at the beginning, start here.
If you would like to start with Gauss's Lemma, start here.
Today's proof is taken from Gareth A. Jones and J. Mary Jones' Elementary Number Theory.
Lemma 1:
if
(a) p,q are odd primes
(b) P = the set of integers {1, 2, ..., (p-1)/2}
(c) N = the set of integers P = { -1, -2, ..., -(p-1)/2 }
(d) qx ≡ n (mod p) where n ∈ N, x ∈ P
then:
there exists a y such that (-p/2) is less than (qx - py) which is less than 0.
Proof:
(1) There exists y such that qx - n = py [Since qx ≡ n (mod p) -- see here for review of modular arithmetic]
(2) This then gives us: qx - py = n.
(3) qx - py is less than 0 since n is less than 0.
(4) qx - py is greater than (-p/2) since n ≥ -(p-1)/2 = (-p+1)/2 which is greater than -p/2.
QED
Lemma 2: if p,q,x,y are integers such that:
(a) p,q are positive, odd primes
(b) (-p/2) is less than qx - py
(c) qx - py is less than 0
(d) x,y are positive.
Then:
(a) there is only 1 value that y can have.
(b) 0 is less than qx/p which is less than y
(c) y is less than (qx/p) + 1/2.
Proof:
(1) Let y be any integer that satisfies the conditions (a),(b),(c)
(2) There is no value y' that y' is an integer and less than y which satisfies (a),(b),(c) since:
(a) qx - p(y-1) = qx - py + p
(b) We know that absolute(p) is greater than absolute(qx-py) since (-p/2) is less than (qx-py) which is less than 0.
(c) Since p is positive and qx-py is negative, we know that qx-py + p is greater than 0.
(3) There is no value y' such that y' is an integer and greater than y which satisfies (a),(b),(c) since:
(a) qx - p(y+1) = qx - py - p
(b) Since -p is greater than -p/2, we know that qx-py-p is less than (-p/2).
(4) From (a),(b),(c), we know that (p/2) is greater than (py-qx) which is greater than 0.
(5) Dividing (4) by p gives us:
(1/2) is greater than y - (qx/p) which is greater than 0.
(6) From (5), we know that y is greater than (qx/p).
(7) From (5), we also know that (1/2) + (qx/p) is greater than y.
(8) Since q,x,p are positive, we know that qx/p is greater than 0.
(9) By (#8),(#6), we know that y is greater than 0.
QED
Lemma 3: if q,p,x,y are integers such that:
(a) p,q are positive, odd primes
(b) (-p/2) is less than qx - py
(c) qx - py is less than 0
(d) x ∈ { 1, 2, ..., (p-1)/2 }
(e) y is a positive integer
Then:
y is less than (qx/p) + 1/2 ≤ [q(p-1)]/2p + 1/2 which is less than q+1/2
Proof:
(1) From Lemma 2, we know that:
0 is less than (qx/p) which is less than y which is less than (qx/p) + 1/2.
(2) From (d), we know that x ≤ (p-1)/2.
(3) Combining (1) and (2), we have:
(qx/p) + (1/2) ≤ [q(p-1)]/2p + (1/2)
(4) We can conclude that [q(p-1)]/2p + (1/2) is less than (q+1)/2 since:
(a) [q(p-1)]/2p + (1/2) = (qp - q + p)/2p = [(qp/p - q/p + p/p)]/2 =
= (q - q/p + 1)/2 = (q + 1 - q/p)/2
(b) q/p is greater than 0 since q,p are odd primes.
(c) From (a) and (b), we have:
(q + 1 - q/p)/2 is less than (q+1)/2 [ Since 1 - q/p is less than 1 ]
QED
Lemma 4: if q,p are odd primes, then there exist μ, ν where:
(a) Using the Legendre Symbol (see here):
(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
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: Qn: the set of quadratic residues
That is, these are the integers a mod n where a ≡ s2 (mod n) and s ∈ Un
NOTE: See here for a review of Un
Examples:
Q7 = { 1, 2, 4 }
12 ≡ 1 (mod 7) [ 1 ∈ U7 since 1 ≡ 1 (mod 7) ]
22 ≡ 4 (mod 7) [ 4 ∈ U7 since (4)(2) ≡ 1 (mod 7)]
42 ≡ 2 (mod 7) [ 2 ∈ U7 since (2)(4) ≡ 1 (mod 7)]
Q8 = { 1 }
12 ≡ 1 (mod 8)
Lemma 1:
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 Up, then gi ∈ Qp if and only if i is even.
Proof:
(1) if i is even, then gi/2 ∈ Up [See here for definition of primitive root]
(2) But gi/2 ∈ Up, then gi ≡ (gi/2)2 (mod p) and therefore gi ∈ Qp [See above for definition of Qp]
(3) if gi ∈ Qp, then there exists j such that gi ≡ (gj)2 (mod p) [Based on definition of Qp]
(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, gi ≡ gq(φ(p))+r ≡ (gφ(p))q*gr ≡ (1)q*gr ≡ gr (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:
g2j ≡ (1)q'*gr' ≡ gr' ≡ gr (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, gi must be an element of Qp. [See Lemma 1 above]
(4) From Lemma 2, we know that gi ∈ Qp 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 ≡ gi (mod p) (see here for definition of primitive root)
(7) Let h ≡ g(p-1)/2 (mod p)
(8) h2 ≡ gp-1 (mod p) [See here for a review of exponents if needed]
(9) φ(p) = p-1 [See here for details.]
(10) gp-1 ≡ gφ(p) ≡ 1 (mod p) [See Euler's Theorem]
(11) So p divides gp-1-1 → p divides h2 - 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 ≡ (gi)(p-1)/2 ≡ (g(p-1)/2)i ≡ hi ≡ (-1)i (mod p)
(16) Now from Lemma 3 above:
(17) Since a ≡ gi (mod p), we also have:
(18) Finally, since a(p-1)/2 ≡ (-1)i (mod p) from#15, we have:
QED
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: Qn: the set of quadratic residues
That is, these are the integers a mod n where a ≡ s2 (mod n) and s ∈ Un
NOTE: See here for a review of Un
Examples:
Q7 = { 1, 2, 4 }
12 ≡ 1 (mod 7) [ 1 ∈ U7 since 1 ≡ 1 (mod 7) ]
22 ≡ 4 (mod 7) [ 4 ∈ U7 since (4)(2) ≡ 1 (mod 7)]
42 ≡ 2 (mod 7) [ 2 ∈ U7 since (2)(4) ≡ 1 (mod 7)]
Q8 = { 1 }
12 ≡ 1 (mod 8)
Lemma 1:
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 Up, then gi ∈ Qp if and only if i is even.
Proof:
(1) if i is even, then gi/2 ∈ Up [See here for definition of primitive root]
(2) But gi/2 ∈ Up, then gi ≡ (gi/2)2 (mod p) and therefore gi ∈ Qp [See above for definition of Qp]
(3) if gi ∈ Qp, then there exists j such that gi ≡ (gj)2 (mod p) [Based on definition of Qp]
(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, gi ≡ gq(φ(p))+r ≡ (gφ(p))q*gr ≡ (1)q*gr ≡ gr (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:
g2j ≡ (1)q'*gr' ≡ gr' ≡ gr (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, gi must be an element of Qp. [See Lemma 1 above]
(4) From Lemma 2, we know that gi ∈ Qp 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 ≡ gi (mod p) (see here for definition of primitive root)
(7) Let h ≡ g(p-1)/2 (mod p)
(8) h2 ≡ gp-1 (mod p) [See here for a review of exponents if needed]
(9) φ(p) = p-1 [See here for details.]
(10) gp-1 ≡ gφ(p) ≡ 1 (mod p) [See Euler's Theorem]
(11) So p divides gp-1-1 → p divides h2 - 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 ≡ (gi)(p-1)/2 ≡ (g(p-1)/2)i ≡ hi ≡ (-1)i (mod p)
(16) Now from Lemma 3 above:
(17) Since a ≡ gi (mod p), we also have:
(18) Finally, since a(p-1)/2 ≡ (-1)i (mod p) from#15, we have:
QED
Saturday, February 11, 2006
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 Un [See here for a definition of Un]
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
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 Un [See here for a definition of Un]
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
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. Up: Set of units modulo p.
x ∈ Up 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 ∈ Up
Definition 2. Primitive Root Modulo p
x is a primitive root for a set S if for any y ∈ S, y ≡ xi (mod p) where i ≥ 1.
Example: 2 is a primitive root for U3
By Definition 1, U3 = { 1, 2 } since (1)(1) ≡ 1 (mod p) and (2)(2) ≡ 1 (mod p).
But then:
1 ≡ 22 (mod p)
2 ≡ 21 (mod p)
Definition 3: Cyclic set
A set is cyclic if there exists at least one element that is a primitive root.
Example: U3 is cyclic since it has a primitive root of 2.
Definition 4: Order of an element of Up
The order of x ∈ Up is the least element i such that xi ≡ 1 (mod p).
Example:
1 has an order of 1 in U3 [See Definition 2 example for details]
2 has an order of 2 in U3
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 Up divides p-1.
(1) Let a be an element of Up
(2) ap-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, ap-1 ≡ aqd + r ≡ aqd * ar [See here if you need a review of exponents]
(8) Now, since aqd ≡ (ad)q, we have:
aqd ≡ 1 (mod p)
(9) Combining (#8) with (#7) gives us:
ap-1 ≡ (1)*ar ≡ ar
(10) But ap-1 ≡ 1 (mod p) so ar ≡ 1 (mod p)
(11) And this is a contradiction since r is less than d but d is the lowest value where ad ≡ 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 ∈ Up.
(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 Up
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 Sd = the set of elements a in S where gcd(a,n) = n/d.
For example, let's consider n=8.
S2 = elements a where gcd(a,8) = 8/2 = 4 = { 4 }
S4 = elements a where gcd(a,8) = 8/4 = 2 = { 2 }
S8 = elements a where gcd(a,8) = 8/8 = 1 = { 1, 3, 5, 7}
Another example, let's consider n = 12
S2 = elements a where gcd(a,12) = 12/2 = 6 = { 6 }
S3 = elements a where gcd(a,12) = 12/3 = 4 = {4, 8}
S4 = elements a where gcd(a,12) = 12/4 = 3 = {3, 9}
S12 = elements a where gcd(a,12) = 12/12 = 1 = { 1, 5, 11}
(3) We note that the total # of all Sd = 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 ∈ Sc
(e) We also note that each element is only in 1 Sd since d = n/gcd(a,n)
(4) Let a' = (ad)/n for any integer a in Sd
(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 Sd 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 Sd = φ(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 Up and order(a)=d, then a1, a2, ..., ad 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 a1
If k=2, then we are done since we have 2 distinct elements a1 and a2.
(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
au ≡ av (mod p)
We can assume that u,v are less than k since ak ≡ 1 (mod p) and order(a)=k implies that no other ai = 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) at*av ≡ ak ≡ 1 (mod p)
(8) But since au ≡ av (mod p), then we have:
at*au ≡ at+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 xi - hi
(1) Case i = 1, 2, 3
x - h divides x1 - h1
x2 - h2 = (x + h)(x - h)
x3 - h3 = (x - h)(x2 + h2 + hx)
(2) Assume that x-h divides up to some value xn - hn such that x ≥ 3.
(3) hxn - hnx = hx(xn-1 - hn-1)
(4) Now x-h divides xn-1 - an-1 by our assumption in #2.
(5) So x-h divides hxn - hnx
(6) Now xn+1 - hn+1 = (xn + hn)(x - h) + hxn - hnx.
(7) Since x-h divides hxn - hnx, using (#6), we find that it must also divide xn+1 - hn+1.
(8) So, we apply the principle of induction and we are done.
QED
Lemma 7: Lagrange's Theorem
Let anxn + an-1xn-1 + ... + a1x + a0 ≡ 0 (mod p) where ai 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 a0 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 an-1xn-1 + ... + a1x1 + a0 ≡ 0 (mod p), there are at most n-1 solutions.
(3) Let f(x) = anxn + ... + a1x + a0
(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 x0 - h0 = 0.
(6) From Lemma 6, we know that x - h divides xi - hi
(7) So for each i in (#5), we have:
xi - hi = (x - h)(xi-1 + hxi-2 + ... + hi-2x + hi-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 ai.
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 Up with order(a) = d, then there exists b,i such that a ≡ bi (mod p) and 1 ≤ i ≤ d and gcd(i,d)=1.
(1) By Lemma 5 above, the set of elements in Up with order=d consist of b1, b2, ..., bd.
(2) But we note that all elements of order=d solve the equation xd - 1 ≡ 0 (mod p) [By the definition of Order]
(3) From Lemma 7 above, we know that there are at most d solutions to xd - 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 ≡ bi (mod p).
(5) Let j = gcd(i,d)
(6) ad/j ≡ b(id/j) ≡ (bd)i/j ≡ 1i/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 a1, a2, ... ad are distinct mod p. [See Lemma 5]
(4) Each value ai in (#3) solves the polynomial ad ≡ 1 (mod p) since:
(ai)d ≡ adi ≡ (ad)i ≡ 1 (mod p) [By the definition of order, see above]
(5) Now, ad - 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 ≡ bi (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 bi 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 Up has φ(d) elements of order d for each d that divides p-1.
(1) Let w(d) = the number of elements in Up 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 Up. [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 Up 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 Up [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 a1, a2, ... ap-1 are distinct. [By Lemma 5 above]
(5) So, by definition, a is a primitive root for Up and Up is cyclic [See Definition 3 and Definition 4 above]
QED
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. Up: Set of units modulo p.
x ∈ Up 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 ∈ Up
Definition 2. Primitive Root Modulo p
x is a primitive root for a set S if for any y ∈ S, y ≡ xi (mod p) where i ≥ 1.
Example: 2 is a primitive root for U3
By Definition 1, U3 = { 1, 2 } since (1)(1) ≡ 1 (mod p) and (2)(2) ≡ 1 (mod p).
But then:
1 ≡ 22 (mod p)
2 ≡ 21 (mod p)
Definition 3: Cyclic set
A set is cyclic if there exists at least one element that is a primitive root.
Example: U3 is cyclic since it has a primitive root of 2.
Definition 4: Order of an element of Up
The order of x ∈ Up is the least element i such that xi ≡ 1 (mod p).
Example:
1 has an order of 1 in U3 [See Definition 2 example for details]
2 has an order of 2 in U3
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 Up divides p-1.
(1) Let a be an element of Up
(2) ap-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, ap-1 ≡ aqd + r ≡ aqd * ar [See here if you need a review of exponents]
(8) Now, since aqd ≡ (ad)q, we have:
aqd ≡ 1 (mod p)
(9) Combining (#8) with (#7) gives us:
ap-1 ≡ (1)*ar ≡ ar
(10) But ap-1 ≡ 1 (mod p) so ar ≡ 1 (mod p)
(11) And this is a contradiction since r is less than d but d is the lowest value where ad ≡ 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 ∈ Up.
(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 Up
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 Sd = the set of elements a in S where gcd(a,n) = n/d.
For example, let's consider n=8.
S2 = elements a where gcd(a,8) = 8/2 = 4 = { 4 }
S4 = elements a where gcd(a,8) = 8/4 = 2 = { 2 }
S8 = elements a where gcd(a,8) = 8/8 = 1 = { 1, 3, 5, 7}
Another example, let's consider n = 12
S2 = elements a where gcd(a,12) = 12/2 = 6 = { 6 }
S3 = elements a where gcd(a,12) = 12/3 = 4 = {4, 8}
S4 = elements a where gcd(a,12) = 12/4 = 3 = {3, 9}
S12 = elements a where gcd(a,12) = 12/12 = 1 = { 1, 5, 11}
(3) We note that the total # of all Sd = 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 ∈ Sc
(e) We also note that each element is only in 1 Sd since d = n/gcd(a,n)
(4) Let a' = (ad)/n for any integer a in Sd
(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 Sd 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 Sd = φ(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 Up and order(a)=d, then a1, a2, ..., ad 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 a1
If k=2, then we are done since we have 2 distinct elements a1 and a2.
(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
au ≡ av (mod p)
We can assume that u,v are less than k since ak ≡ 1 (mod p) and order(a)=k implies that no other ai = 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) at*av ≡ ak ≡ 1 (mod p)
(8) But since au ≡ av (mod p), then we have:
at*au ≡ at+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 xi - hi
(1) Case i = 1, 2, 3
x - h divides x1 - h1
x2 - h2 = (x + h)(x - h)
x3 - h3 = (x - h)(x2 + h2 + hx)
(2) Assume that x-h divides up to some value xn - hn such that x ≥ 3.
(3) hxn - hnx = hx(xn-1 - hn-1)
(4) Now x-h divides xn-1 - an-1 by our assumption in #2.
(5) So x-h divides hxn - hnx
(6) Now xn+1 - hn+1 = (xn + hn)(x - h) + hxn - hnx.
(7) Since x-h divides hxn - hnx, using (#6), we find that it must also divide xn+1 - hn+1.
(8) So, we apply the principle of induction and we are done.
QED
Lemma 7: Lagrange's Theorem
Let anxn + an-1xn-1 + ... + a1x + a0 ≡ 0 (mod p) where ai 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 a0 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 an-1xn-1 + ... + a1x1 + a0 ≡ 0 (mod p), there are at most n-1 solutions.
(3) Let f(x) = anxn + ... + a1x + a0
(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 x0 - h0 = 0.
(6) From Lemma 6, we know that x - h divides xi - hi
(7) So for each i in (#5), we have:
xi - hi = (x - h)(xi-1 + hxi-2 + ... + hi-2x + hi-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 ai.
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 Up with order(a) = d, then there exists b,i such that a ≡ bi (mod p) and 1 ≤ i ≤ d and gcd(i,d)=1.
(1) By Lemma 5 above, the set of elements in Up with order=d consist of b1, b2, ..., bd.
(2) But we note that all elements of order=d solve the equation xd - 1 ≡ 0 (mod p) [By the definition of Order]
(3) From Lemma 7 above, we know that there are at most d solutions to xd - 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 ≡ bi (mod p).
(5) Let j = gcd(i,d)
(6) ad/j ≡ b(id/j) ≡ (bd)i/j ≡ 1i/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 a1, a2, ... ad are distinct mod p. [See Lemma 5]
(4) Each value ai in (#3) solves the polynomial ad ≡ 1 (mod p) since:
(ai)d ≡ adi ≡ (ad)i ≡ 1 (mod p) [By the definition of order, see above]
(5) Now, ad - 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 ≡ bi (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 bi 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 Up has φ(d) elements of order d for each d that divides p-1.
(1) Let w(d) = the number of elements in Up 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 Up. [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 Up 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 Up [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 a1, a2, ... ap-1 are distinct. [By Lemma 5 above]
(5) So, by definition, a is a primitive root for Up and Up is cyclic [See Definition 3 and Definition 4 above]
QED
Subscribe to:
Posts (Atom)
