sin x < x < tan x for x in (0,π/2)

In today's blog, I will show how it is possible to use a unit circle to establish that if x is greater than 0 and less than π/2, then sin x is less than x which is less than tan x.

Theorem: if x is in (0,π/2), then sin x is less than x is less than tan x



Proof:

(1) Let O be a circle with radius = 1.

(2) Let ∠ CDO and ∠ BAO be right angles.

(3) Let x be the angle at ∠ COD

(4) We can see the following values apply to this diagram

cos x = adjacent/hypotenuse = OD/OC = OD/1 = OD

sin x = opposite/hypotenuse = CD/OC = CD/1 = CD

tan x = sin x/cos x = opposite/adjacent = AB/OA =AB/1 = AB

(5) Area of triangle OAC = (1/2)(base)(height) = (1/2)(OA)(CD) = (1/2)(1)(sin x) = (1/2)(sin x) [See Lemma 2, here for proof]

(6) Area of sector OAC = (1/2)(x)(radius)² = (1/2)(x)(1)² = (1/2)x [See Lemma 2, here for proof]

(7) Area of triangle OAB = (1/2)(base)(height) = (1/2)(OA)(AB) = (1/2)(1)(tan x) = (1/2)(tan x) [See Lemma 2, here for proof]

(8) By the diagram above, it is clear that triangle OAB is greater than sector OAC which is greater than triangle OAC.

(9) This then gives us that (1/2)(tan x) is greater than (1/2)(x) which is greater than (1/2)(sin x).

(10) Dividing all values by (1/2) gives us:

tan x is greater than x which is greater than sin x.

QED

References

• Use of Squeezing Theorem to Find Limits, analyzemath.com
  

Cauchy's Mean Value Theorem

I use Cauchy's Mean Value Theorem in my proof of L'Hopital's Rule (proof to be added later). Augustin-Louis Cauchy used this proof to as part of his effort to make calculus more rigorous. For those interested in learning more about Cauchy's role in reworking the foundations of calclulus, check out The Origins of Cauchy's Rigorous Calculus by Judith V. Grabiner.

Theorem Cauchy's Mean Value Theorem

If f(x),g(x) are continuous functions on the closed interval [a,b] and differentiable on (a,b)

Then, there exists a number c in (a,b) such that:

[f(b) - f(a)]g'(c) = [g(b)-g(a)]f'(c)

Proof:

(1) Let us define a function h(x) such that:

h(x) = [g(b) - g(a)]*[f(x) - f(a)] - [f(b) - f(a)]*[g(x) - g(a)]

(2) h(a) = h(b) = 0 since:

h(a) = [g(b) - g(a)]*[f(a) - f(a)] - [f(b) - f(a)]*[g(a) - g(a)] = [g(b) - g(a)]*0 - [f(b) - f(a)]*0 = 0

h(b) = [g(b) - g(a)]*[f(b) - f(a)] - [f(b) - f(a)]*[g(b) - g(a)] = 0

(3) h(x) is continuous in the closed interval [a,b] since:

(a) Using the Constant Law (see Lemma 1, here), we know that we can treat the values f(a),f(b),g(a),g(b), -1 as continuous functions.

(b) Using the Multiplication Law (see Lemma 3, here), we can treat -g(a), -f(a) as continuous functions.

(c) Using the Addition Law (see Lemma 2, here), we know that the following are continuous functions:

g(b) + [- g(a)] = g(b) - g(a)
f(x) + [- f(a)] = f(x) - f(a)
f(b) + [-f(a)] = f(b) - f(a)
g(x) + [-g(a)] = g(x) - g(a)

(d) Using the Multiplication Law and the Addition Law, we can see that h(x) is a continuous function

Since h(x) = [g(b)-g(a)]*[f(x) - f(a)] - [f(b) - f(a)]*[g(x) - g(a)]

(4) h(x) is also differentiable on (a,b) since:

NOTE: The detail here is parallel to the detail in step #3.

(a) We know that all constants are differentiable (see Lemma 1, here) so this means that f(a),f(b),g(a),g(b), -1 are all differentiable on (a,b)

(b) We know that the product of all differentiable functions are differentiable (see Lemma 4, here) so this means that -g(a), -f(a) are differentiable on (a,b)

(c) We also know that the addition of differentiable functions are differentiable (see Lemma 3, here) so this means that the following are all differentiable on (a,b):

g(b) + [- g(a)] = g(b) - g(a)
f(x) + [- f(a)] = f(x) - f(a)
f(b) + [-f(a)] = f(b) - f(a)
g(x) + [-g(a)] = g(x) - g(a)

(d) Finally, from the principles that we have already reviewed we know that h(x) is differentiable on (a,b) since:

h(x) = [g(b)-g(a)]*[f(x) - f(a)] - [f(b) - f(a)]*[g(x) - g(a)]

(e) We can now define h'(x)

Let u(x) = [g(b) - g(a)]*[f(x) - f(a)]

Let v(x) = [f(b) - f(a)]*[g(x) - g(a)]

u'(x) = [g(b) - g(a)][f'(x) - 0] + [0 - 0]*[f(x) - f(a)] = [g(b) - g(a)]f'(x) [See Lemma 4, here]

v'(x) = [f(b) - f(a)][g'(x) - 0] + [0 - 0]*[g(x) - g(a)] = [f(b) - f(a)]g'(x) [See Lemma 4, here]

h(x) = u(x) - v(x)

h'(x) = u'(x) - v'(x) = [g(b) - g(a)]f'(x) - [f(b) - f(a)]g'(x) [See Lemma 3, here]

(5) Using Rolle's Theorem, we know that there exists a point c such that:

