Monday, October 20, 2008

Complete Residue System

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

A set of n integers a1, a2, ..., an is a complete residue system if every integer is congruent (mod n) to exactly one of the aj'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 j1 and j2 are different integers such that:

a ≡ j1 + i (mod n)

a ≡ j2 + i (mod n)

(7) Then:

a - i ≡ j1 (mod n)

a - i ≡ j2 (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 a1, ..., an form a complete residue system (mod n), then for all integers c, the numbers b*a1+c, ..., b*an + 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 a1, ..., an be a complete residue system (mod n). [See Definition 1 above]

(3) Since ai 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) ≡ ak (mod n)

(4) Multiplying both sides by b gives us:

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

(5) This gives us:

d ≡ b*ak + c (mod n)

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

(7) To complete the proof, we need to show that each b*ak + 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*ai + c (mod n)

(9) Subtracting c from both sides gives:

d - c ≡ b*ai (mod n)

(10) Multiplying e to both sides gives us:

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

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

e(d-c) ≡ ai ≡ ak (mod n)

(12) This demonstrates that i = k.

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

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

QED

References

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 a0, ..., an such that all ai ∈ F and x = a0un + a1un-1 + ... + an.

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

References

Saturday, March 01, 2008

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

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

Lemma 1:

if p is prime, then:

(a + b)
p ≡ ap + bp (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)!]ap-mbm ≡ 0 (mod p)

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

(a + b)p = ap + np + bp

(5) Since ap + nb + bp ≡ ap + bp (mod p), it follows that:

(a + b)p ≡ ap + bp (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 = ap-2

(d) Then a*b ≡ a*(ap-2) ≡ ap-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

Monday, January 28, 2008

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 xn 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) = a0xr + a1xr-1 + ... + ar-1x + ar

(2) Let h(x) = b0xs + b1xs-1 + ... + bs-1x + bs

(3) Let f(x) = c0xt + c1xt-1 + ... + ct-1x + ct

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

r = s + t

and

a0 = b0*c0

(5) Since a0 = b0*c0, it follows that:

c0 = a0/b0

(5) Since g(x) is monic and h(x) is monic, it follows that a0 = 1 and b0= 1.

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

c0 = a0/b0 = 1/1 = 1

QED

Sunday, January 27, 2008

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

Friday, January 25, 2008

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

Thursday, January 24, 2008

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) = cos2(x) - sin2(x) [See Lemma 3, here]

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

(4) cos(2x)/sin(2x) = [cos2(x) - sin2(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 - tan2 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 - tan2 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

Tuesday, January 08, 2008

Equation for a circle

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

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

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)2 + (y - centerY)2 = r2

Proof:

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

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

(2) Squaring both sides gives us:

r2 = (x - centerX)2 + (y - centerY)2

QED

Monday, January 07, 2008

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 [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]:

x2 + y2 = 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:

cos2[(k/n)2π] + sin2[(k/n)2π] = 1

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

x2 + y2 = 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

Saturday, January 05, 2008

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 pc divides ef but pc does not divide k.

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

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

(5) But then we have a contradiction since e divides k implies that pc 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 pc divides e but does not divide a.

(3) Since pc divides e, it follows that pc 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 pc must divide a since no p can divide f. This contradicts step #2.

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

QED

Wednesday, January 02, 2008

Cyclotomic Equation

Lemma 1:

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

Then:

1 + ζ + ζ2 + ... + ζn-1 = 0

Proof:

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

1 + ζ + ζ2 + ... + ζn-1 = ζ(1 + ζ + ζ2 + ... + ζn-1)

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

(3) Let x = 1 + ζ + ζ2 + ... + ζ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 + ζ + ζ2 + ... + ζn-1 =0

QED

Corollary 1.1:

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

a = (-a) ζ + (-a)ζ2 + ... + (-a)ζn-1

Proof:

(1) From Lemma 1 above:

-1 = ζ + ζ2 + ... + ζn-1

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

QED

Lemma 2:

if i ≡ j (mod q)

and

ζ is a primitive qth root of unity

Then:

ζi = ζ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:

ζi*(ζq)r = ζj*(ζq)s

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

ζi*1r = ζj*1s

which means that:

ζi = ζj

QED