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: Q_n: the set of quadratic residues

That is, these are the integers a mod n where a ≡ s² (mod n) and s ∈ U_n

NOTE: See here for a review of U_n

Examples:

Q₇ = { 1, 2, 4 }

1² ≡ 1 (mod 7) [ 1 ∈ U₇ since 1 ≡ 1 (mod 7) ]
2² ≡ 4 (mod 7) [ 4 ∈ U₇ since (4)(2) ≡ 1 (mod 7)]
4² ≡ 2 (mod 7) [ 2 ∈ U₇ since (2)(4) ≡ 1 (mod 7)]

Q₈ = { 1 }

1² ≡ 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 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

Euler's Theorem

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

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

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

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

Definition 1: Reduced Set of Residues mod n

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

Examples:

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

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

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

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

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

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

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

QED

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

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

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

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

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

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

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

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

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

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

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

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

(e) So we have a contradiction.

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

QED

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

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

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

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

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

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

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

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

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

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

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

QED

Theorem: Euler's Theorem

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

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

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

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

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

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

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

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

QED

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

Groups and Abelian Groups

Group theory is one of the most fundamental and important ideas in all of mathematics. The basic insight came out the theory of algebraic equations (which I will explore in more detail in a future blog)

Evariste Galois first defined the concept of a group in 1832. It took a long time before people generally appreciated the importance of the idea. The mathematical community eventually recognized its importance when Louisville presented a reedited version of Galois's papers in 1846.

At the time Galois and Abel enter the picture, it was well known that there exists an equation for solving the quadratic equation (ax² + bx + c=0), the cubic equation (ax³ + bx² + cx + d = 0), and the quartic equation (ax⁴ + bx³ + cx² + dx + e=0). It was suspected that no such equation existed for the quintic equation (ax⁵ + bx⁴ + cx³ + dx² + ex + f=0)

Niels Abel was the first to prove that there was no general solution for the quintic equation. His proof is one of the highpoints of mathematical theory and made use of what are today called abelian groups.

Evariste Galois submitted a paper on the solution to the quintic equation as an entry to the Paris Academy's Grand Prize in 1829. The story goes that his entry was returned by Cauchy because it had been predated by Abel's solution which was entered posthumously for the Grand Prize. Galois then generalized his paper to cover all equations quintic or higher. Due to the death of his reviewer, Galois's rewritten paper was never considered and the Grand Prize of 1830 was awarded to Abel and Jacobi.

Galois's proof is one of the most important insights in all of mathematics. He showed that proper understanding of an algebraic equation as a group of permutations determines whether an algebraic equation is solveable through a general algebraic equation. To accomplish this, Galois made use of permutations and what is today known as field theory. I will talk about these other ideas in a future blog. For now, I will focus on groups and abelian groups.

Before defining a group, we need to define four concepts: closure, associativity, identity element, inverse, commutativity.

Definition 1: Closure: When the operation is applied to any two elements of the set, the result is also an element of the set.

This is true of multiplication with integers (an integer * an integer = an integer) and multiplication with fractions ( a fraction * a fraction = a fraction).

It is not true of division with integers (many integer divisions result in a fraction) and it is not true of fractions (consider division by 0 which has an undefined result)

Definition 2: Associativity: if we have three elements, a,b,c, then the (ab)c = a(bc).

This is true of multiplication and addition with integers.

It is not true of subtraction with integers (5 - 6)-1 ≠ 5 - (6-1)

It is also not true of division since (1 / 2) / 2 ≠ 1 / (2/2)

Definition 3: Identity Element: there exists an element such that all elements applied to this element result in the original element.

This is true of addition and multiplication where 0 is the identity element in addition and 1 is the identity element in multiplication.

Definition 4: Inverse: there exists an element that when multiplied with a given element results in the identity element.

This is true of multiplication with nonzero rational numbers. 5 * (1/5) = 1

This is true of multiplication of nonzero real numbers. (1/3) * 3 = 1

This is not true of multiplication with integers. For example, there is no whole number integer x such that 2x = 1.

Definition 5: Commutativity: for any two elements, the operation has the same value regardless of the order, that is, ab=ba.

This is true of multiplication and addition:
1 + 3 = 3 + 1
2 * 3 = 3 * 2

This is not true of subtraction or division.
1 - 3 ≠ 3 - 1
1 / 3 ≠ 3 / 1

Now, we can define a group and an abelian group.