h'(c) = 0 and c in (a,b)

(6) Now, combining our result for h'(x) in step #4 with step #5, we have:

h'(c) = [g(b) - g(a)]f'(c) - [f(b) - f(a)]g'(c) = 0

(7) Adding [f(b) - f(a)]g'(c) to both sides gives us:

[g(b) - g(a)]f'(c) = [f(b) - f(a)]g'(c)

QED

Corollary: Mean Value Theorem

If f(x) is a continuous function on the closed interval [a,b] and differentiable on the open interval (a,b), then there exists a point c in (a,b) such that:

f(b) - f(a) = f'(c)(b-a)

Proof:

(1) Let g(x) = x

(2) Then g'(x) = 1

(3) Using Cauchy's Mean Value Theorem above, we see that there exists a value c such that:

[f(b) - f(a)]g'(c) = [g(b)-g(a)]f'(c)

(4) Since g'(c) = 1, we see that:

f(b) - f(a) = [g(b) - g(a)]f'(c)

(5) Since g(x)=x, we see that:

f(b) - f(a) = (b - a)f'(c)

QED

References

• L'Hopital's Rule, Ask Dr. Math
• C. H. Edwards, Jr. and David E. Penney, Calculus and Analytic Geometry, Prentice Hall, 1990.
  

L'Hopital's Rule

In today's blog, I present a proof for L'Hopital's Rule which is also known as L'Hospital's Rule
which states that under certain circumstances, lim (x → a) f(x)/g(x) = lim (x → a) f'(x)/g'(x). I use it for example in the proof that ∑ 1/n² = π²/6 (Proof to be added later).

To prove this theorem, I will need to start with some lemmas that show that L'Hopital's Rule is true for specific cases.

Lemma 1: L'Hopital's Rule for 0/0 limits

Let f(x),g(x) be two functions that are differentiable in a deleted neighborhood (b,a) such that g'(x) is a nonzero, finite real number in that neighborhood, that is, when b is less than x is less than a.

If:

lim(x → a) f(x) = 0 and lim(x → a) g(x) = 0 and lim(x → a) f'(x)/g'(x) = a finite, real number

Then:

lim (x → a) f(x)/g(x) = lim (x → a) f'(x)/g'(x)

Proof:

(1) Let f(x),g(x) be continuous functions such that f(a)=0, g(a)=0

(2) Using Cauchy's Mean Value Theorem (see Theorem, here), for any x, there exists a point c such that x is less than c which is less than a and:

[f(a) - f(x)]g'(c) = [g(a)-g(x)]f'(c)

(3) We can rerrange the equation to give us:

f'(c)/g'(c) = [f(a) - f(x)]/[g(a) - g(x)]

(4) Since f(a)=0 and g(a) = 0, this gives us:

f'(c)/g'(c) = f(x)/g(x)

(5) Let L = lim(x → a) f'(x)/g'(x) [We know that L is a finite real number from the given]

(6) Let ε be any positive real value.

(7) By definition of limits (see Definition 1, here), for ε, there exists a δ such that:

if (x - a) is between -δ and +δ, then f'(x) - L is between -ε and +ε

(8) Since c is between x and a, we can see that as x moves toward a so does c. This gives us:

lim(c → a) f'(c)/g'(c) = L since

if (c-a) is between -δ and +δ, then f'(c) - L is between -ε and +ε

(9) But from step #4, since f(x)/g(x) = f'(c)/g'(c), we can see that as x moves toward a, c likewise moves toward a and we have:

lim(x → a) f(x)/g(x) = L since:

for ε, there exists a δ such that:

if (x - a) is between δ and +δ, then (x-c) is also between -δ and +δ and since f(x)/g(x) = f'(c)/g'(c), we have that f(x)/g(x) - L is between -ε and +ε since f(c)/g'(c) - L is between -ε and +ε [See step #7]

QED

Lemma 2: L'Hopital's Rule for ∞/∞ limits

Let f(x),g(x) be two functions that are differentiable in a deleted neighborhood (b,a) such that g'(x) is a nonzero, finite real number in that neighborhood, that is, when b is less than x is less than a.

If:

lim(x → a) f(x) = ∞ and lim(x → a) g(x) = ∞ and lim(x → a) f'(x)/g'(x) = a finite, real number

Then:

lim (x → a) f(x)/g(x) = lim (x → a) f'(x)/g'(x)

Proof:

(1) Let L = lim (x → a) f'(x)/g'(x) where L is a finite real number.

(2) Let ε be any positive value.

(3) From step #1, there exists δ such that if x -a is between -δ and δ, then f'(x) - L is between -ε and ε [Definition of limit, see here]

(4) Let b = a - δ

(5) Using Cauchy's Mean Value Theorem (see here), we know that there exists a value c such that c is in (a,b) and:

[f(a) - f(x)]g'(c) = [g(a)-g(x)]f'(c)

