Saturday, February 07, 2009

Derivative of Increasing and Decreasing Functions

Lemma: Derivative of Increasing and Decreasing Functions

Let f be a continuous function on (a,b) where the at no point f'(x)=0.

If for all x on [a,b], f(x) is increasing, then f'(x) is positive.

If for all x on [a,b], f(x) is decreasing, then f'(x) is negative.

Proof:

(1) From the definition of derivatives (see Definition 1, here):

f'(x) = lim (Δx → 0) [f(x + Δx) - f(x)]/(Δx)

So, the sign of f'(x) is the sign of [f(x + Δx) - f(x)]/Δx and we can assume that is is nonzero.

(2) Case I: Δx is positive

If f(x) is strictly increasing, then f(x + Δx) - f(x) is positive and f'(x) is positive.

If f(x) is striclty decreasing, then f(x + Δx) - f(x) is negative and f'(x) is negative.

(3) Case II: Δx is negative

If f(x) is strictly increasing, then f(x + Δx) - f(x) is negative and f'(x) is positive

If f(x) is strictly decreasing, then f(x + Δx) - f(x) is positive and f'(x) is negative.

QED
Posted by at No comments :

Tuesday, February 03, 2009

An Inequality Lemma for the Cauchy Bound of Real Roots

The following result is used my proof of Cauchy's Bound for real roots.

Lemma 1: abs(c)n = abs(cn)

Proof:

(1) Assume that c is nonnegative

(2) Then, cn is nonnegative

(3) Then, abs(cn) = cn

(4) Since abs(c) = c, it follows that: cn = abs(c)n

(5) Assume that c is negative

(6) We can assume that n is odd

[Otherwise, cn = (-c)n = abs(c)n = abs(cn) ]

(8) abs(cn) = -cn = (-1)n*cn = (-c)n = abs(c)n

QED

Lemma 2:

Let:

ancn = -an-1cn-1 + .... + -a0

Then:

abs(an)*abs(c)n ≤ abs(an-1)*abs(c)n-1 + ... + abs(a0)

Proof:

(1) Using the Triangle Inequality (see Lemma 4, here), we know that:

abs(-an-1cn-1 + .... + -a0) ≤ abs(-an-1cn-1) + ... + abs(-a0)

so that:

abs(ancn) ≤ abs(-an-1cn-1) + ... + abs(-a0)

(2) Using a basic property of inequalities (see Lemma 1, here):

abs(an)*abs(cn) = abs(ancn)

and likewise:

abs(-an-1)*abs(cn-1) = abs(-an-1cn-1)

...

(3) So we have:

abs(an)*abs(cn) ≤ abs(-an-1)*abs(cn-1) + ... + abs(-a0)

(4) Using Lemma 1 above, we have:

abs(an)*abs(c)n ≤ abs(an-1)*abs(c)n-1 + ... + abs(a0)

QED
Posted by at No comments :

Triangle Inequality

Definition 1: Absolute Value

abs(a) = a if a is nonnegative or abs(a)=-a if a is negative.

So for example:

abs(5) = 5

abs(0) = 0

abs(-1) = 1

Now, let's look at some basic properties

Lemma 1: abs(ab) = abs(a)*abs(b)

Proof:

Case I: both a,b positive

abs(ab) = ab = abs(a)*abs(b)

Case II: both a,b negative

abs(ab) = ab = (-a)*(-b) = abs(a)*abs(b)

Case III: one negative, one positive

Assume a is positive, b is negative (since a,b are symmetrical, we can switch them as necessary)

abs(ab) = -ab = a*(-b) = abs(a)*abs(b)

QED

Lemma 2: -abs(a) ≤ a ≤ abs(a)

Proof:

Case I: a is nonnegative

-a ≤ a ≤ a

so

-abs(a) ≤ a ≤ abs(a)

Case II: a is negative

a ≤ a ≤ -a

so

-abs(a) ≤ a ≤ abs(a)

QED

Lemma 3: abs(a) ≤ b if and only if -b ≤ a and a ≤ b.

Proof:

(1) Assume abs(a) ≤ b

Case I: a is nonnegative

abs(a) = a

Since abs(a) ≤ b, it follows that a ≤ b and b is nonnegative