Definition 6: Group: A group is defined as a set of elements and a mathematical operation such that:
(a) Closure: For any two elements of the group, the mathematical operation results in an element of the group.

(b) Associativity: For any three elements of the group, (ab)c =a(bc).

(c) Identity Element: There exists an element i that when combined with any element a, we get: ai=a

(d) Inverse Element: For any element a in the group, there exists an element b also in the group such that ab = i (the inverse element).

Example 1: Addition on integers forms a group.

(a) Closure: integer + integer = integer

(b) Associativity: for all integers (a + b) + c = a + (b + c)

(c) Identity Element: 0: for all integers (a + 0) = a

(d) Inverse Element: For all integers a, a + (-a) = 0

Example 2: Multiplication on integers is not a group.

(a) Closure: integer * integer = integer (true)

(b) Associativity: for all integers (a * b) * c = a * (b * c) ( true)

(c) Identity Element: 1: for all integers a * 1 = a (true)

(d) Inverse Element: 2 does not have an inverse element. (false)

Example 3: Multiplication on nonzero rational numbers is a group.

(a) Closure: rational number * rational number = rational number

(b) Associativity: for all rational numbers (a * b) * c = a * (b * c)

(c) Identity Element: 1: for all rational integers: a * 1 = a

(d) Inverse Element: for any rational number a/b, there exists b/a such that (a/b)(b/a) = 1

Definition 7: Abelian Group: An abelian group is a group that also has the property of being commutative.

Example 1: the addition of integers is an abelian group.

(a) See Example 1 above to see why it is a group.

(b) Commutative: a + b = b + a

Theorem: For a given odd prime p, the multiplication of units modulo p form an abelian group.

NOTE: If you are not familiar with units modulo p, review here.

(1) Closure:

(a) Let a,b be units modulo p.

(b) By definition (see here), there exists a',b' such that (a)(a') = 1 (mod p), (b)(b') = 1 (mod p).

(c) So (a)(a')(b)(b') ≡ 1 * 1 ≡ 1 (mod p)

(d) (a)(b)(a')(b') = (a)(a')(b)(b') [Since integers are commutative]

(e) (ab)(a'b') ≡ 1 (mod p) so by definition (ab) is a unit modulo p.

(2) Associativity:

(a) Let a,b,c be units modulo p.

(b) a(bc) = (ab)c [Since integers are associative]

(c) So a(bc) ≡ (ab)c (mod p).

(3) Identity Element:

We know that 1 is a unit modulo an odd prime p.

(4) Inverse:

This is true by definition of units modulo p (see here).

(5) Commutativity:

(a) Let a,b be units modulo p.

(b) ab = bc [Since commutativity of integers with multiplication]

(c) So (ab) ≡ (bc) (mod p)

QED

References

• Lloyd Motz, Jefferson Weaver; The Story of Mathematics
• Edna E. Kramer; The Nature and Growth of Modern Mathematics
• MacTutor History of Group Theory
• Group Theory, Wikipedia
  

Èvariste Galois

Èvariste Galois was born on October 25, 1811 in La Reine, France. Galois was educated by his mother up until he was 12. There was some discussion about sending him to college when he was 10 but in the end, it was decided that he should stay at home. In 1815, his father was elected mayor of La Reine.

In 1823, enrolled in school. In 1824-1825, he received good grades, but in 1826, he was forced to repeat a grade because he failed rhetoric. In 1827, Galois enrolled in his first math class.

In 1828, just one year after his first math class, Galois took the entrance examination for the Ecole Polytechnique, the top university. He failed.

Despite the setback, Galois continued his studies of mathematics including work by Lagrange and Legendre. In April 0f 1829, he published a paper on continued fractions which included the proof that reduced quadratic equations are represented by purely periodic continued fractions.

Later that year, a scandal erupted when a vulgar poems were distributed and attributed to Galois's father. The result was more than Galois's father could stand and he committed suicide on July 2, 1829. Just a few weeks later, Galois made his second attempt at entrance to the Ecole Polytechnique. Again, he failed. In December of 1829, Galois entered Ecole Normale.

Galois submitted a paper on the theory of equations to be published. He learned that the same topic had just been covered in a posthumous article written by Niels Henrik Abel. Galois rewrote the article on the conditions whereby an equation is soluble by radicals and resubmitted it. The paper was ver well received and was submitted to Fourier who was secretary of the Paris Academy for the Grand Prize. Unfortunately, Fourier died in April of 1830 and Galois's paper got lost. In June, the Grand Prize of the Paris Academy was awarded to Niels Henrik Abel and Carl Jacobi.