(6) Multiplying both sides by 1/([g'(c)][g(a) - g(x)]) gives us:

[f(a) - f(x)]/[g(a) - g(x)] = f'(c)/g'(c)

(7) Likewise, we can multiply (-1)/(-1) to both sides to get:

[f(x) - f(a)]/[g(x) - g(a)] = f'(c)/g'(c)

(8) Since c is in (a,b) and c moves toward a as x moves toward a, we have:

lim (c → a) f'(c)/g'(c) = lim (x → a) f'(x)/g'(x) = L

(9) But this means that:

lim (x → a) ([f(x) - f(a)]/[g(x) - g(a)]) = lim (c → a) f'(c)/g'(c) = L

(10) So using the definition of a limit we have:

If x - a is between -δ and +δ, then:

[f(x) - f(a)]/[g(x) - g(a)] - L is between -ε and +ε

(11) But since x is in (a,b), we know that x - a is less than a - (a - δ) = δ so we can conclude that:

[f(x) - f(a)]/[g(x) - g(a)] - L is between -ε and +ε

(12) Let h(x) = [1 - f(a)/f(x)]/[1 - g(a)/g(x)]

(13) Now,

lim (x → a) h(x)*f(x)/g(x) = lim(x → a) ([1 - f(a)/f(x)]/[1 - g(a)/g(x)]*f(x)/g(x) =

= lim (x → a) =([f(x) - f(a)]/g(x)-g(a)]) = L

(14) So, it follows that for x in (a,b), we have:

h(x)*f(x)/g(x) - L is between -ε and +ε

(15) Since lim (x → a) f(x) = ∞ and lim (x → a) g(x) = ∞, we have:

lim (x → a) [1 - f(a)/f(x)] = 1 - 0 = 1

lim (x → a) [1 - g(a)/g(x)] = 1 - 0 = 1

(16) Using the Quotient Rule for Limits (see Lemma 7, here), we have:

lim (x → a) h(x) = (lim (x → a) [1 - f(a)/f(x)])/(lim (x → a)[1 - g(a)/g(x)]) = 1/1 = 1

(17) Using the Product Rule for Limits (see Lemma 2, here), we have:

lim (x → a) h(x)*f(x)/g(x) =lim (x → a) h(x) * lim (x → a) f(x)/g(x)

(18) This means that:

lim (x → a) f(x)/g(x) = [lim (x → a) h(x)*f(x)/g(x)]/[lim (x → a) h(x)] =

= L/1 = L

QED

Lemma 3: L'Hopital's Rule for 0/0 limits where f'(x)/g'(x) has an infinite limit

Let f(x),g(x) be two functions that are differentiable in a deleted neighborhood (b,a) such that, when b is less than x is less than a.

If:

lim(x → a) f(x) = 0 and lim(x → a) g(x) = 0 and lim(x → a) f'(x)/g'(x) = +∞ or -∞

Then:

lim (x → a) f(x)/g(x) = lim (x → a) f'(x)/g'(x)

Proof:

(1) Let f(x),g(x) be continuous functions such that f(a)=0, g(a)=0

(2) Using Cauchy's Mean Value Theorem (see Theorem, here), for any x, there exists a point c such that x is less than c which is less than a and:

[f(a) - f(x)]g'(c) = [g(a)-g(x)]f'(c)

(3) We can rerrange the equation to give us:

f'(c)/g'(c) = [f(a) - f(x)]/[g(a) - g(x)]

(4) Since f(a)=0 and g(a) = 0, this gives us:

f'(c)/g'(c) = f(x)/g(x)

(5) Let L = lim(x → a+) f'(x)/g'(x)

We can assume that L is +∞. We could make the same argument with some adjustments if L is -∞

(6) Let ε be any positive real value.

(7) For an infinite limit, for ε, there exists a δ such that:

if (x - a) is between -δ and +δ, then f'(x) is between -1/ε and +1/ε

(8) Since c is between x and a, we can see that as x moves toward a so does c. This gives us:

lim(c → a+) f'(c)/g'(c) = +∞ since

if (c-a) is between -δ and +δ, then f'(c) is between -1/ε and +1/ε

(9) But from step #4, since f(x)/g(x) = f'(c)/g'(c), we can see that as x moves toward a, c likewise moves toward a and we have:

lim(x → a+) f(x)/g(x) = +∞ since:

for ε, there exists a δ such that:

if (x - a) is between δ and +δ, then (x-c) is also between -δ and +δ and since f(x)/g(x) = f'(c)/g'(c), we have that f(x)/g(x) is between -1/ε and +1/ε since f(c)/g'(c) is between -1/ε and +1/ε [See step #7]

QED

Lemma 4: L'Hopital's Rule for ∞/∞ limits where f'(x)/g'(x) has an infinite limit

Let f(x),g(x) be two functions that are differentiable in a deleted neighborhood (b,a) such that, when b is less than x is less than a.

If:

lim(x → a) f(x) = ∞ and lim(x → a) g(x) = ∞ and lim(x → a) f'(x)/g'(x) = +∞ or -∞

Then:

lim (x → a) f(x)/g(x) = lim (x → a) f'(x)/g'(x)

Proof:

(1) Let L = lim (x → a) f'(x)/g'(x) where L is +∞

NOTE: We can use the same argument with some modifications if L is -∞

(2) Let ε be any positive value.

(3) From step #1, there exists δ such that if x -a is between -δ and δ, then f'(x) is between -1/ε and 1/ε

This is true since we are talking about an infinite limit where 1/ε can get as close to infinity as one wishes.

(4) Let b = a - δ

(5) Using Cauchy's Mean Value Theorem (see here), we know that there exists a value c such that c is in (a,b) and:

[f(a) - f(x)]g'(c) = [g(a)-g(x)]f'(c)

(6) Multiplying both sides by 1/([g'(c)][g(a) - g(x)]) gives us:

[f(a) - f(x)]/[g(a) - g(x)] = f'(c)/g'(c)

(7) Likewise, we can multiply (-1)/(-1) to both sides to get:

[f(x) - f(a)]/[g(x) - g(a)] = f'(c)/g'(c)

(8) Since c is in (a,b) and c moves toward a as x moves toward a, we have:

lim (c → a) f'(c)/g'(c) = lim (x → a) f'(x)/g'(x) = L

(9) But this means that:

lim (x → a) ([f(x) - f(a)]/[g(x) - g(a)]) = lim (c → a) f'(c)/g'(c) = L

(10) So using the definition of a limit we have:

If x - a is between -δ and +δ, then:

[f(x) - f(a)]/[g(x) - g(a)] is between -1/ε and +1/ε

(11) But since x is in (a,b), we know that x - a is less than a - (a - δ) = δ so we can conclude that:

[f(x) - f(a)]/[g(x) - g(a)] is between -1/ε and +1/ε

(12) Let h(x) = [1 - f(a)/f(x)]/[1 - g(a)/g(x)]

(13) Now,

lim (x → a) h(x)*f(x)/g(x) = lim(x → a) ([1 - f(a)/f(x)]/[1 - g(a)/g(x)]*f(x)/g(x) =

= lim (x → a) =([f(x) - f(a)]/g(x)-g(a)]) = L

(14) So, it follows that for x in (a,b), we have:

h(x)*f(x)/g(x) is between -1/ε and +1/ε

(15) Since lim (x → a) f(x) = ∞ and lim (x → a) g(x) = ∞, we have:

lim (x → a) [1 - f(a)/f(x)] = 1 - 0 = 1

lim (x → a) [1 - g(a)/g(x)] = 1 - 0 = 1

(16) Using the Quotient Rule for Limits (see Lemma 7, here), we have:

lim (x → a) h(x) = (lim (x → a) [1 - f(a)/f(x)])/(lim (x → a)[1 - g(a)/g(x)]) = 1/1 = 1

(17) Using the Product Rule for Limits (see Lemma 2, here), we have:

lim (x → a) h(x)*f(x)/g(x) =lim (x → a) h(x) * lim (x → a) f(x)/g(x)

(18) This means that:

lim (x → a) f(x)/g(x) = [lim (x → a) h(x)*f(x)/g(x)]/[lim (x → a) h(x)] =

= L/1 = L

QED

Theorem: L'Hopital's Rule

Let f(x),g(x) be two functions that are differentiable in a deleted neighborhood a such that g'(x) is nonzero in that neighborhood.

If one of the following conditions are true:

(a) lim(x → a) f(x) = 0 and lim(x → a) g(x) = 0

(b) lim(x → a) f(x) = ∞ and lim(x → a) g(x) = ∞

Then:

lim (x → a) f(x)/g(x) = lim (x → a) f'(x)/g'(x)

Proof:

(1) Now, we need to be able to handle the following four cases:

Case I: a is a real number/L is a real number
Case II: a is a real number/L is infinity
Case III: a is infinity/L is a real number
Case IV: a is infinty/L is infinity

(2) Case I is handled through Lemma 1 and Lemma 2.

(3) Case II is handled through Lemma 3 and Lemma 4.

(4) Assume that a is +∞

We can make the same arguments if a is -∞ with some modifications.

(5) There exists y such that 1/y = x.

(6) As x goes towards +∞, y goes toward +0.

(7) dx/dy = -1/y² (See Lemma 2, here)

(8) Using the Chain Rule (see Lemma 2, here)

f'(x) = d/dy[f(1/y)] = f'(1/y)*d/dy[1/y] = f'(1/y)*(-1/y²)

g'(x) = d/dy[g(1/y)] = g'(1/y)*d/dy[1/y] = g'(1/y)*(-1/y²)

(9) Thus, we have:

lim (x → +∞) [f'(x)/g'(x)] = lim (y → 0+) [f'(1/y)*(-1/y²)]/[g'(1/y)*(-1/y²)] =

= lim (y→ 0+) [f'(1/y)/g'(1/y)]

(10) Now, depending on f(x),g(x), f'(x)/g'(x), we can use Lemma 1, 2, 3, or 4 to establish:

lim (y → 0+) [f'(1/y)/g'(1/y)] = lim (y → 0+) f(1/y)/g(1/y)

(11) Since x=1/y, this gives us:

lim (x → +∞) [f'(x)/g'(x)] = lim(y → 0+) [f'(1/y)/g'(1/y)] = lim (y → 0+) f(1/y)/g(1/y) = lim (x → +∞) f(x)/g(x)

QED

References

• L'Hopital's Rule, Ask Dr. Math
• C. H. Edwards, Jr. and David E. Penney, Calculus and Analytic Geometry, Prentice Hall, 1990.

Products of linear factors

Using the Fundamental Theorem of Algebra, we know that it is possible to express any equation of degree n with one variable as a product of linear factors.

In other words:

xⁿ + a₁x^n-1 + ... + a_n = (x - r₁)(x - r₂)*....*(x - r_n) where r_i represent the n roots for the equation.

In today's, blog, I show that we are not limited to this form.

Lemma 1:

if (r_i ≠ 0), then:

(x - r_i) = 0 if and only if (1 - x/r_i) = 0

Proof

(1) Assume that:

(x - r_i) = 0

(2) Then dividing both sides by (-r_i) gives us:

(1 - x/r_i) = 0

(3) Assume that:

(1 - x/r_i) = 0

(4) Multiply both sides by (-r_i) so that:

(x - r_i) = 0

QED

Corollary 1.1:

if (r_i² ≠ 0), then:

(x² - r_i²) = 0 if and only if (1 - x²/r_i²) = 0

Proof:

This follows directly from Lemma 1 above if set x' = x² and r' = r_i² then we have:

(x² - r_i²) = (1 - x²/r_i²) if and only if (x' - r') = (1 - x'/r')

QED

Euclid's Proof of the Infinitude of Primes

In today's blog, I will present a very well known proof. What makes this proof especially appealing is that it is not too complex. Even so, it is very powerful. This theorem was first presented in Euclid's Elements (Book IX, Proposition 20).

Theorem: There are an infinite number of primes.

Proof:

(1) Assume that there is only a finite number of primes.

(2) Then, there exists a prime p_n that is the largest prime.

(3) Let p₁, p₂, ..., p_n be the list of all primes that exist.

(4) Let x = p₁*p₂*...*p_n + 1.

(5) By the fundamental theorem of arithmetic (see Theorem 3, here), we know there is at least one prime that divides x. Let us call this prime p*.

(6) But none of the primes p₁ ... p_n divide x since x ≡ 1 (mod p_i) for any of the primes p₁ ... p_n

(7) Therefore, we have a contradiction. We have a prime p* that is not in the complete list of primes.

(8) So, we reject our assumption in step#1 and conclude that there are an infinite number of primes that exist.

QED

Modular Arithmetic: Additional Lemma

Lemma 1: if a ≡ b (mod p), then ap^n-1 ≡ bp^n-1 (mod pⁿ)

Proof:

(1) a ≡ b (mod p)

(2) So, there exists c such that pc = a - b

(3) So that a = pc + b

(4) So, ap^n-1 ≡ (pc+b)p^n-1 ≡ pⁿc + bp^n-1 ≡ bp^n-1 (mod pⁿ)

QED

Chinese Remainder Theorem

The Chinese Remainder Theorem gets its name from a 3rd century book written by the Chinese mathematician Sun Tzu. There are more details available on wikipedia.

In essence, it is a theorem about simultaneous congruences (see here if you need a review of modular arithmetic).

In today's blog, I will show the proof as it relates to standard integers.

Theorem: Chinese Remainder Theorem

Let a_i be a set of set of k integers consisting of a₁, a₂, ..., a_k.

Let n_i be a set of k coprime integers consists of n₁, n₂, ..., n_k where for any i,j if i ≠ j, then gcd(n_i,n_j)=1. [See here for review of greatest common divisor if needed]

Then, there exists an integer x such that for each a_i, n_i:

x ≡ a₁ (mod n₁)

x ≡ a₂ (mod n₂)

...

x ≡ a_k (mod n_k)

Proof:

(1) Let n = n₁ * n₂ * ... * n_k

(2) Let c_i = n / n_i for i = 1, ..., k

(3) We see that for all i, gcd(c_i,n_i) = 1 since:

(a) Assume gcd(c_i,n_i)=d where d is a number greater than 1.

(b) Then there exists a prime p that divides d (By the Fundamental Theorem of Arithmetic, see here)

(c) Since c_i = n₁ * ... * n_k, by Euclid's Generalized Lemma (see here), p must divides n_j where j ≠ i.

(d) But this impossible since by assumption gcd(n_i,n_j) = 1 when i ≠ j.

(e) So we reject that assumption in #2a.

(4) We further see that for all i,j when i ≠ j, n_j divides c_i.

This follows directly from c_i = n / n_i.

Which means that:

c_i ≡ 0 (mod n_i)

(5) Using Bezout's Identity (see here) and step #3, we know that for each c_i, n_i, there exists integers d_i,e_i such that:

c_id_i + e_in_i = 1.

(6) But this means that c_id_i ≡ 1 (mod n_i) since c_id_i - 1 = (-e_i)n_i

(7) Let x = a₁c₁d₁ + a₂c₂d₂ + ... + a_ic_id_i + ... + a_kc_kd_k

(8) We can show that x satisfies the assumption of the theorem since for any i:

x ≡ a₁(0)d₁ + a₂(0)d₂ + ... + a_i(1) + ... + a_k(0)d_k ≡ a_i (mod n_i)

QED

Group Theory: Quotient Groups

In today's blog, I will review some basic lemmas regarding normal subgroups and quotient groups. The concept of normal subgroups was first offered by Evariste Galois. The important idea behind normal subgroups is that when a subgroup is normal, then the set of left or right cosets is itself a group. This is what will be presented in today's blog.

I will use this result as part of Kummer's proof on Fermat's Last Theorem for regular primes.

Definition 1: Normal Subgroup

A subgroup H of a group G is called a normal subgroup of G if for all a ∈ G and all h ∈ H, there exists an element h' ∈ H such that ah = (h')a

NOTE: It is quite possible that h'=h but this is not necessary. From this perspective, normal subgroup is not necessarily an abelian group, that is, it may not be commutative (see here for definition of an abelian group).

NOTE #2: For all purposes definition 1 is the same as aH = Ha. Here's why:

For any x ∈ aH, there exists h ∈ H such that x = ah. From the definition, there exists h' such that h' ∈ H and ah=h'a which means that x=h'a which means that x ∈ Ha.

Lemma 1: A subgroup H is normal in G if and only if g^-1Hg ⊆ H for all g in G.

Proof:

(1) Assume H is a normal subgroup of G.

(2) Then, for any g ∈ G, h ∈ H, there exists h' ∈ H such that hg = gh' [See Definition of a Normal Subgroup above]

(3) Thus, g^-1hg = h' [Since g^-1gh' = eh' = h']

NOTE: We know that g^-1 ∈ G and that g^-1g = e (Inverse Property of Groups, see here). We know that eh' = h' (Identity Property of Groups, see here)

(4) Therefore for all g,h, we know that g^-1hg ∈ H [Since g^-1hg = h' and h' ∈ H]

(5) So that g^-1Hg ⊆ H [That is, for all x ∈ g^-1Hg → x ∈ H]

(6) Assume that g^-1Hg ⊆ H for all g ∈ G

(7) This means that Hg ⊆ gH [Since from #6, we have gg^-1Hg ⊆ gH and gg^-1Hg = eHg = Hg]

(8) Since g^-1 ∈ G, our assumption in #6 gives us:

(g^-1)^-1H(g^-1) = gHg^-1 ⊆ H

But this also means that:

gH ⊆ Hg since gHg^-1g = gH ⊆ Hg

(9) So combining step #7 and step #8 gives us: Hg = gH

NOTE: Hg = gH shows that for all h ∈ H, g ∈ G, there exists h' ∈ H such that: hg = gh'.

QED

Lemma 2: A subgroup of an abelian group is normal

Proof:

(1) Let G be an abelian group. [See here for definition of an abelian group]

(2) Let H be a subgroup of G. [See here for definition of a subgroup]

(3) g ∈ G, h ∈ H → gh = hg. [from the definition of abelian groups]

(4) Multiplying both sides by the inverse of g (see here) gives us:

g^-1gh = g^-1hg

This implies that:

h = g^-1hg

(5) Since h ∈ H, this gives us:
h ∈ H, g ∈ G → g^-1hg ∈ H.

(6) Using Lemma 1 above, we can now conclude that H is a normal subgroup of G.

QED

Definition 2: Quotient Group

Let G be a group and H a normal subgroup of G. The Quotient Group is defined as as the coset aH such that {aH : a ∈ G} and is represented as G/H

Example 1: Z/2Z under addition = { 0+2Z, 1+2Z}

Let Z be the set of integers.

We can see that the left coset 2z = the set of even integers = { ..., -2, 0, 2 ... }

Z/2Z = {a(2Z) : a ∈ Z} = two distinct cosets {0 + 2z, 1 + 2z}

Lemma 3: if aH = a'H, then there exists h ∈ H such that a' = ah

Proof:

(1) a' ∈ a'H [H is a group → e ∈ H → a'e ∈ a'H]

(2) a' ∈ aH [since aH = a'H]

(3) From #2, there exists h ∈ H such that a' = ah

QED

Lemma 4: aH = H if and only if a ∈ H

Proof:

(1) Assume aH = H

(2) a = ae ∈ aH

(3) So combining #1 and #2, a ∈ H

(4) Assume a ∈ H

(5) x ∈ aH → x=ah with h ∈ H

(6) But if a ∈ H and h ∈ H, then ah ∈ H (by property of closure, see here)

(7) From #5 and #6, we conclude that aH ⊆ H

(8) Let h ∈ H

(9) From #4 and #8, ah ∈ H and a^-1h ∈ H

(10) So, h = eh = (aa^-1)h = a(a^-1h)

(11) So, from #10, h ∈ aH and therefore H ⊆ aH

(12) Combining #7 (aH ⊆ H) and #11 (H ⊆ aH) gives us: aH = H

QED

Lemma 5: A Quotient Group is itself a group under the operation (aH)(bH) = abH.

Proof:

(1) Let H be a normal subgroup of G.

(2) Let G/H be the quotient group { aH : a ∈ G }

(3) First, we need to prove that (aH)(bH) = abH is a well-defined operation. In other words, we need to show that aH=a'H, bH = b'H → (a'b')H = (ab)H

NOTE: A function maps each of its input to exactly one output (see here for Wikipedia's review of a mathematical function) So, we need to prove if the inputs are equal, the outputs are equal.

(3) Assume that aH = a'H and bH = b'H with a,a',b,b' ∈ G

(4) Then a' = ah₁ and b' = bh₂ for some h₁,h₂ in H [By Lemma 3 above]

(5) Then a'b'H = (ah₁)(bh₂)H

(6) Using Lemma 4 above, since h₁, h₂ ∈ H we know that:

h₁H = H
h₂H = H

So that we have:

(ah₁)(bh₂)H = (ah₁)bH

(7) Since H is a normal subgroup of G, we know that b ∈ G → bH=Hb [See definition 1 above, note 2]

This gives us:

(ah₁)bH = (ah₁)Hb

Using Lemma 4 above gives us

(ah₁)Hb = aHb = abH

(8) Closure: x ∈ G/H, y ∈ G/H → xy ∈ G/H since:

x ∈ G/H → there exists a ∈ G such that x = aH.

y ∈ G/H → there exists b ∈ G such that y = bH

xy = (aH)(bH) = (ab)H [Definition of operation]

xy ∈ G/H since a ∈ G, b ∈ G → ab ∈ G so (ab)H ∈ G/H.

(9) Identity: H

e ∈ G → eH ∈ G/H

e ∈ H so eH = H [From Lemma 4 above]

Further, we see that:

(aH)(H) = (aH)(eH) = (ae)H = aH

(14) Inverse: a^-1H

x ∈ G/H → x = aH such that a ∈ G

a ∈ G → a^-1 ∈ G

So a^-1H ∈ G/H

Further,

(aH)(a^-1H) = (aa^-1)H = eH = H

(15) Associativity:

(aHbH)cH = (ab)HcH = (ab)cH [From the definition of the operation for this group]

= a(bc)H = [(ab)c = a(bc) since a,b,c ∈ G and G is a group so is characterized by associativity]

= aH(bc)H = [From the definition of operation for this group: aH(bc)H = a(bc)H]

= aH(bHcH) [From the defintion of operation for this group: bHcH = (bc)H]

QED

Group Theory: Lagrange's Theorem

In today's blog, I review the proof for Lagrange's Theorem. The theorem is named after Joseph-Louis Lagrange who first stated it. The first complete proof came 30 years later.

In today's blog, I also use the concept of order, subgroup, and coset. The concept of the coset was first proposed by Evariste Galois. The term "coset" was coined by G. A. Miller in 1910.

The content of today's blog is taken from Joseph A. Gallian's Contemporary Abstract Algebra.

Definition 1: Order of a Group

The number of elements of a group.

NOTE: If you need to review the definition of the group, see here.

Definition 2: Subgroup

If H is a subset of a group G and H is a group itself under the operation of G, then H is a subgroup of G.

Definition 3: Coset of H in G

Let G be a group and H a subgroup of G. For any a ∈ G, the set aH { ah : h ∈ H } is called the left coset of H in G containing a. The set Ha { ha : h ∈ H } is called the right coset of H in G containing a.

NOTE: An important idea behind the coset is that it is a distinct partition of elements (see Lemma 2 below). From the property of closure, we know that if two values are elements of a group, then their product (by this, I mean the result of the group operation) is also an element of the group.

From this, we know that the set of cosets can be divided up as follows: a₁H, a₂H, ..., a_rH where r is a positive integer and where for each coset i ≠ j → a_iH ∩ a_jH = ∅ [See Lagrange's Theorem below to see how this partitioning can be used]

Example 1 Coset: Z₉

Let G = Z₉ = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } with operation '+'

NOTE: Z₉ is the set of integers modulo 9 [See here for a review of modular arithmetic]

Let H = { 0, 3, 6 } with operation '+'

We can see that H is a subgroup of G

The left coset in this case is a+H (note it would aH is the operation were '*')

Here are the cosets:

0 + H = { 0, 3, 6 } = 3 + H = 6 + H
1 + H = { 1, 4, 7 } = 4 + H = 7 + H
2 + H = {2, 5, 8} = 5 + H = 8 + H

We can see that all cosets are either equal or distinct. I present a proof of this in Lemma 2 below.

Example 2: Even integers

Let Z be the set of integers

Then 2Z is a left coset which includes { ..., 0, 2, 4 , 6, ... }

Lemma 1: aH = H if and only if a ∈ H

Proof:

(1) Assume aH = H

(2) Then, a = ae ∈ aH = H

(3) Assume a ∈ H

(4) aH ⊆ H since h ∈ H → ah ∈ H [By property of closure, see here if needed]

(5) H ⊆ aH since:

(a) Let h be any element of H.

(b) a^-1 ∈ H since a ∈ H [By the inverse property, see here if needed]

(c) a^-1H ∈ H [By property of closure, see here if needed]

(d) So h = eh = (aa^-1)h = a(a^-1h) [By identity property, inverse property, and associative property, see here if needed]

(e) But a(a^-1h) ∈ aH so that from (#5d), h ∈ aH.

(6) So H = aH since H ⊆ aH and aH ⊆ H.

QED

Lemma 2: if aH, bH are two cosets, then aH = bH or aH ∩ bH = ∅

Proof:

(1) Assume that aH ∩ bH ≠ ∅

(2) Let x ∈ aH ∩ bH since aH ∩ bH ≠ ∅

(3) Then there exists h₁, h₂ such that:

x = ah₁
x= bh₂

Since x is found in both aH and bH by assumption.

(4) Thus, a = xh₁^-1 = (bh₂)h₁^-1

(5) From this, aH = [(bh₂)h₁^-1]H = b(h₂h₁^-1H) = bH [By Lemma 1 above]

QED

Theorem: Lagrange's Theorem

If G is a finite group and H is a subgroup of G, then the order of H divides the order of G.

Proof:

(1) Let a₁H, a₂H, ..., a_rH denote the distinct left cosets of H in G. [See Definition 3 above for details on left cosets of H in G.]

NOTE: If two cosets are equal then we only count them once.

(2) For each a ∈ G, we have aH = a_iH for some i by our construction in step #1.

(3) a ∈ aH since:

a = ae and ae ∈ aH since H is a subgroup. [See Definition 2 above for details on subgroups]

(4) Thus, each member of G belongs to one of the cosets a_iH [from step #2 and step #3.]

(5) G = a₁H ∪ a₂H ∪ ... ∪ a_rH [This follows directly from step #4]

(6) From Lemma 2 above, we know a_iH = a_jH or a_iH ∩ a_jH = ∅ and since each a_i is distinct, we get:

order(G) = order(a₁H) + order(a₂H) + ... + order(a_rH)

(7) Since order(a_iH) = order(H) for each i (by the definition of cosets, see definition 3 above, we have:

order (G) = r*order(H)

QED

Modular Arithmetic and Unique Mappings

Today, I talk about a result using modular arithmetic that I use in the properties of cyclotomic integers.

Lemma 1: For a given odd prime λ, each value i, 2*i, 3*i, ... (λ-1)*i maps to a distinct value of 1,2,3,...,(λ-1) modulo λ

Proof:

(1) Let a,b be any integer between 1 and λ-1 where a ≠ b

(2) Let i be any integer between 1 and λ - 1.

(3) Assume that a*i ≡ b*i (mod λ) where a,b are distinct.

(4) So λ divides a*i - b*i and there exists c such that λc = ai-bi = i(a-b)

(5) By Euclid's Lemma, λ divides either i or λ divides a-b.

(6) We know that λ doesn't divide i since i is between 1 and λ -1.

(7) So λ divides a-b

(8) But this means that a-b=0 since a,b are between 1 and λ - 1 and if a,b are distinct then abs(a-b) is between 1 and λ-2 which is not divisible by λ

(9) So we have a contradiction and we reject our assumption in (3).

QED

modular arithmetic and functions

Today, I want to go over a single lemma which I use in my analysis of cyclotomic integers.

Lemma 1:

if α,β are integers such α ≡ β (mod γ) and f(x) = xⁿ + a₁x^n-1 + ... + a_n

then f(α) ≡ f(β) (mod γ)

Proof:

(1) f(α) - f(β) = [(α)ⁿ - (β)ⁿ] + [a₁(α)^n-1 - a₁(β)^n-1] + ... + [a_n-1α - a_n-1β] + [a_n - a_n]

(2) Now, since α ≡ β (mod γ), we also have:

(α)² ≡ (β)² (mod γ)

all the way up to:

(α)^n-1 ≡ (β)^n-1 (mod γ)

and:

(α)ⁿ ≡ (β)ⁿ (mod γ)

(3) So this means that γ divides all parts of
[(α)ⁿ - (β)ⁿ] + [a₁(α^n-1 - β^n-1)] + ... + [a_n-1(α - β)]

(4) Which means that γ divides f(α) - f(β)

QED

Fields and Rings

In today's blog, I will talk about the assumptions behind the idea of a field. I use the concept of a field in the proof for the Division Algorithm for Polynomials.

Definition 1: Ring

A ring R is a nonempty set with two binary operations: addition (a + b) and multiplication (ab).

It has the following properties:

1. Commutative Rule for Addition: a + b = b + a

2. Associative Rule for Addition: (a + b) + c = a + (b + c)

3. Additive Identity: there exists a value 0 ∈ R such that a + 0 = a for all a ∈ R

4. Additive Inverse: for all elements a ∈ R, there exists a value -a ∈ R such that a + -a = 0.

5. Associative Rule for Multiplication: a(bc) = (ab)c

6. Distributive Rule: a(b + c) = ab + ac and (b + c)a = ba + ca

Definition 2: Commutative Ring

A ring that has the following additional property:

7. Commutative Rule for Multiplication: ab = ba

Definition 3: Field

A field is a commutative ring R with unity in which every nonzero element is a unit.

It has all the properties of a commutative ring plus:

8. Multiplicative Identity (unity): there exists a value 1 ∈ R such that such that a * 1 = a for all a ∈ R

9. Multiplicative Inverse (every nonzero element is a unit): for all nonzero elements a ∈ R, there exists an inverse a^-1 ∈ R such that a*a^-1 = 1.

Examples:

1. The set of integers Z is a commutative ring with unity 1. [See here for more information on the integers]

2. The set Z_n is a commutative ring with unity 1. [See here for more information on modular arithmetic]

3. The set of 2x2 matrices with integer entries is a noncommutative ring with unity. [See here for more information on 2x2 matrices]

4. If p is prime, then the set Z_p is a field. [See here for more information on modular arithmetic]

5. The set of rational numbers Q is a field.

6. The set of real numbers R is a field.

7. The set of complex numbers is a field. [See here for more information on complex numbers]

8. The set of Gaussian Integers is a ring. [See here for more information on Gaussian Integers]

9. The set of Eisenstein Integers is a ring. [See here for more information on Eisenstein Integers]

References

• Joseph A. Gallian, Contemporary Abstract Algebra
• Rings, Wikipedia
  

Division Algorithm for Polynomials

In today's blog, I will go over a result that I use in the proof for the Fundamental Theorem of Algebra.

Today's proof is taken from Joseph A. Gallian's Contemporary Abstract Algebra.

Theorem: Division Algorithm for Polynomials

Let F be a field, f(x), g(x) ∈ F[x] with 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)q(x) + r(x) with g(x) ≠ 0

(2) If f(x) = 0 or deg f(x) is less than g(x), then q(x)=0, r(x)=f(x)

(3) So, we can assume that f(x) ≠ 0 and deg f(x) ≥ deg g(x)

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

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

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

(7) We note that deg f₁(x) is less than deg f(x) since:

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

= a_nxⁿ + ... + a₀ - a_nb_m^-1x^n-m(b_mx^m + ... + b₀) =

= a_nⁿ - a_nxⁿ + a_n-1x^n-1 + ... + a₀ - a_nb_m^-1b_m-1x^n-1 - ... - a_nb_m^-1b₀x^n-m =

= a_n-1x^n-1 + ... + a₀ - a_nb_m^-1b_m-1x^n-1 - ... - a_nb_m^-1b₀x^n-m

So that f₁(x) has a degree of n-1 while f(x) has a degree of n.

(8) Now, we are ready to prove this theorem by induction.

(9) The assumption is true for deg f(x) = 0

deg f(x) is 0 → f(x)=C where C is a constant.

If deg g(x) is 0, then g(x) = D where D is a nonzero constant and q(x) = C/D and r(x)=0.

If deg g(x) is greater than 0, then q(x)=0 and r(x)=C.

(10) We can now assume that the assumption holds for all polynomials up to degree n-1.

(9) We see that:

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

where the degree of f₁(x) is n-1 [See step #7]

(10) But by the induction hypothesis (step #10), we can assume that there exists q₁(x) and r₁(x) where r₁(x) has a degree lower than g(x).

(11) Therefore, we have:

a_nb_m^-1x^n-mg(x) + f₁(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)

(12) Which proves that degree r(x) is less than degree g(x) by principle of induction.

(13) Now, we still need to prove uniqueness of q(x),r(x)

(14) Suppose that:

f(x) = g(x)q(x) + r(x) = g(x)q'(x) + r'(x) where r(x),r'(x)=0 or deg r(x),r'(x) is less than deg g(x)

(15) Now, if we substract both equations, we get:

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

which is the same as:

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

(16) Now since r'(x) and r(x) have degree less than g(x), the only way that this can be true is if r'(x) - r(x) = 0

(17) But then r'(x) = r(x) and q(x) = q'(x)

QED

References

• Joseph A. Gallian, Contemporary Abstract Algebra.