Since b is nonnegative and a is nonnegative, then it -b ≤ a.

Case II: a is negative

Since abs(a) ≤ b, it follows that -a ≤ b which is the same as -b ≤ a and therefore b must be nonnegative.

Since b is nonnegative, it follows that a ≤ b.

(2) Assume that -b ≤ a and a ≤ b.

Case I: a is nonnegative

Since a ≤ b, it follows that b is nonnegative

So abs(a) ≤ b.

Case II: a is negative

Since -b ≤ a, it follows that b ≥ -a.

Since a is negative, -a is positive, and we have:

abs(a) ≤ b.

QED

Lemma 4: Triangle Inequality

For all real numbers a,b

abs(a + b) ≤ abs(a) + abs(b)

Proof:

(1) For all real numbers a,b (from Lemma 1 above)

-abs(a) ≤ a ≤ abs(a)

-abs(b) ≤ b ≤ abs(b)

(2) Adding these two conditions together gives us:

-[abs(a) + abs(b)] ≤ a + b ≤ abs(a) + abs(b)

(3) Let c = a+b and d =abs(a) + abs(b)

(4) Using Lemma 3, we know that:

abs(c) ≤ d if and only if -d ≤ c and c ≤ d.

(5) But using step #2, we know that:

-d = -[abs(a) + abs(b)] ≤ c = a + b

and

c = a + b ≤ d = abs(a) + abs(b)

(6) So, using step #4 we get:

abs(c) ≤ d

which is equivalent to:

abs(a + b) ≤ abs(a) + abs(b)

QED
Posted by at 5 comments :

Sunday, February 01, 2009

Polynomials are continuous

For a definition of polynomials, see Definition 1, here. For a definition of continuous functions, see Definition 1, here.

Lemma 1: f(x)=x is continuous

Proof:

(1) Let ε be any arbitrary value.

(2) Let δ = ε

(3) For any point c, it is clear that if x lies in (c - δ, c + δ), then f(x)=x lies in (f(c) - ε, f(c) + ε )

QED

Corollary 1.1 : Polynomials are continuous

Proof:

(1) The function f(x)=x is continuous. [See Lemma 1 above]

(2) Since the product of continuous functions is continuous [See Lemma 3, here], then f(x)=xn where n is a positive integer is also continuous.

(3) Since f(x)=C is continuous [See Lemma 1, here], it follows that any function of the form cxn is also continuous.

(4) Since the addition of continuous functions is continuous [See Lemma 2, here], it follows that any polynomial function is continuous since it consists of the form:

f(x) = c0 + c1x + c2x2 + ... + cnxn

where each ci is a constant.

QED

Lemma 2: The Derivative of a polynomial is itself a polynomial

Proof

(1) The derivative of each term of a polynomial is itself a term of a polynomial [See the Lemma 2, here]

(2) So, it follows that the derivative itself is also a polynomial. [See Definition 1, here]

QED

Corollary 2.1: The derivative of a polynomial is a continuous function.

Proof:

This follows directly from Lemma 2 above and Corollary 1.1 above.

QED
Posted by at 2 comments :

Interval of a Function with Simple Roots

Lemma: Interval of a Function with Simple Roots

Let f be a function with simple roots such that f(c)=0

Then there exists an interval (a,b) such that:

c is in (a,b)

for all x in (a,b), f'(x) is all positive or all negative

Proof:

(1) Since f has only simple roots and f(c)=0, then it follows that f'(c) ≠ 0. [See Corollary 1.1, here]

(2) Since f is a polynomial, we know that f'(x) is continuous. [See Corollary 2.1, here]

(3) Since f'(c) is nonzero, let ε be nonzero and less than abs{ f'(c) }.

(4) Since f'(x) is continuous at c, there exists a number δ such that if x is in the (c - δ, c + δ), then f'(x) is in (f'(c)-ε, f'(c)+ε). [By the definition of a continuous function]

(5) Since ε is less than abs{f'(c) }, it follows that for x in (c -δ, c + δ), f'(x) is either entirely positive or entirely negative.

QED
Posted by at No comments :

Saturday, January 31, 2009

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
Posted by at No comments :

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) R1 = Q3R2 + R3

(b) R2 = Q4R3 + R4

...

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

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

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