In July of 1830, there was revolution in France. Charles X quickly departed and riots broke out. The head of the Ecole Normale locked the students in a the school to prevent them from joining in the unrest. In 1830, the director of the Ecole Normale wrote an editorial criticizing the students for their behavior. Galois wrote a response defending the students and criticizing the decision to do a student lock up. After writing this reply, Galois was expelled.

Galois next entered the Artillery of the National Guard. In December of 1830, King Louis Philippe disassembled the Artillery of the National Guard because he saw them as a threat to his power. 19 of the guards had been accused of conspiracy but were later released. On May 9, 1831, a great celebration was put together. Galois was there. At one point, Galois raised his glass to make a toast and held up a dagger at the same time. This was taken as a threat against the king. That same evening, Galois was arrested. He was held in prison until June 15 when he was acquitted.

On July 14, Galois was arrested for wearing the uniform of the Artillery of the National Guard which had been outlawed. While in prison, he found out that one of his math papers had been rejected and he attempted suicide. He was stopped by the other prisoners. Finally, on April 29, he was released.

By this time, he was in love with a young woman he had met. On May 30, he entered into a duel. It is believed that it was over the young woman. During the fight, he was severely wounded and died on May 31, 1832 at the age of 20.

Galois's papers were collected and sent out. Eventually, they made their way to Joseph Liouville who was deeply impressed. Liouville presented them to the French Academy in September 1843. These papers were published in 1846 and form the basis of what is today known as Galois Theory.

Today, Galois is considered to be one of the most original and talented mathematicians of all time and Galois Theory is one of the great gems of modern mathematics.

References

• MacTutor Biography of Galois
• Galois Archives
  

Niels Henrik Abel

Niels Henrik Abel was born on August 5, 1802 in Frindoe, Norway. His father was a vicar in the village of Gjerstad. His father was active politically and was part of the movement that led to Norway's separation from Denmark in 1814.

When Niels was 13 years old, he left home to attend the Cathedral School in Christiania. The school was set up in the new ideals of the time. Instead of corporal punishment, in theory, teachers appealed to a student's sense of honor and decency. Unfortunately, these ideals were not deep in practice. The math teacher at the school would have students copy math problems from the chalkboard and then he would discipline any student who did not learn the lesson. In November, 1817, this math teacher beat a student so badly that the student died. After a protests from the students, the teacher was fired.

It was at this time that a new math teacher came to the school: Bernt Michael Homboe. He had a great love for mathematics that went beyond the standard mathematical education of the day in Norway. He assigned students independent projects. He was very impressed by the abilities of young Niels Abel and helped him to study advanced mathematical topics.

Niels began to greatly excel in mathematics. Despite this, many of the school's teachers were distressed by what was perceived as an overfocus on math. At this time, classical languages were considered the paradigm of a solid education. Abel would regularly visit the public library to study the works of Newton, Euler, Gauss, and Lagrange.

At the time, the University of Christiania offered major only in theology, medicine, or law. There was no track for mathematics. For this reason, Abel studied mathematics on his own. It was very clear that in order to continue his studies, he needed to go abroad. Owing mostly to a lack of funds, Abel stayed at the University of Christiania for 4 years.

In 1823, Abel moved to Denmark where he was able to meet the leading Nordic mathematician of the day, Ferdinand Degen. He lived with his aunt and her husband in Christianshavn. In his private studies, he made progress on number theory and elliptic equations. He also met his future fiancee Christine Kemp.

Abel's first proof was about the impossibility of finding a solution to the quintic equation which he published in 1824 when he was 22 years old. He translated the article to French and he condensed the proof to 6 pages. The resulting article was very difficult to read and was largely ignored by the leading mathematicians.

In 1824, he got a government grant to study mathematics abroad for 2 years. It was during these travels that he met an engineer named Leopold Crelle. In 1826, Crelle launched his soon-to-be-famous math magazine, Crelle's Journal. It was here that Abel would publish most of his work.

It was in Crelle's Journal, that Abel published an expanded version of his proof of the impossibility of solving the general quintic equation, a treatise on the binomial series, and six other submissions.

