Greatest Common Divisor of a Polynomial and its First Derivative

Lemma 1:

Let a be a root of a polynomial P.

Then:

a is a multiple root of P if and only if a is also a root of P' (the first derivative of P)

Proof:

(1) Since a is a root of P, there exists a polynomial Q such that (see Theorem, here):

P = (x - a)Q

(2) Using the Product Rule of Derivatives (see Lemma 4, here), we know that:

P' = Q + (x-a)Q'

(3) But then (x-a) only divides P' if and only if it also divides Q.

QED

Corollary 1.1:

If a polynomial has only simple roots

Then:

Its first derivative does not share any of those roots.

Proof

(1) Assume that a polynomial P has only simple roots.

(2) Assume that a root a divides both P and P'

(3) Then by Lemma 1 above, a is a multiple root of P.

(4) But by step #1 this is impossible so we reject our assumption in step #2.

QED

Lemma 2:

If a polynomial P has only simple roots

Then P,P' are relatively prime.

Proof:

(1) Assume that P,P' are not relatively prime.

(2) Then, they have a common irreducible factor of degree 1.

[Since by definition, two polynomials are relatively prime if their only common factor is of degree 0]

(3) Then there exists a polynomial of the form X-a that divides both P and P' (See Thereom, here)

(4) Then from Lemma 1 above, a is a multiple root of P

(5) But this is impossible, so we reject our assumption in step #1.

QED

References

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

Alternate Form of the Greatest Common Divisor Algorithm for Polynomials

The usual form of the Greatest Common Divisor for Polynomials uses a series of steps of the form (see the proof for the usual form, here):

(a) R₁ = Q₃R₂ + R₃

(b) R₂ = Q₄R₃ + R₄

...

(c) R_n-2 = Q_nR_n-1 + R_n

(d) R_n-1 = Q_n+1R_n + R_n+1

But for Sturm's Theorem, I need to use an alternate form.

(a) R₁ = Q₃R₂ - R₃

(b) R₂ = Q₄R₃ - R₄

...

(c) R_n-2 = Q_nR_n-1 - R_n

(d) R_n-1 = Q_n+1R_n - R_n+1

Definition 1: Divisor for Polynomials

Let P₁, P₂ ∈ F[X].

We say that P₂ divides P₁ if there exists Q ∈ F[X] such that P₁ = P₂Q

Definition 2: GCD for Polynomials

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

(a) D divides P₁ and P₂
(b) If S is a polynomial which divides P₁ and P₂, then S divides D.

Definition 3: Relatively prime polynomials

If 1 is the GCD for polynomials P₁, P₂, then P₁, P₂ are said to relatively prime polynomials.

Definition 4: degree: deg

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

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

For any two polynomials P₁, P₂, there exists a GCD

Proof:

(1) Let P₁, P₂ be any two polynomials such that deg P₁ ≥ deg P₂

(2) If P₂ = 0, then P₁ is the GCD of P₁, P₂ [See Definition 2 above]

(3) Otherwise, we divide P₁ by P₂ using the the alternate form of Euclidean Division Algorithm for Polynomials. [See Theorem, here]

(4) Then there exists two polynomials Q₁, R₁ such that:

P₁ = Q₁P₂ - R₁

and deg R₁ is less than deg P₂.

(5) If R₁ = 0, then P₂ is the GCD of P₁, P₂

(6) Next, we divide P₂ by R₁ to get:

P₂ = Q₂R₁ - R₂

and deg R₂ is less than deg R₁

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

(a) R₁ = Q₃R₂ - R₃

(b) R₂ = Q₄R₃ - R₄

...

(c) R_n-2 = Q_nR_n-1 - R_n

(d) R_n-1 = Q_n+1R_n - R_n+1

(8) Since deg P₂ is greater than deg R₁ which is greater than deg R₂ which is greater than ... deg R_n which is greater deg R_n+1, this sequence cannot extend indefinitely.

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

(10) R_n divides P₁, P₂ since:

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

Because R_n divides R_n-1, from equation 7c, R_n divides R_n+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 R_n divides R₂ and R₃ before it, it is clear from 7a, that R_n divides R₁

It is clear from step #6 that R_n divides P₂ and clear from step #4 that R_n divides P₁

(11) Assume that P₁ and P₂ are both divisible by a polynomial S.

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

(13) By step #6, S must divide R₂

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

(15) This proves that R_n is the GCD for P₁,P₂ [See Definition 2 above]

QED

References

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

Ring of Polynomials

If you are not comfortable with the idea of rings, start here.

Definition 1: Polynomial in one indeterminate with coefficients in a ring A

P : N → A such that P = { n ∈ N : P_n ≠ 0 }

where N is the set of natural numbers (that is, 0, 1, 2, ... )

As a convention, this mapping is usually represented in the form:

