## 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
• Jean-Pierre Tignol, , World Scientific, 2001

## 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
• Gareth A. Jones, J. Mary Jones, , Springer, 2002.

## 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
• Jean-Pierre Tignol, , World Scientific, 2001

## 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