(a) R1 = Q3R2 - R3

(b) R2 = Q4R3 - R4

...

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

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

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

If 1 is the GCD for polynomials P1, P2, then P1, P2 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 Xn 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 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 the alternate form of 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

References
Posted by at No comments :

Thursday, January 29, 2009

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 : Pn ≠ 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:

anxn + an-1xn-1 + ... + a1x + a0

where n ∈ N.

Example 1:

5x2 + 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 = Pn + Qn

Example 2:

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

Definition 3: Polynomial Multiplication

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

Example 3:

(5x2 + 3x + 2)(3x2 + x + 5) = (5*3)x(2+2) + (5*1 + 3*3)x(2+1) + (5*5 + 3*1 + 2*3)x(2+0) + (3*5 + 2*1)x(1+0) + (2*5)x0

Definition 4: A[X]

The set of all polynomials with coefficients in A

Example 4:

5x2 + 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:

Pn + Qn = (P + Q)n = (Q + P)n = Qn + Pn

(3) Associative Property for Addition

(Pn + Qn) + Rn = (P + Q)n + Rn = ([P + Q] + R)n = (P + [Q + R])n

= Pn + (Q + R)n = Pn + (Qn + Rn)

(4) Additive Identity

This is the 0 polynomial. Pn + 0 = (P + 0)n = Pn

(5) Additive Inverse

Pn + -Pn = (P + -P)n = 0

(6) Associative Property for Multiplication

∑(i+j+k=n) (Pi*Qj)*Rk = [(P*Q)*R]n = [P*(Q*R)]n = ∑ (i+j+k=n)Pi*(Qj*Rk)

(7) Distributive Property for Multiplication

∑(i+j=n) Pi(Qj + Rj) = ∑(i+j=n)Pi(Q + R)j = [P(Q+R)]n
= (PQ + PR)n = ∑(i+j=n)(PiQj) + ∑(i+j=n)(PiRj)

We can use the same argument to prove:

∑(i+j=n) (Qj + Rj)Pi = ∑(i+j=n)(QjPi) + ∑(i+j=n)(RjPi)

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

Assume that A is commutative.

∑(i+j=n)PiQj = (PQ)n = (QP)n = ∑(i+j=n)QjPi

QED

References
Posted by at No comments :

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 = anxn + ... + a0

B = bnxn-1 + ... + b0

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

(6) an + bn = (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 = anxn + ... + a0

B = bnxn-1 + ... + b0

(5) The highest exponent will be an*bn = (a*b)n+n

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

QED

References
Posted by at No comments :

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) = anxn + ... + a0

g(x) = bmxm + ... + b0

where an and bm 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:

f1(x) = f(x) - anbm-1xn-mg(x)

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

(9) By the induction hypothesis, there exists q1(x) and r1(x) such that:

f1(x) = q1(x)g(x) - r1(x)

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

(10) So, then:

f1(x) + anbm-1xn-mg(x) = anbm-1xn-mg(x) + q1(x)g(x) - r1(x)

= [anbm-1xn-m + q1(x)]g(x) - r1(x)

where deg r1 is less than deg g(x) or deg r1(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
Posted by at No comments :

Wednesday, January 28, 2009

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
Posted by at 1 comment :

Friday, January 16, 2009

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) = A1*A2*...*An

Then:

F'(x)/F(x) = A'1/A1 + A'2/A2 + ... + A'n/An

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) = U1*...*Un-1

Then:

F'(x)/F(x) = U'1/U1 + U'2/U2 + ... + U'n-1/Un-1

(3) Let G(x) = Un*(U1*...*Un-1)

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

G'(x) = U'n*(U1*....*Un-1) + Un*(U1*...*Un-1)'

(5) Then G'(x)/G(x) = U'n/Un + (U1*...*Un-1)'/(U1*...*Un-1)

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

G'(x)/G(x) = U'n/Un + U'1/U1 + ... + U'n-1/Un-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)Ua = aUa-1dU

(3) So, we have:

F'(x) = aUa-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
Posted by at No comments :

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
Posted by at 1 comment :

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
Posted by at No comments :

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
Posted by at 1 comment :

(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
Posted by at 2 comments :

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
Posted by at No comments :
Subscribe to: Posts ( Atom )