a_nxⁿ + a_n-1x^n-1 + ... + a₁x + a₀

where n ∈ N.

Example 1:

5x² + 3x + 2 is a polynomial.

5,3,2 are all integers which is a ring (see here for details on integers)

{ 2 → 5, 1 → 3, 0 → 2 }

Definition 2: Polynomial Addition

(P + Q)_n = P_n + Q_n

Example 2:

(5x² + 3x + 2) + (3x² + x + 5) = (5 + 3)x² + (3+1)x + (2+5) = 8x² + 4x + 7

Definition 3: Polynomial Multiplication

(PQ)_n = ∑(i+j=n) P_i*Q_j

Example 3:

(5x² + 3x + 2)(3x² + x + 5) = (5*3)x⁽²⁺²⁾ + (5*1 + 3*3)x⁽²⁺¹⁾ + (5*5 + 3*1 + 2*3)x⁽²⁺⁰⁾ + (3*5 + 2*1)x⁽¹⁺⁰⁾ + (2*5)x⁰

Definition 4: A[X]

The set of all polynomials with coefficients in A

Example 4:

5x² + 3x + 2 ∈ Z[X] where Z is the set of all integers.

Lemma 1:

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

Proof:

(1) I will show that A[X] has all the properties of a ring.

(2) Commutative Property for Addition:

P_n + Q_n = (P + Q)_n = (Q + P)_n = Q_n + P_n

(3) Associative Property for Addition

(P_n + Q_n) + R_n = (P + Q)_n + R_n = ([P + Q] + R)_n = (P + [Q + R])_n

= P_n + (Q + R)_n = P_n + (Q_n + R_n)

(4) Additive Identity

This is the 0 polynomial. P_n + 0 = (P + 0)_n = P_n

(5) Additive Inverse

P_n + -P_n = (P + -P)_n = 0

(6) Associative Property for Multiplication

∑(i+j+k=n) (P_i*Q_j)*R_k = [(P*Q)*R]_n = [P*(Q*R)]_n = ∑ (i+j+k=n)P_i*(Q_j*R_k)

(7) Distributive Property for Multiplication

∑(i+j=n) P_i(Q_j + R_j) = ∑(i+j=n)P_i(Q + R)_j = [P(Q+R)]_n
= (PQ + PR)_n = ∑(i+j=n)(P_iQ_j) + ∑(i+j=n)(P_iR_j)

We can use the same argument to prove:

∑(i+j=n) (Q_j + R_j)P_i = ∑(i+j=n)(Q_jP_i) + ∑(i+j=n)(R_jP_i)

(8) Commutative Property for Multiplication is true if A has the Commutative Property for Multiplication

Assume that A is commutative.

∑(i+j=n)P_iQ_j = (PQ)_n = (QP)_n = ∑(i+j=n)Q_jP_i

QED

References

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

Degree of a Polynomial

Definition 1: Degree of a polynomial

The highest nonzero exponent is the degree of the polynomial.

As a convention, the degree of a zero polynomial is said to be -∞.

Lemma 1: deg(A+B) ≤ max(degA,degB)

Proof:

(1) We start with with deg A = 0, deg B=0 where A ≠ -B [We can ignore deg = - ∞ since by the Additive Identity Property (see here), it is true]

(2) A+B ≠ 0, so deg(A+B) = 0

(3) Assume that this is true up to deg A, deg B ≤ n-1.

(4) Let:

A = a_nxⁿ + ... + a₀

B = b_nx^n-1 + ... + b₀

(5) We can assume that a_n ≠ -b_n [Since if this is the case, the n degrees cancels out and the proposition is true by the inductive hypothesis.]

(6) a_n + b_n = (a+b)_n [See here for Additive Rule for Polynomials]

(7) So the deg(A+B) = n

QED

Lemma 2: deg(AB) = deg(A) + deg(B)

Proof:

(1) Assume deg A = 0, deg B = 0

(2) Then deg(AB) = 0 = 0 + 0

(3) Assume that the proposition is true up to n-1

(4) Let:

A = a_nxⁿ + ... + a₀

B = b_nx^n-1 + ... + b₀

(5) The highest exponent will be a_n*b_n = (a*b)_n+n

(6) deg(a*b)_n+n = 2n = deg(a) + deg(b)

QED

References

• "Degree of a Polynomial", Wikipedia.org
  

Alternate Form of the Division Algorithm for Polynomials

Theorem: Alternative Form of the Division Algorithm for Polynomials

Let F be a field

Let f(x),g(x) be polynomials of F[x] where g(x) ≠ 0

Then:

There exists unique polynomials q(x), r(x) in F[x] such that f(x) = g(x)q(x) - r(x) and r(x)=0 or deg r(x) is less than deg g(x)

Proof:

(1) Let f(x),g(x) be two polynomials such that g(x) ≠ 0

