Complete Residue System

Definition 1: Complete Residue System (from Stark's Introduction to Number Theory)

A set of n integers a₁, a₂, ..., a_n is a complete residue system if every integer is congruent (mod n) to exactly one of the a_j's.

In other words, a complete residue system is a one-to-one correspondence (bijection) between a set of elements the different congruence classes modulo n.

Lemma 1:

Any set of n consecutive integers is a complete residue system modulo n.

That is for any integer i, {i+0, i+1, ..., i+n-1} is a complete residue system

Proof:

(1) 0, 1, ..., n-1 is a complete residue system modulo n.

(2) Let i be any integer.

(3) For any integer a, there exists an integer j such that:

a - i ≡ j (mod n) and j ∈ {0, 1, ..., n-1}

so that:

a ≡ j + i (mod n)

(4) Since a can be any integer, this shows that j+i is "onto" the complete residue system.

(5) To complete the proof, we have to show that j+i is also "one-to-one" with the complete residue system.

(6) Suppose that j₁ and j₂ are different integers such that:

a ≡ j₁ + i (mod n)

a ≡ j₂ + i (mod n)

(7) Then:

a - i ≡ j₁ (mod n)

a - i ≡ j₂ (mod n)

(8) But then a -i is congruent to two distinct elements of the complete residue system which is impossible.

(9) Hence, every integer i + j is a distinct congruence class.

QED

Lemma 2:

If gcd(a,n)=1, then there exists an integer c such that ac ≡ 1 (mod n)

Proof:

(1) By Bezout's Identity (see Lemma 1, here), thre exists integers c,d such that:

ac + nd = 1.

(2) Which means that:

ac - 1 = -nd

(3) And therefore:

ac ≡ 1 (mod n)

QED

Lemma 3:

If gcd(b,n)=1 and the numbers a₁, ..., a_n form a complete residue system (mod n), then for all integers c, the numbers b*a₁+c, ..., b*a_n + c also form a complete residue system (mod n).

Proof:

(1) By Lemma 2 above, since gcd(b,n)=1, there exists an integer e such that:

b*e ≡ 1 (mod n)

(2) Let a₁, ..., a_n be a complete residue system (mod n). [See Definition 1 above]

(3) Since a_i is a complete residue system, For any integers c,d it follows that there exists an integer k such that 1 ≤ k ≤ n and:

e(d - c) ≡ a_k (mod n)

(4) Multiplying both sides by b gives us:

b*e(d-c) ≡ (d-c) ≡ b*a_k (mod n)

(5) This gives us:

d ≡ b*a_k + c (mod n)

(6) Since d can take on any value, it is clear that b*a_k + c is onto the complete residue set. That is, for any residue (d), we can find an expression of the form b*a_k + c that is congruent to it.

(7) To complete the proof, we need to show that each b*a_k + c is also one-to-one with the complete residue system.

(8) Assume that there exists an integer i such that 1 ≤ i ≤ n and:

d ≡ b*a_i + c (mod n)

(9) Subtracting c from both sides gives:

d - c ≡ b*a_i (mod n)

(10) Multiplying e to both sides gives us:

e(d-c) ≡ e*b*a_i ≡ a_i (mod n)

(11) But using step #3, we have:

e(d-c) ≡ a_i ≡ a_k (mod n)

(12) This demonstrates that i = k.

(13) Thus, every integer is congruent to exactly one of the n integers b*a₁ + c, ..., b*a_n + c.

(14) So, we have shown that this is a complete residue system (mod n).

QED

References

• Harold M. Stark, An Introduction to Number Theory (MIT Press, 1978)

Field Extension

The content in today's blog, assumes that you feel comfortable with the idea of fields. For review of this concept, start here.

Definition 1: subfield

A set B is a subfield of a set A if both A,B are fields and B is a subset of A.

Definition 2: field extension

A set A is a field extension of a set B if B is a subfield of A.

Definition 3: R=F(u)

A field R = F(u) if and only if the following is true:

(i) u is a number that may or may not be part of the field F

(ii) For any numbers x ∈ R, there exists coefficients a₀, ..., a_n such that all a_i ∈ F and x = a₀uⁿ + a₁u^n-1 + ... + a_n.

The important idea behind Definittion 3 above is that F(u) is a field extension of F.

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

field automorphism

Definition 1: Bijective

A bijective map is a map f from set X to a set Y with the property that for every y in Y, there is exactly one x in X such that f(x) = y.

Definition 2: Homomorphism

A homomorphism is a map from one algebraic structure to another of the same type that preserves certain properties.

Definition 3: Isomorphism

An isomorphism is a bijective map f such that both f and its inverse f^-1 are homomorphisms.

Definition 4: Automorphism

An automorphism is an isomorphism from a mathematical object to itself.

Definition 5: Ring Homomorphism

A ring homomorphism is a mapping between two rings which preserves the operations of addition and multiplication.

If R,S are rings and f: is the mapping R → S, the the following properties hold:

(1) f(a+b) = f(a) + f(b) for all a,b ∈ R

(2) f(ab) = f(a)f(b) for all a,b ∈ R

(3) f(1) = 1

Definition 6: Field Automorphism

A field automorphism is a bijective ring homomorphism from a field to itself.

References

• "Automorphism", Wikipedia.org
  
• "Bijection", Wikipedia.org
• "Homomorphism", Wikipedia.org
  
• "Isomorphism", Wikipedia.org
• "Ring Homomorphism", Wikipedia.org
  

(a + b)p ≡ ap + bp (mod p)

Lemma 1:

if p is prime, then:

(a + b)^p ≡ a^p + b^p (mod p)

Proof:

(1) Using the Binomial Theorem (see Theorem here), we know that:



(2) Now, since p is a prime, it is clear that for each term p!/(m!)(p-m)!, p is not divisible by any term ≤ m or by any term ≤ p-m so that we have:

p!/(m!)(p-m)! = p*([(p-1)*...*p-m+1]/[m!])

(3) This shows that each of these terms is divisible by p and therefore:

[p!/(m!)(p-m)!]a^p-mb^m ≡ 0 (mod p)

(4) So that there exists an integer n such that:

(a + b)^p = a^p + np + b^p

(5) Since a^p + nb + b^p ≡ a^p + b^p (mod p), it follows that:

(a + b)^p ≡ a^p + b^p (mod p)

QED

The set of congruence classes modulo n: Z/nZ

In considering modular arithmetic (see here for review if needed), we can divide all integers into congruence classes modulo n.

Definition 1: Congruence class modulo n: [i]

Let [i] represent the set of all integers such that [i] = { ..., i-2n, i-n, i, i+n, i+2n, ... }

To make this definition even clearer, let's consider the following lemma.

Lemma 1: x ∈ [i] if and only if x ≡ i (mod n)

Proof:

(1) Assume x ≡ i (mod n)

(2) Then n divides x - i

(3) So, there exists an integer a such that an = x - i

(4) So that x = an + i

(5) Assume that x ∈ [i]

(6) Then, there exists a such that x = i + an

(7) This shows that an = x - i and further that n divides x - i.

(8) Therefore, we have x ≡ i (mod n)

QED

Lemma 2: There are only n distinct congruence classes modulo n

Proof:

(1) To prove this, I will show that for all x ∈ Z, there exists i such that:

x ≡ i (mod n)

and

0 ≤ i ≤ n-1

(2) For x ∈ Z, there exists k such that x ≡ k (mod n)

(3) We can assume that k is positive since if k is negative, k ≡ -k (mod n) since n divides k + -k.

(4) We can further assume that k ≤ n-1, since if k ≥ n, it follows that k ≡ (k-n) (mod n) since n divides (k - [k-n]) = k -k + n = n.

QED

We can now consider the set of congruence classes modulo n as the set Z/nZ.

Definition 2: set of congruence classes modulo n: Z/nZ

Z/nZ = { [0], ..., [n-1]}

Example 1: Z/3Z

Z/3Z = { [0], [1], [2] }

For purposes of showing the relationship between Z and Z/nZ, I will from this point on view Z/nZ = {0, ..., n-1}.

So that Z/3Z will also be represented as {0, 1, 2}

Lemma 3: Z/nZ is a commutative ring

Proof:

(1) Z/nZ has commutative rule for addition

For all a,b ∈ Z/nZ: a+b ≡ b + a (mod n)

(2) Z/nZ has associative rule for addition

For all a,b,c ∈ Z/nZ: (a + b) + c ≡ a + (b + c) (mod n)

(3) Z/nZ has additive identity rule

0 ∈ Z/nZ and for all a ∈ Z/nZ: a ≡ a + 0 (mod n)

(4) Z/nZ has additive inverse rule:

(a) Let a be any congruence class modulo n such that a ∈ Z/nZ

(b) Assume a ≠ 0 for if a = 0, then a + a ≡ 0 (mod n) and a is its own additive inverse.

(c) Let b = n - a

(d) b ∈ Z/nZ since 1 ≤ b ≤ n-1

(e) a + b ≡ n ≡ 0 (mod n)

(5) Z/nZ has an associative rule for multiplication:

For all a,b,c ∈ Z/nZ: (ab)c ≡ a(bc) (mod n)

(6) Z/nZ has a distributive rule:

For all a,b,c ∈ Z/nZ: a(b+c) ≡ ab + ac ≡ (b + c)a (mod n)

(7) Z/nZ has a commutative rule for multiplication

For all a,b ∈ Z/nZ: ab ≡ ba (mod n)

(8) Thus, Z/nZ is a commutative ring. [See Definition 2, here]

QED

Lemma 4: if p is a prime, then Z/pZ is a field

Proof:

(1) Z/pZ has a multiplicative identity rule.

1 ∈ Z/pZ and for all a ∈ Z/pZ 1*a ≡ a*1 ≡ a (mod p)

(2) Z/pZ has a multiplicative inverse rule since:

(a) Let a be any nonzero element of Z/pZ

(b) If p = 2, then a is its own inverse and a*a ≡ 1*1 ≡ 1 (mod 2).

(c) If p ≥ 3, then let b = a^p-2

(d) Then a*b ≡ a*(a^p-2) ≡ a^p-1 ≡ 1 (mod p). [See Fermat's Little Theorem, here]

(3) Thus, Z/pZ is a field. [See Definition 3, here]

QED

Lemma 5:

if p is prime and ab ≡ 0 (mod p), then a ≡ 0 (mod p) or b ≡ 0 (mod p)

Proof:

(1) Assume a is not ≡ 0 (mod p)

(2) Since ab ≡ 0 (mod p), it follows that p divides ab.

(3) If a is not ≡ 0 (mod p), then it follows that p does not divide a.

(4) So, using Euclid's Lemma (see Lemma 2, here), it follows that p divides b.

(5) And equivalently, b ≡ 0 (mod p)

QED

References

• Gareth A. Jones, J. Mary Jones, Elementary Number Theory, Springer, 2002.
  

monic polynomials

In today's blog, I will present a property of monic polynomials. A monic polynomial is a polynomial of degree n where the coefficient of xⁿ is 1.

Lemma 1: Division by a monic polynomial

If f,g,h are polynomials such that f = g/h and g,h are monic. Then f is also monic.

Proof:

(1) Let g(x) = a₀x^r + a₁x^r-1 + ... + a_r-1x + a_r

(2) Let h(x) = b₀x^s + b₁x^s-1 + ... + b_s-1x + b_s

(3) Let f(x) = c₀x^t + c₁x^t-1 + ... + c_t-1x + c_t

(4) Since g(x) = h(x)*f(x), it follows that:

r = s + t

and

a₀ = b₀*c₀

(5) Since a₀ = b₀*c₀, it follows that:

c₀ = a₀/b₀

(5) Since g(x) is monic and h(x) is monic, it follows that a₀ = 1 and b₀= 1.

(6) It therefore follows that f(x) is monic since:

c₀ = a₀/b₀ = 1/1 = 1

QED

Roots of Polynomials

The following proof is taken from Jean-Pierre Tignol's Galois' Theory of Algebraic Equations.

Theorem: An element a ∈ F is a root of polynomial P ∈ F[X] if and only if (X-a) divides P.

Proof:

(1) deg(X - a) =1 [See Definition 4, here for definition of degree]

(2) Therefore, the remainder R of the division of P by (X - a) is a constant polynomial. [See Theorem, here]

(3) So, from the Division Algorithm for Polynomials (see Theorem, here), there exists Q,R such that:

P = (X - a)Q + R

(4) Further:

P(a) = (a -a)Q + R = R

(5) This shows that P(a) = 0 if and only if R = 0. That is, P(a) = 0 if and and only if P is divisible by (X - a).

QED

References

• Jean-Pierre Tignol, Galois' Theory of Algebraic Equations, World Scientific, 2001

tan(π/4) = 1

Lemma: tan π/4 = 1

Proof:

(1) Using definition:

tan(π/4) = sin(π/4)/cos(π/4)

(2) Using the triangle definition of sin and cosine (see here), we know that:

sin (x) = cos (π/2 - x)

(3) This then gives us that:

sin (π/4) = cos(π/2 - π/4) = cos(2π/4 - π/4) = cos(π/4)

(4) So that:

tan(π/4) = cos(π/4)/cos(π/4) = 1

QED

cot 2x = (1/2) [cot x - tan x]

Lemma 1: cot 2x = (1/2)[cot x - tan x]

Proof:

(1) cot 2x = 1/tan(2x) = cos(2x)/sin(2x) [See here for definition of tan]

(2) cos(2x) = cos²(x) - sin²(x) [See Lemma 3, here]

(3) sin(2x) = 2(sin x)(cos x) [See Lemma 2, here]

(4) cos(2x)/sin(2x) = [cos²(x) - sin²(x)]/2(sin x)(cos x) =

= (1/2)[cos(x)/sin(x) - sin(x)/cos(x)] = (1/2)[cot(x) - tan(x)]

QED

Lemma 2: tan(-b) = -tan b

Proof:

(1) tan(-b) = sin(-b)/cos(-b) [See here for definition of tangent]

(2) sin(-b) = -sin b [See Property 4, here]

(3) cos(-b) = cos b [See Property 9, here]

(4) So, tan(-b) = (-sin b)/(cos b) = (-1)(sin b)/(cos b) = (-1)tan b = -tan b.

QED

Lemma 3: tan(a + b) = [tan a + tan b]/[1 - (tan a)(tan b)]

Proof:

(1) tan(a + b) = sin(a + b)/cos(a + b) [See here for definition of tangent]

(2) sin(a + b) = (sin a)(cos b) + (cos a)(sin b) [See Theorem 1, here]

(3) cos(a + b) = (cos a)(cos b) - (sin a)(sin b) [See Theorem 2, here]

(4) So that:

sin(a + b)/cos(a + b) = [(sin a)(cos b) + (cos a)(sin b)]/[(cos a)(cos b) - (sin a)(sin b)] =

(sin a)(cos b)/[(cos a)(cos b) - (sin a)(sin b)] + (cos a)(sin b)/[(cos a)(cos b) - (sin a)(sin b)]

(5) Multiplying both sides of the fractions by 1/(cos a)(cos b) gives us:

(tan a)/[1 - (tan a)(tan b)] + (tan b)/[1 - (tan a)(tan b)] =

= [tan a + tan b ]/[1 - (tan a)(tan b)]

QED

Corollary 3.1: tan(a - b) = [tan a - tan b]/[1 + (tan a)(tan b)]

Proof:

(1) tan(a - b) = tan (a + (-b)) = [tan a + tan (-b)]/[1 - (tan a)(tan -b)]

(2) Using Theorem 2 above, we have:

[tan a + tan (-b)]/[1 - (tan a)(tan -b)] = [tan a - tan b]/[1 + (tan a)(tan b)]

QED

Lemma 4: tan (2x) = (2 tan x)/(1 - tan² x)

Proof:

(1) tan(2x) = tan(x + x)

(2) Using Theorem 3 above:

tan(x + x) = [tan x + tan x]/[1 - (tan x)(tan x)] =

= (2 tan x)/(1 - tan² x)

QED

Lemma 5: 2 cos mx cos nx = cos(m + n)x + cos(m -n)x

Proof:

(1) Using cos(a + b) = cos(a)cos(b) - sin(a)sin(b) [See Theorem 2, here]

cos(m+n)x = cos(mx + nx) = cos(mx)cos(nx) - sin(mx)sin(nx)

cos(m-n)x = cos(mx - nx) = cos(mx)cos(-nx) - sin(mx)sin(-nx)

(2) Using cos(-x) = cos(x) [see Property 9, here] and sin(-x) = -sin(x) [see Property 4, here], we have:

cos(m - n)x = cos(mx)cos(nx) + sin(mx)sin(nx)

(3) So:

cos(m+n)x + cos(m-n)x = cos(mx)cos(nx) - sin(mx)sin(nx) + cos(mx)cos(nx) + sin(mx)sin(nx) =
2 cos(mx)cos(nx)

QED

Equation for a circle

Postulate 1: The distance d between two points (x1,x2) and (y1,y2)

d = √(x2 - x1)² + (y2 - y1)²

This postulate assumes all the postulates from Euclid but that works fine for the standard Cartesian coordinates.

Definition 1: A circle

A circle is the set of points equidistant from a given point. This given point is called the center. The distance from the center to any point in the set of points is called the radius.

Theorem 1: Equation of a circle

For any given circle with center at (centerX, centerY) and radius r, the equation is:

(x - centerX)² + (y - centerY)² = r²

Proof:

(1) By Definition 1 above and Postulate 1 above, we have:

r = √(x - centerX)² + (y - centerY)²

(2) Squaring both sides gives us:

r² = (x - centerX)² + (y - centerY)²

QED

Geometric Interpretation of Roots of Unity

The nth roots of unity can be thought of as n points evenly dividing up a circle.

Wolfram's MathWorld web site has a wonderful graphic that demonstrates this:



Here's the reason that it's true:

Theorem: The N-th Roots of Unity correspond to n points evenly dividing up a circle

Proof:

(1) The number of radians in a circle is 2π [See here for review of radians, if needed]

(2) The equation for roots of unity is (see Corollary 1.1, here):



where 0 ≤ k ≤ n-1.

(3) So each root of unity is:

cos[ (2kπ)/n] + isin[(2kπ)/n]

where 0 ≤ k ≤ n-1

(4) Which is the same as:

cos[(k/n)2π] + isin[(k/n)2π]

where 0 ≤ k ≤ n -1

(5) Now, complex values can be graphed on the Cartesian coordinate system on x + iy [this is called the complex plane].

(6) Each of the roots above maps to a point on the circumference of a unit circle since:

(a) The equation for a unit circle at (0,0) is [See Theorem 1, here]:

x² + y² = 1

(b) Since we are mapping cos[(k/n)2π] + isin[(k/n)2π] to x + iy, this gives us:

x = cos[(k/n)2π]

y = sin[(k/n)2π]

(c) From a previous result (see Corollary 2, here), we have:

cos²[(k/n)2π] + sin²[(k/n)2π] = 1

(d) So, applying step #6b above gives us:

x² + y² = 1

(7) So, all we have left to prove is that each of these n points is equidistant from the adjacent points on the circle.

(8) Clearly, we have points at based on the following n values:

(0/n)2π, (1/n)2π, (2/n)2π, ..., [(n-1)/n]2π

where

y = cos[(k/n)2π]

x = sin[(k/n)2π]

(9) Now, if we use a unit circle, it is clear that each of these points is equidistant from each other since:

Consider a circle which has the radius r = 1.

It is clear that plotting lines at (0/n)2π, (1/n)2π. ... ([n-1]/n)2π divides up the total circle (2π radians) into n equal portions.

Using a unit circle, it is clear that x=[cos(k/n)2π] and y = [sin(k/n)2π] are the places of intersection when the circle is evenly divided since:

sin θ = y/r = y

cos θ = x/r = x



In other words, each y=cos[(k/n)2π] and x=sin[(k/n)2π] is a point at the place where the (k/n)th part of the circle sweeps out against the circumference of the circle.

Since the length of the circumference is πD=(2r)πr = 2(1)π, [see Corollary 1, here], this means that the length of each subtended arc is (k/n)*2π.

This results in the patterns above depending upon the value of n.

QED

For example, if we graph the third roots of unity. Then, we have:

lines sweeping out at:

0, (1/3)2π, and (2/3)2π.

which results in the following graph:



References

• Rowland, Todd and Weisstein, Eric W. "Root of Unity." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/RootofUnity.html
• "Complex Plane", Wikipedia.com
• "Roots of Unity", Wikipedia.com
  

Elementary Lemmas

Lemma 1:

If:

gcd(e,f)=1
e divides k
f divides k

Then:

ef divides k

Proof:

(1) Assume that ef does not divide k.

(2) Then, there must exist a prime p and a power c such that p^c divides ef but p^c does not divide k.

(3) Since gcd(e,f)=1, it follows that p^c must entirely divide e or p^c must entirely divide f.

(4) Let's assume that p^c divides e. [We can make a parallel argument if p^c divides f.

(5) But then we have a contradiction since e divides k implies that p^c divides k.

(6) So we reject our assumption in step #1.

QED

Lemma 2:

If a ≥ b and b ≥ a, then a = b

Proof:

(1) a ≥ b

(2) So it follows that a = b or a is greater than b.

(3) But a is not greater than b since b ≥ a.

(4) So then it follows that a = b.

QED

Corollary 2.1:

If a,b are positive and a divides b and b divides a, then a = b

Proof:

(1) If a divides b, then b ≥ a.

(2) If b divides a, then a ≥ b

(3) Since a ≥ b and b ≥ a, we can use Lemma 2 above to conclude that a= b.

QED

Lemma 3:

if gcd(e,f)=1 and e divides af

then:

e divides a

Proof:

(1) Assume that e does not divide a.

(2) Then, there exists a prime p such that p^c divides e but does not divide a.

(3) Since p^c divides e, it follows that p^c must divide af.

(4) Using Euclid's Lemma (see Lemma 2, here), we know that if p divides af, then it divides a or it divides f. But it cannot divide f since gcd(e,f)=1 so it divides a.

(5) But then p^c must divide a since no p can divide f. This contradicts step #2.

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

QED

Cyclotomic Equation

Lemma 1:

Let ζ = the n-th root of unity where ζ ≠ 1

Then:

1 + ζ + ζ² + ... + ζ^n-1 = 0

Proof:

(1) Since ζⁿ = 1, we have:

1 + ζ + ζ² + ... + ζ^n-1 = ζ(1 + ζ + ζ² + ... + ζ^n-1)

(2) Now ζ ≠ 0 [since 0ⁿ ≠ 1] and ζ ≠ 1

(3) Let x = 1 + ζ + ζ² + ... + ζ^n-1

(4) Assume that x ≠ 0

(5) So, x = ζx [from step #1]

(6) Since we assume x ≠ 0, we can divide both sides by x to get 1 = ζ

(7) But this contradicts step #2 so we reject our assumption in step #3 and conclude that:

1 + ζ + ζ² + ... + ζ^n-1 =0

QED

Corollary 1.1:

if ζ is a primitive n-th root of unity, then:

a = (-a) ζ + (-a)ζ² + ... + (-a)ζ^n-1

Proof:

(1) From Lemma 1 above:

-1 = ζ + ζ² + ... + ζ^n-1

(2) So, a = (-a)(ζ + ζ² + ... + ζ^n-1 ) = (-a) ζ + (-a)ζ² + ... + (-a)ζ^n-1

QED

Lemma 2:

if i ≡ j (mod q)

and

ζ is a primitive qth root of unity

Then:

ζⁱ = ζ^j

Proof:

(1) i ≡ j (mod q) implies there exists integers r,s such that:

i +r*q = j + s*q

(2) So, it follows that:

ζⁱ*(ζ^q)^r = ζ^j*(ζ^q)^s

(3) Since ζ^q = 1, we have:

ζⁱ*1^r = ζ^j*1^s

which means that:

ζⁱ = ζ^j

QED