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

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

Saturday, December 08, 2007

Irreducible Polynomials

Definition 1: Irreducible Polynomials

A polynomial P ∈ F[X] is irreducible in F[X] if deg P is greater than 0 and P is not divisible by any polynomial Q ∈ F[X] such that 0 is less than deg Q is less than deg P.

NOTE: See Definition 1, here, for definition of polynomials and Definition 4, here, for definition of deg of a polynomial.

Lemma 1:

If a polynomial D divides an irreducible polynomial P,

Then, either D is a constant or deg D = deg P.

Proof:

(1) Let P be an irreducible polynomial

(2) Let D be a polynomial that divides P.

(3) Assume that D is not a constant and that deg D is less than deg P.

(4) Then D cannot divide P [by Definition 1 above]

(5) So we have a contradiction and we must reject our assumption at step #3.

QED

Corollary 1.1: Every polynomial of degree 1 is irreducible

(1) Assume that there exists a polynomial D of degree 1 that is not irreducible.

(2) Then there exists a polynomial P that divides D where deg P is less than deg D and deg P is greater than 0.

(3) But this is impossible since deg D = 1 (either deg P = 0 or deg P ≥ 1).

(4) So we reject our assumption at step #1.

QED

Theorem 2: Euclid's Lemma for Polynomials

For polynomials S,T,U if S divides TU and S is relatively prime to T, then S divides U.

Proof:

(1) Since GCD(S,T)=1, there exists polynomials V,W such that [See Corollary 3.1, here]:

SV + TW = 1

(2) Multiplying both sides by U gives us:

S(UV) + (TU)W = U

(3) This proves that S divides U since S divides TU.

QED

Corollary 2.1: Generalized Euclid's Lemma for Polynomials

If a polynomial S divides a product of r factors and is relatively prime to the first r-1 factors, then it divides the last one.

Proof:

(1) Let T = the first r-1 factors.

(2) Let U = the last factor

(3) Then S divides TU and GCD(S,T)=1 so using Theorem 2 above, we can conclude that S divides U.

QED

Corollary 2.2: If a polynomial is divisible by pairwise relatively prime polynomials, then it is divisible by their product

Proof:

(1) Let P1, ..., Pr be relatively prime polynomials which divide a polynomial P.

(2) For r=1, P1 = P so the corollary is true.

(3) Assume that it is true up to r-1.

(4) So, then we have:

P = P1*..*Pr-1*Q

(5) By Corollary 2.1 above, since Pr divides P, it follows that Pr must divide Q.

(6) So, then it follows that P1...*...*Pr must divide P.

QED

Theorem 3: Every non constant polynomial P ∈ F[X] is a finite product:

P = cP1P2...Pn

where c ∈ Fx and P1, P2, ..., Pn are monic irreducible polynomials where this factorization is unique. Order of these polynomials is not unique and there may include repeats of the same polynomial more than once.

Proof:

(1) If P is irreducible, then P = c*P1 where c is the leading coefficient of P and P1 = c-1P is irreducible and monic. [See Definition 1 above and Theorem 2, here]

(2) If P is reducible, then it can be written as a product of two polynomials of degree less than deg P.

(3) If the two polynomials less than P are irreducible, then we are done. If not, then we can continue to break each reducible polynomial into a product of reducible polynomials and then using step #1, we break this product into the desired result.

(4) The next step is to prove that this product independent of order is unique.

(5) Assume that:

P = cP1*...*Pn = dQ1*...*Qm

where c,d ∈ Fx and P1, ..., Pn, Q1, ..., Qm are irreducible polynomials.

(6) c = d since both equal the leading coefficient of P.

(7) So, we have:

P1*...*Pn = Q1*...*Qm

(8) Using Corollary 2.1 above, we know that P1 cannot be relatively prime to all Qi

(9) So, let's assume that there exists a Qi such that GCD(P1,Qi) ≠ 1. Let's label it Q1

(10) Let D be the unique monic GCD of P1,Q1. [See Theorem 2, here]

(11) Since P1 is irreducible, then P1 = cD for some c.

(12) Since P1 is monic, then c = 1 and P1 = D.

(13) Since Q1 is monic and irreducible, we can use the same argument as in steps #11 and steps #12 to establish that Q1 = D.

(14) Therefore, it follows that Q1 = P1

(15) We can make the same argument for all n elements of Pi so that we have P2 = Q2, P3 = Q3, ..., Pn = Qn

(16) Since there must be a matched element for each Pi, it follows that n ≤ m.

(17) But we can also make the same line of argument for Qj so that we also know that m ≤ n

(18) Therefore n = m.

QED

References

Friday, December 07, 2007

Greatest Common Divisor for Polynomials

Definition 1: Divisor for Polynomials

Let P1, P2 ∈ F[X].

We say that P2 divides P1 if there exists Q ∈ F[X] such that P1 = P2Q

Definition 2: GCD for Polynomials

A greatest common divisor (GCD) of P1, P2 is a polynomial D ∈ F[X] which has the following properties:

(a) D divides P1 and P2
(b) If S is a polynomial which divides P1 and P2, then S divides D.