In July of 1826, Abel headed to Paris. His goal was to impress the very well established Paris Academy. He had worked hard to create a treatise on elliptic integrals. Known today as the Paris Treatise, this is a major mathematical breakthrough. In it, he establishes research areas that are still continuing today and he presented a generality of results that went beyond the mathematics of the day. He submitted this treatise to the Paris Academy in October of 1826. He never heard back. By the end of 1826, he headed back to Norway.

Once back, despite a lack of funds, Abel continued to make great advances in mathematics. He submitted a constant barrage of articles to Crelle's which was not able to publish them as quickly as Abel wrote them up.

In the Autumn of 1828, while Abel was making plans for his marriage, he became very sick and died. He was 26. A few weeks after he died, a letter from Crelle arrived offering Abel an important post in Berlin.

In 1841, the Paris Treatise was published in the Paris Academy's Journal.

References

• MacTutor Biography
• Biography from the Abel Prize Web Site
  

Quadratic Reciprocity: Gauss's Lemma for Quadratic Residues

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.

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

Definition 1: Congruence Class (mod n)

The set of all numbers that are congruent to each other modulo a value n. This congruence class is represented in brackets such as [0].

NOTE: If you are not familiar with the concept of congruence or modulo, you can review modular arithmetic here.

If we consider n = 3, then we see that:
[1] = { ... ,-2, 1, 4, 7, ... }

since:

-2 ≡ 4 ≡ 7 ≡ 1 (mod 3).

Definition 2: Unit (mod p)

A congruence class [a] is a unit mod p if there exists another congruence class [b] such that ab ≡1 (mod p).

Here are some examples:

1 is a unit mod 8
3 is a unit mod 8 since (3)(3) ≡ 1 (mod 8)
5 is a unit mod 8 since (5)(5) ≡ 1 (mod 8)
7 is a unit mod 8 since (7)(7) ≡ 1 (mod 8)

Lemma 1: Let p be an odd prime. Let P be the set { 1, 2, ... (p-1)/2 }. Let x,y be elements of P.
Then: x ≠ y → x ± y is not congruent to 0.

(1) Assume that x is less than y (otherwise, we can use the same arguments on y)

(2) Case I: x + y

3 ≤ x + y ≤ (p-1)/2 + (p-1)/2 -1 = (p-1)/2 + (p-1-2)/2 = (2p -4)/2 = p-2.

(3) Case II: x-y

-1 ≥ x-y ≥ 1 - (p-1)/2 = (2 - p + 1)/2 = (-p + 3)/2 = -(p-3)/2

(4) Case III: y-x

1 ≤ y - x ≤ (p-1)/2 - 1 = (p-1-2)/2 = (p-3)/2

QED

Lemma 2: Let p be a prime, let a be an integer such that gcd(a,p)=1. Let P be the set { 1, 2, ... (p-1)/2 }. Then:
x ∈ P, y ∈ P, ax ≡ ± ay → x=y

(1) Assume that ax ≡ ± ay (mod p) and x ≠ y.

(2) ax ± ay ≡ 0 (mod p) [See here for a review of modular arithmetic if needed]

(3) So, p divides a(x ± y)

(4) But p doesn't divide a since gcd(a,p) = 1