(2) We can assume that deg f(x) ≥ deg g(x) since:

if deg f(x) = 0, then f(x) = g(x)(0) - 0.

if deg f(x) is less than deg g(x), then f(x) = g(x)(0) - [-f(x)]

(3) Let:

f(x) = a_nxⁿ + ... + a₀

g(x) = b_mx^m + ... + b₀

where a_n and b_m are nonzero.

[We can make this assumption since g(x) ≠ 0 and deg f(x) ≥ deg g(x).]

(4) I will use induction to establish the existence of q(x), r(x).

(5) q(x),r(x) exist if deg f(x) = 0 since:

(a) Assume deg f(x) = 0

(b) Then there exists C such that f(x)=C

(c) Since deg f(x) ≥ deg g(x), it follows that deg g(x)= 0 and there exists D such that g(x)=D

(d) Let q(x) = C/D

(e) Then it follows that f(x) = g(x)*q(x) - 0

(6) Assume that our assumption holds true up to deg f(x) = n-1

(7) Let:

f₁(x) = f(x) - a_nb_m^-1x^n-mg(x)

(8) So, deg f₁(x) is less than deg f(x)

(9) By the induction hypothesis, there exists q₁(x) and r₁(x) such that:

f₁(x) = q₁(x)g(x) - r₁(x)

where deg r₁ is less than deg g(x) or deg r₁(x) = 0

(10) So, then:

f₁(x) + a_nb_m^-1x^n-mg(x) = a_nb_m^-1x^n-mg(x) + q₁(x)g(x) - r₁(x)

= [a_nb_m^-1x^n-m + q₁(x)]g(x) - r₁(x)

where deg r₁ is less than deg g(x) or deg r₁(x) = 0

(11) This proves the first part of the theorem. To complete it, we need to prove uniqueness.

(12) Assume that:

f(x) = g(x)q(x) - r(x) = g(x)q'(x) - r'(x)

where deg r(x), deg r'(x) = 0 or is less then deg g(x)

(13) So that:

0 = g(x)q(x) - r(x) - g(x)q'(x) + r'(x)

(14) Then:

r(x) - r'(x) = g(x)[q(x) - q'(x)]

(15) Assume that q(x) - q'(x) is nonzero.

(16) Then, deg g(x)[q(x)-q'(x)] = deg g(x) + deg (q(x) - q'(x)) [See Lemma 2, here]

(17) And, deg(r(x) - r'(x)) ≤ max(deg r(x),deg r'(x)) [See Lemma 1, here]

(18) But this is impossible since deg(r(x)) is less than deg g(x)

(19) So, we have a contradiction and we reject our assumption in step #15.

(20) So, if q(x) - q'(x) is 0, then it follows that r(x) - r'(x) is also 0.

(21) Then q(x) = q'(x) and r(x) = r'(x)

QED

Reference

• Joseph A. Gallian, Contemporary Abstract Algebra.

Inequality lemmas

Lemma 1: abs(a/b) ≤ 1 if and only if abs(a) ≤ abs(b)

Proof:

Case I: a,b are both positive

(1) Assume abs(a/b) ≤ 1

(2) a/b ≤ 1

(3) a ≤ b

(4) abs(a) ≤ abs(b)

(5) Assume abs(a) ≤ abs(b)

(6) a ≤ b

(7) a/b ≤ 1

(8) abs(a/b) ≤ 1

Case II: a,b are both negative

(1) Assume abs(a/b) ≤ 1

(2) a/b ≤ 1

(3) -a ≤ -b [since -b is positive]

(4) abs(a) ≤ abs(b)

(5) Assume abs(a) ≤ abs(b)

(6) -a ≤ -b

(7) a/b ≤ 1 [since -b is positive]

(8) abs(a/b) ≤ 1

Case III: Only b is negative

(1) Assume abs(a/b) ≤ 1

(2) -(a/b) ≤ 1

(3) (a/b) ≤ -1

(4) a ≤ -b [since b is negative and -b is positive]

(5) abs(a) ≤ abs(b) [ since abs(b) = -b ]

(6) Assume abs(a) ≤ abs(b)

(7) a ≤ -b

(8) a/b ≥ -1 [since b is negative]

(9) -(a/b) ≤ 1

(10) abs(a/b) ≤ 1

Case IV: Only a is negative

(1) Assume abs(a/b) ≤ 1

(2) -(a/b) ≤ 1

(3) -a ≤ b [since b is positive]

(4) abs(a) ≤ abs(b) [since abs(a) = -a and abs(b) = b]

(5) Assume abs(a) ≤ abs(b)

(6) -a ≤ b

(7) -a/b ≤ 1

(8) abs(a/b) ≤ 1

QED

Corollary 1.1: abs(a) is greater than abs(b) if and only if abs(a/b) greater than 1

Proof:

(1) Assume that abs(a) is greater than abs(b)