Definition 3: Relatively prime polynomials

Two polynomials P1, P2, then P1, P2 are said to relatively prime polynomials if the only factors they have in common are of degree 0.

Definition 4: degree: deg

The deg of a polynomial P is the greatest integer n for which the coefficient Xn in the expression of P is not zero.

Theorem 1: Euclid's Algorithm for Greatest Common Divisor for Polynomials

For any two polynomials P1, P2, there exists a GCD

Proof:

(1) Let P1, P2 be any two polynomials such that deg P1 ≥ deg P2

(2) If P2 = 0, then P1 is the GCD of P1, P2 [See Definition 2 above]

(3) Otherwise, we divide P1 by P2 using the Euclidean Division Algorithm for Polynomials. [See Theorem, here]

(4) Then there exists two polynomials Q1, R1 such that:

P1 = Q1P2 + R1

and deg R1 is less than deg P2.

(5) If R1 = 0, then P2 is the GCD of P1, P2

(6) Next, we divide P2 by R1 to get:

P2 = Q2R1 + R2

and deg R2 is less than deg R1

(7) If R2 ≠ 0, then we can set up the following equations:

(a) R1 = Q3R2 + R3

(b) R2 = Q4R3 + R4

...

(c) Rn-2 = QnRn-1 + Rn

(d) Rn-1 = Qn+1Rn + Rn+1

(8) Since deg P2 is greater than deg R1 which is greater than deg R2 which is greater than ... deg Rn which is greater deg Rn+1, this sequence cannot extend indefinitely.

(9) Therefore, Rn+1 = 0 for some n.

(10) Rn divides P1, P2 since:

Because Rn+1=0, Rn divides Rn-1

Because Rn divides Rn-1, from equation 7c, Rn divides Rn+1

We can now proceed up each of these implied equations in the same way until we get to 7b.

Since we have shown that Rn divides R2 and R3 before it, it is clear from 7a, that Rn divides R1

It is clear from step #6 that Rn divides P2 and clear from step #4 that Rn divides P1

(11) Assume that P1 and P2 are both divisible by a polynomial S.

(12) Then by step #4, S must divide R1.

(13) By step #6, S must divide R2

(14) We can now use the same argument to go through the equations in step #7 to conclude that S must likewise divide Rn.

(15) This proves that Rn is the GCD for P1,P2 [See Definition 2 above]

QED

Definition 5: monic polynomial

A polynomial is monic if and only if its leading coefficient is 1.

Theorem 2:

Any two polynomials P1, P2 ∈ F[X] which are not both 0 have a unique monic greatest common divisor D1 and a polynomial D ∈ F[X] is a greatest common divisor of P1, P2 if and only if D=cD1 for some c ∈ Fx (= F - {0}).

Proof:

(1) Let P1 ∈ F[X] be polynomials such that deg P1 is greater than deg P2

(2) Using Theorem 1 above, we know that there exists Rn such that Rn is the GCD of P1, P2

(3) Dividing Rn by its leading coefficient gives us a monic GCD of P1,P2

(4) Assume that D, D' are GCD's of P1, P2

(5) Then D divides D' and D' divides D. [See Definition 2 above]

(6) Then there exists polynomials Q,Q' ∈ F[X] such that:

D' = DQ
D = D'Q'

(7) So that:

Q = D'/D
Q' = D/D'