(5) So, p divides x ± y [By Euclid's Lemma]

(6) So, x ± y ≡ 0 (mod p)

(7) But x ± y is not congruent to 0 (mod p) from Lemma 1 above.

(8) So we have a contradiction and we reject (#1)

QED

Corollary 2.1: If p is an odd prime and P = { 1, 2, ... (p-1)/2 } and gcd(a,p)=1, then there exists ε_i where aP = { (ε₁₎, (ε₂)(2), ... (ε_(p-1)/2)[(p-1)/2] } and each ε_i = +1 or -1.

(1) We know that each element of aP must be in { ±1, ±2, ... ±(p-1)/2 } since:

(a) Let b be any element of P.

(b) We know that ab must fit into one of the following congruence classes [± 1], [± 2], ... [ ±(p-1)/2 ] since ab (mod p) must be between 0 and p-1.

(c) But this means that either it is between 0 and (p-1)/2 or it is between (p-1)/2 + 1 and p - 1.

(d) If it is between 0 and (p-1)/2 then we are done.

(e) If it is between (p-1)/2 + 1 and p-1, then ab (mod p) is between -(p-1)/2 and -1 since p-1 ≡ -1 (mod p) and since [(p-1)/2 + 1] ≡ -(p-1)/2 (Consider that (p-1)/2 + 1 + (p-1)/2 = (p-1+2 +p - 1)/2 = 2p/2 = p.)

(f) But then either way ab is in { ± 1, ± 2, ... ± (p-1)/2 }

(2) We know that aP = { ±1, ±2, ... ±(p-1)/2 } since:

(a) Let's suppose we have b,c such that b,c ∈ P and b ≠ c.

(b) Then, we know that that ab is not congruent to ac from Lemma 2 since it if they were congruent then they must be the same which contradicts our assumption.

QED

Lemma 3: if p is an odd prime and a is a unit mod p, then a^(p-1)/2 ≡ (∏ε_i) (mod p) where ε_i is derived from aP as in Corollary 2.1 above.

(1) We know that aP = { ± 1, ± 2, ... ±(p-1)/2 } where at each point ε_i = 1 or -1 [See corollary 2.1]

(2) (∏ε_i) ≡ [(a*1)(a*2)...(a*(p-1)/2)]/[(1)(2)...(p-1)/2] (mod p)

NOTE: We can make this assumption since multiplication in modular arithmetic is an abelian group. More details here.

(3) Now, be definition of factorial [(p-1)/2]! ≡ (1)(2)...(p-1)/2 [See here for review of factorials]

(4) Likewise (a*1)(a*2)*...*(a*[p-1]/2) ≡ a^(p-1)/2[(p-1)/2]! (mod p)

(5) Combining #2 with #3 and #4 gives us:
(∏ε_i) ≡ a^(p-1)/2[(p-1)/2]!/[(p-1)/2]! = a^(p-1)/2 (mod p)

QED

Lemma 4: Gauss's Lemma for Quadratic Residues

If p is an odd prime and gcd(q,p)=1, then:



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

(1) Let x,y be elements of P such that x ≠ y.

(2) qx is not congruent to ± qy (mod p) (from Lemma 2 above)

(3) So, we see from (2) that there are (p-1)/2 distinct congruence classes that are created from qP since for each combination, we know from (2), that there is no overlap.

(4) q^(p-1)/2 ≡ (∏ε_i) (mod p) where ε_i = 1 if (i) ∈ P and ε_i = -1 if (i) ∈ N [From Lemma 3 above]

(5) So, q^(p-1)/2 ≡ (-1)^μ (mod p) where μ = the number of elements in qP ∩ N since:

(a) (∏ε_i) = (-1)^μ where μ is the number of times ε_i = -1. [Since we can ignore all the times ε_i = 1]

(b) But this means we need to figure out the count of all elements b ∈ qP that are also in N.

(c) And this means that we are looking for the number of elements in qP ∩ N.

(6) By Euler's Criterion (see here), we know that:


(7) Combining (5) and (6) gives us our conclusion since the Legendre symbol is only = to 1 or -1.


QED

Quadratic Reciprocity: The Proof

Today, I will present a proof for the Principle of Quadratic Reciprocity:



For those not familiar with quadratic reciprocity, quadratic residues, or with the notation above, start here.

Today's proof is based on the Gareth A. Jones and J. Mary Jones Elementary Number Theory.

Theorem 1: Principle of Quadratic Reciprocity.

Given p,q are odd primes. if p or q ≡ 1 (mod 4), then p is a quadratic residue of q if and only if q is a quadratic residue of p. if both p and q ≡ 3 (mod 4), then p is a quadratic residue of q if and only q is not a quadratic residue of p and likewise, q is a quadratic residue of p if and only if p is not a quadratic residue of q.

(1) Let P be the set of integers {1, 2, ... (p-1)/2 }

(2) Let N be the set of integers -P, that is, {-1, -2, ... -(p-1)/2}

(3) Let Q be the set of integers {1, 2, ... (q-1)/2 }

(4) Now by Gauss's Lemma (see here):



where μ is the number of elements in qP ∩ N. [See here for details on qP ∩ N]

(5) Further, we can conclude (see here):



where μ + ν is the number of pairs (x,y) ∈ PxQ such that -p/2 is less than qx-py is less than q/2.

(6) From a result, I will show later, there exist values α and β such that:

μ + ν = (p-1)(q-1)/4 - (α + β).

(7) Now, it can be shown (see Lemma 2 here), that α = β

(8) With this in place, we combine (#5) with (#6) to get (see Lemma 3 here):



QED

Note: if you are unclear how (#8) is equivalent to the given, see here.