(2) Assume that abs(a/b) is not greater than 1

(3) Then abs(a/b) ≤ 1

(4) Then abs(a) ≤ abs(b) [From Lemma 1 above]

(5) But this contradicts step #1 so we reject our assumption in step #2.

(6) Assume that abs(a/b) is greater than 1.

(7) Assume that abs(a) is not greater than abs(b)

(8) Then abs(a) ≤ abs(b)

(9) Then abs(a/b) ≤ 1 [From Lemma 1 above]

(10) But this contradicts step #6 so we reject our assumption in step #7.

QED

Lemma 2:

if a,b,q are integers such that abs(a/b - q) is less than 1

Then:

There exists an integer c such that abs(a/b - c) is less than (1/2)

Proof:

(1) Assume abs(a/b - q) is greater than (1/2) [Otherwise, set c = q and we are done]

(2) if (a/b - q) is less than -1/2, then [a/b - (q-1)] is less than 1/2 and [a/b - (q-1)] is greater than 0

(3) if (a/b - q) is greater than 1/2, then [a/b - (q+1)] is greater than -1/2 and [a/b - (q+1)] is less than 0

QED

Corollary 2.1:

Let a,b be integers

if abs(a) ≤ abs(b)

Then:

There exists an integer c such that abs(a/b - c) is less than (1/2)

Proof:

(1) Assume abs(a) ≤ abs(b)

(2) Then abs(a/b) ≤ 1. [See Lemma 1 above]

(3) If (a/b) = 0, then c = 0 and the conclusion follows.

(4) if (a/b) ≥ -1, then abs(a/b + 1) is less than 1.

(5) if (a/b) ≤ 1, then abs(a/b - 1) is greater than -1.

(6) So, the conclusion follows from Lemma 2 above.

QED

A Simple Lemma Based on Calculus

The lemma in today's proof is used in my proof of Sturm's Problem of the Number of Roots. I will add a link to this proof when it is available.

Lemma 1:

Let F(x) = A*B

Then:

F'(x)/F(x) = A'/A + B'/B

Proof:

(1) Using the Product Rule (see Lemma 4, here):

F'(x) = A'B + B'A

(2) So:

F'(x)/F(x) = (A'B + B'A)/AB = A'B/AB + B'A/AB = A'/A + B'/B

QED

Corollary 1.1:

Let: F(x) = A₁*A₂*...*A_n

Then:

F'(x)/F(x) = A'₁/A₁ + A'₂/A₂ + ... + A'_n/A_n

Proof:

(1) Let F(x)=AB

Using Lemma 1 above, we know that F'(x)/F(x) = A'/A + B'/B

(2) Assume that this is true up to n-1 so that:

if F(x) = U₁*...*U_n-1

Then:

F'(x)/F(x) = U'₁/U₁ + U'₂/U₂ + ... + U'_n-1/U_n-1

(3) Let G(x) = U_n*(U₁*...*U_n-1)

(4) Using the Product Rule (see Lemma 4, here):

G'(x) = U'_n*(U₁*....*U_n-1) + U_n*(U₁*...*U_n-1)'

(5) Then G'(x)/G(x) = U'_n/U_n + (U₁*...*U_n-1)'/(U₁*...*U_n-1)

(6) From our assumption in step #2, this gives us:

G'(x)/G(x) = U'_n/U_n + U'₁/U₁ + ... + U'_n-1/U_n-1

(7) By Induction, we are done.

QED

Lemma 2:

Let F(x) = (x - α)^a

Then:

F'(x) = a(x - α)^a-1

Proof:

(1) Let U = x - α

(2) Using the power rule (see Lemma 2, here):

(d/dx)U^a = aU^a-1dU

(3) So, we have:

F'(x) = aU^a-1dU = a(x-α)^a-1*1 = a(x-α)^a-1

QED

Corollary 2.1:

Let F(x) = (x - α)^a

Then:

F'(x)/F(x) = a/(x - α)

Proof:

(1) From Lemma 1 above, F'(x) = a(x - α)^a-1

(2) Then F'(x)/F(x) = a(x-α)^a-1/(x - α)^a = a/(x - α)

QED

Corollary 2.2:

Let F(x) = (x - α)^a(x - β)^b(x - γ)^c*...

Then:

F'(x)/F(x) = a/(x - α) + b/(x - β) + c/(x - γ) + ...

Proof:

(1) Let A = (x - α)^a, B = (x - β)^b, C= (x - γ)^c, etc.

(2) So, we have: F(x) = A*B*C*...

(3) Using Corollary 1.1 above, this gives us that:

F'(x)/F(x) = A'/A + B'/B + C'/C + ...

(4) Using Corollary 2.1 and step #1, this gives us:

F'(x)/F(x) = a/(x - α) + b/(x - β) + c/(x - γ) + ...

QED

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