QQ' = (D'/D)(D/D') = 1

(8) But since Q'Q=1, they must both be constants which are inverses of each other.

(9) So, if D and D' are monic, then Q=Q'=1 and D=D' [Otherwise if Q ≠ 1, then D'=DQ would imply that D' is not be monic]

(10) Suppose D is any GCD of P1, P2

(11) Let D' be the unique monic GCD of P1, P2

(12) Let a = the leading coefficient of D.

(13) It is clear that (1/a)D = D' since the monic GCD is unique [see Step #9 above]

QED

Theorem 3:

If D is the GCD of P1, P2, then there exists polynomials U1, U2 such that:

D = P1U1 + P2U2 where U1, U2 ∈ F[X]

Proof #1:

(1) Using step #7c from Theorem 1 above, we have:

Rn-2 = QnRn-1 + Rn

which gives us:

Rn = Rn-2 - QnRn-1

and likewise:

Rn-1 = Rn-3 - Qn-1Rn-2

(2) We can then use the same type of equation to resolve Rn-1 to get:

Rn = Rn-2 - Qn(Rn-3 - Qn-1Rn-2) =

= Rn-2 - QnRn-3 + QnQn-1Rn-2 =

= -Rn-3Qn + Rn-2(1 +QnQn-1)

(3) We've now put Rn in terms of Rn-3 and Rn-2

(4) In this way, we can eliminate each Ri in terms of Ri-1 and Ri-2 up until we resolve R1 into P1, P2

(5) Eventually we get to an expression of Rn such that:

Rn = P1U1 + P2U2

QED

Proof #2:

(1) From step #4 of Theorem 1 above, we have:

P1 = Q1P2 + R1

(2) Using Matrix Theory (see here for review of 2 x 2 matrices), this gives us:



(3) From step #6 of Theorem 1 above we have:

P2 = Q2R1 + R2

which gives us:



(4) We can continue this approach until step #7d:

Rn-1 = Qn+1Rn + Rn+1

which gives us:



(5) Combining the matrix equations gives us:



(6) Now, since we know that:





(7) We see that each:



is invertible (see here for review of invertibility of matrices).

(8) We can then rearrange the equation in step #5 to be:



(9) Now, we can define U1, U2, U3, U4 such that:



(10) It now follows that:



(11) This then gives us that:

U1*P1 + U2*P2 = Rn

and

U3*P1 + U4*P2 = 0

QED

Corollary 3.1:

If P1, P2 are relatively prime polynomials in F[X], then there exists polynomials U1, U2 such that:

P1U1 + P2U2 = 1

Proof:

Since for relatively prime polynomials GCD = 1, this result follows directly from Theorem 3 above.

QED

References

Tuesday, December 04, 2007

Polynomials defined

A polynomial expression is a mathematical construct that if often used and rarely defined. The most common form is a polynomial in one variable which can be represented as:
a0xn + a1xn-1 + ... + a(n-1)x + an

In today's blog, I will present a more formal definition and then show the very fundamental result that a polynomial is a ring. If you are not familiar with rings, then please start here.

The content in today's blog is taken from Jean Tignol's excellent Galois' Theory of Algebraic Equations.

Definition 1: Polynomial in one indeterminant with coefficients in ring A

P: N → A such that { n ∈ N : Pn ≠ 0 } is finite. The set of all polynomials in one indeterminant with coefficients in ring A can be denoted as A[X].

Example 1:

Let us consider the polynomial:

a0 + a1X + ... + anXn

In this case, each ai is a coefficient in ring A.

We can see that for each i, that i ∈ N and that there exists an integer n ∈ N such that:

if i ≤ n, then i ∈ N maps to ai.

if i is greater than n, then i ∈ N maps to 0.

Definition 2: Addition of Polynomials

(P + Q)n = Pn + Qn

In other words, each of the maps corresponding to the same natural number are added together to form a new map.

Definition 3: Multiplication of Polynomials

(PQ)n = ∑ (i+j=n) Pi*Qj

In other words, each of the maps corresponding to the multiplication of all maps where the index of one plus the index of the other = n.

Lemma 1: If A is a ring, then A[X] is a ring which is commutative if and only if A is commutative

Proof:

(1) A[X] is a ring since:

(a) A[X] has a commutative operation of addition

P + Q = Pi + Qi for all i.

Q + P = Qi + Pi for all i.

Since A is a ring, Pi + Qi = Qi + Pi

(b) A[X] has an associative rule for addition

(P + Q) + R = (Pi + Qi) + Ri for all i

P + (Q + R) = Pi + (Qi + Ri) for all i

(Pi + Qi) + Ri = Pi + (Qi + Ri) since A is a ring.

(c) A[X] has an additive identity

Let Q be a polynomial such that all Qi map to 0.

Then for any polynomial P, it is clear that P + Q = Pi + 0 = Pi for all i.

(d) A[X] has an additive inverse

For any polynomial P:

Let Q be a polynomial derived from P such that for all i: Qi = -Pi

Then

P + Q = Pi + -Pi = 0 for all i.

(e) A[X] has an associative rule for multiplication

PQ = ∑ (i+j=n) Pi*Qj for all n

(PQ)R = ∑ (i+j+k=n) (Pi*Qj)Rk for all n =

= ∑ (i+j+k=n) Pi*(QjRk) for all n

QR = (j+k=n) Qj*Rk for all n

P(QR) = ∑ (i+j+k=n) Pi*(QjRk) for all n

(f) A[X] has a distributive rule

Q + R = Qj + Rj for all j

P(Q+R) = ∑ (i+j=n) Pi*(Qj + Rj) =

= ∑ (i+j=n) PiQj + PiRj

PQ = ∑ (i+j=n) Pi*Qj for all n

PR = ∑ (i+j=n) Pi*Rj for all n.

PQ + PR = ∑ (i+j=n) PiQj + ∑(i + j=n) PiRj for all n =

= ∑(i+j=n) PiQj + PiRj

(Q+R)P = ∑ (i+j=n) (Qj + Rj)*Pi =

= ∑ (i+j=n) PiQj + PiRj

(2) If A is a commutative ring, then A[X] is a commutative ring.

(a) Assume that A is a commutative ring

(b) PQ = ∑ (i+j=n) Pi*Qj for all n =

= ∑ (i+j=n) Qj*Pi for all n = QP

(3) If A[X] is a commutative ring, then A is a commutative ring

(a) Assume that A[X] is a commutative ring

(b) QP = PQ = ∑ (i+j=n) Pi*Qj for all n

(c) QP = ∑ (i+j=n) Qj*Pi for all n

(d) So, therefore for all n, ∑ (i+j=n) Pi*Qj = ∑ (i+j=n) Qj*Pi

QED

References