The set of integers can be constructed from the Natural Numbers.
We can define the set of integers as the set NxN where "x" is the Cartesian Product.
In set theory, the Cartesian Product is the combination of all the elements of one set with all the elements of the other set forming pair.
So, if N = { 1, 2, 3 ... }, then NxN = { (1,1), (1,2), (1,3), ..., (2,1),(2,2), ..., }
Here is the definition for integers:
Definition 1: Set of Integers: Z is the set NxN where (a,b) is the same number as (c,d) if and only if a + d = b + c.
NOTE: Z stands for Zahlen which is German for number.
From this perspective, each number corresponds to the set of all values (a,b) where a-b is equal to the number.
So 0 for example corresponds to { (1,1), (2,2), .... }
And -1 corresponds to { (1,2), (2,3), ... }
We can use the definition to show that (1,1) ~ (2,2) in that 1 + 2 = 1 + 2.
From this, we can now define addition, multiplication, and subtraction.
Definition 2: (a,b) + (c,d) = (a + c, b + d)
Example:
-1 + -3 = (2,3) + (5,8) = (2+5,3+8) = (7,11) = -4
Definition 3: (a,b) * (c,d) = (ac + bd, ad+bc)
Example:
-1 * -1 = (1,2)*(1,2) = (1*1 + 2*2,1*2 + 2*1) = (1 + 4,2 + 2) = (5,4) = 1
-1 * 3 = (1,2)*(4,1) = (1*4 + 2*1,1*1 + 2*4) = (4 + 2,1 + 8) = (6,9) = -3
Definition 4: (a,b) - (c,d) = (a + d, b + c)
Example:
4 - 3 = (5,1) - (4,1) = (5 + 1, 1 + 4) = (6, 5) = 1
(-3) - (-5) = (2,5) - (1,6) = (2 + 6, 5 + 1) = (8, 6) = 2
3 - 4 = (4,1) - (5,1) = (4 + 1, 1 + 5) = (5,6) = -1
Definition 5: (a,b) is less than (c,d) if and only if a + d is less than b + c
Example:
-3 is less than 4 since (2,5) is less than (5,1) since 2+1=3 is less than 5 + 5=10.
Lemma 1: Z is closed under addition.
(1) (a,b) + (c,d) = (a + c, b + d)
(2) a + c is a natural number and b + d is a natural number (since addition is closed for natural numbers, see here)
QED
Lemma 2: Z is closed under multiplication
(1) (a,b) * (c,d) = (ac + bd, ad + bc)
(2) ac, bd, ad, bc are all natural numbers since N is closed under multiplication (see here)
(3) ac + bd, ad + bc are natural numbers since N is closed under addition (see here)
QED
Lemma 3: Z is closed under subtraction
(1) (a,b) - (c,d) = (a + d, b + c)
(2) a + d, b + c are both natural numbers since N is closed under addition (see here)
QED
Lemma 4: Z has 0 as the identity element for addition
n + 0 = (n+1,1) + (1,1) = (n + 2,2) = n
QED
Lemma 5: Z has 1 as the identity element for multiplication
n * 1 = (n + 1, 1)*(2,1) = (2*(n+1) + 1*1, (n+1)*1 + 2) = (2n + 3,n + 3) = n
QED
Lemma 6: Each element of Z has an inverse element for addition that is determined by reversing the pairs (b,a) is the inverse element for (a,b)
n + (-n) = (n+1,1) + (1,n+1) = (n + 1 + 1, 1 + n + 1) = (n+2,n+2) = 0
QED
Lemma 7: Z is commutative on addition: a + b = b + a
a + b = (a+1,1) + (b+1,1) = (a + b + 2,2)
b + a = (b+1,1) + (a+1,1) = (b + a + 2,2) = (a + b + 2,2) [Since natural numbers are commutative on addition, see here]
QED
Lemma 8: Z is commutative on multiplication: a*b=b*a
a*b = (a+1,1)*(b+1,1) = ((a+1)(b+1) + 1*1,(a+1)*1 + 1*(b+1)) =
= (ab + a + b + 1 + 1, a + 1 + b + 1) =
= (ab + a + b + 2,a + b + 2) = ab
b*a = (b+1,1)*(a+1,1) = ((b+1)(a+1) + 1*1,(b+1)*1 + 1*(a+1)) =
= (ba + a + b + 2, a + b + 2) =
= (ab + a + b + 2, a + b + 2) = ab [Since natural numbers are commutative on multiplication, see here]
QED
Lemma 9: Z is associative on addition
(a+b) + c = [(a+1,1) + (b+1,1)] + (c+1,1) = (a+b+2,2) + (c+1,1) = (a+b+c+3,3)=
= a+b+c
a + (b+c) = (a+1,1) + [(b+1,1) + (c+1,1)] = (a+1,1) + (b+c+2,2) = (a+b+c+3,3) =
= a+b+c
QED
Lemma 10: Z is associative on multiplication
(a*b)*c = [(a+1,1)*(b+1,1)]*(c+1,1)=
= [(a+1)(b+1) + (1)(1),(a+1)(1) + 1(b+1)](c+1,1) =
= (ab + a + b + 2, a+1+b+1)(c+1,1) = (ab+1,1)(c+1,1) =
= ((ab+1)(c+1) + (1)(1), (ab+1)(1)+(1)(c+1)) =
= (abc + ab + c + 1 + 1, ab + 1 + c + 1) =
= (abc + ab + c + 2, ab + c + 2) = abc
a*(b*c) = (a+1,1)[(b+1,1)(c+1,1)] =
= (a+1,1)((b+1)(c+1) + (1)(1),(b+1)(1)+(1)(c+1)) =
= (a+1,1)(bc + b + c + 1 + 1,b+1+c+1) =
= (a+1,1)(bc+b+c+2,b+c+2)=(a+1,1)(bc+1,1)=
= ((a+1)(bc+1) + (1)(1),(a+1)(1) + (1)(bc+1)) =
= (abc + a + bc + 1 + 1,a + 1 + bc + 1) =
= (abc + 1, 1) = abc
QED
Lemma 11: Z is distributive: (a+b)c =ac + bc.
(a+b)c = [(a+1,1)+(b+1,1)](c+1,1) = [(a + b + 2,1+1)](c+1,1) = (a+b+1,1)(c+1,1) =
= ((a+b+1)(c+1) + (1)(1),(a+b+1)(1) + (1)(c+1)) =
= (ac + bc +c + a + b + 1 + 1,a + b + 1 + c + 1) =
= (ac + bc + 1, 1) = ac + bc.
QED
References
Monday, February 06, 2006
Sunday, February 05, 2006
Natural Numbers
The natural numbers are the numbers that are most familiar to us; they are the counting numbers that usually begin at 1 (some mathematicians hold that the natural numbers include 0). This also matches with the history of mathematics where the use of 0 was a major innovation.
The mathematician Kronecker once said:
"God made the natural numbers. Everything else is the work of man." (Quoted from here)
At the same time, this leads us to an interesting question. Is it possible to define the natural numbers in terms of a set of axioms similiar to what Euclid did for geometry?
The successful definition of natural numbers was done by two men: Richard Dedekind in his book What is a Number and the logician Guiseppe Peano. Today, these axioms are known as Peano's Axioms.
Here are a set of postulates based on Peano's Axioms:
I. The natural numbers is a set of numbers starting with 1 where each number has a unique successor which we will characterize by S(a) where a is a natural number.
II. All numbers but 1 have are themselves successors to a unique number.
III. a = b if and only if S(a) = S(b)
IV. If a property is possessed by 1 and possession by a value a implies it is also true of S(a), then we say it is true of all numbers. (Axiom of Induction)
Definition 1: m + n
m + 1 = S(m)
m + S(n) = S(m + n)
Example:
1 + 2 = S(1 + 1) = S(S(1)) = S(2) = 3
Definition 2: m * n
m * 1 = m
m * S(n) = m + (m * n)
Example:
2 * 2 = 2 + (2*1) = 2 + 2 = 4
Definition 3: m is less than n
m is less than n if there exists a natural number d such that m + d = n.
Definition 4: m - n
S(m) - 1 = m
S(m) - S(n) = m - n
If m is less than or equal to n, then it is undefined.
Lemma 1: Natural numbers are closed under addition.
(1) m+1 = S(m)
(2) Assume that there exists a value n such that m + n is a natural number.
(3) m + S(n) = S(m+n)
(4) Which must also be a natural number by Axiom I.
QED
Lemma 2: Natural numbers are closed under multiplication
(1) m*1 = m
(2) Assume that there exists a value n such that m * n is a natural number
(3) m*S(n) = m + (m*n)
(4) Which is a natural number by Lemma 1 above.
QED
Lemma 3: Natural numbers are not closed under subtraction.
m - n is undefined for the case where m ≤ n.
QED
Lemma 4: 1 + m = S(m)
(1) Case n=1:
1 + 1 = S(1)
(2) Assume that it is true up to n.
(3) 1 + (n+1) = 1 + S(n) = S(n+1)
(4) So, it is true by Axion IV.
QED
Lemma 5: Natural numbers are commutative under addition: m + n = n + m
(1) For case n=1:
m + 1 = S(m)
(2) From Lemma 4, 1 + m = S(m)
(3) Assume it is true up to n so that m+n=n+m
(4) m + (n+1) = m + S(n) = S(m+n)
(5) (n+1) + m = S(n) + m = S(n+m) = S(m+n)
(6) So, we apply Axiom IV and we are done.
QED
Lemma 6: 1*m = m*1
(1) 1*1 = 1*1
(2) S(m)*1 = S(m) [By Definition 2 above]
(3) 1*S(m) = 1 + m = m + 1 = S(m)
(4) We are done since all numbers are either 1 or a successor to another number. (by Axion II)
QED
Lemma 7: Distributive Law: (a + b)m = am + bm
(1) Case m = 1:
(a + b)1 = a + b [By Definition 2]
a(1) + b(1) = a + b [By Definition 2]
(2) So we assume that it is true up to n so that (a+b)n = an + bn.
(3) (a+b)S(n) = (a + b) + (a+b)n = a + b + an + bn = a + an + b + bn
(4) a(S(n)) + b(S(n)) = a + an + b + bn
(5) So by the Axiom of Induction we are done (see Axiom IV)
QED
Lemma 8: Natural numbers are commutative under multiplication: m * n = n * m
(1) Case n=1:
m * 1 = 1 * m [From Lemma 6 above]
(2) Assume that it is true up to n so that we have m*n=n*m
(3) m*(n+1) = m + mn [By definition 2]
(4) (n+1)*m = nm + m = m + nm = m + mn
(5) So we are done by the Axion of Induction (Axiom IV above)
QED
Lemma 9: Natural numbers are associative under addition:
(a + b) + n = a + (b + n)
(1) Case n = 1
(a + b) + 1 = S(a + b)
a + (b + 1) = a + S(b) = S(a + b)
(2) (a + b) + S(n) = S(a + b + n)
(3) a + (b + S(n)) = a + S(b + n) = S(a + b + n)
(4) It is true now in all cases since all numbers are either 1 or are a successor (by Axiom II above)
QED
Lemma 10: Natural numbers are associative under multiplication:
(a*b)*n = a*(b*n)
(1) Case n = 1
(a*b)*1 = a*b
a*(b*1) = a*b
(2) (ab)*S(n) = S(n)(ab) = (n+1)(ab) = abn + ab
(4) a*(b*S(n)) = a*(b*(n+1)) = a*((n+1)*b) = a*(bn+b) = (bn+b)*a = abn+ab
QED
References
The mathematician Kronecker once said:
"God made the natural numbers. Everything else is the work of man." (Quoted from here)
At the same time, this leads us to an interesting question. Is it possible to define the natural numbers in terms of a set of axioms similiar to what Euclid did for geometry?
The successful definition of natural numbers was done by two men: Richard Dedekind in his book What is a Number and the logician Guiseppe Peano. Today, these axioms are known as Peano's Axioms.
Here are a set of postulates based on Peano's Axioms:
I. The natural numbers is a set of numbers starting with 1 where each number has a unique successor which we will characterize by S(a) where a is a natural number.
II. All numbers but 1 have are themselves successors to a unique number.
III. a = b if and only if S(a) = S(b)
IV. If a property is possessed by 1 and possession by a value a implies it is also true of S(a), then we say it is true of all numbers. (Axiom of Induction)
Definition 1: m + n
m + 1 = S(m)
m + S(n) = S(m + n)
Example:
1 + 2 = S(1 + 1) = S(S(1)) = S(2) = 3
Definition 2: m * n
m * 1 = m
m * S(n) = m + (m * n)
Example:
2 * 2 = 2 + (2*1) = 2 + 2 = 4
Definition 3: m is less than n
m is less than n if there exists a natural number d such that m + d = n.
Definition 4: m - n
S(m) - 1 = m
S(m) - S(n) = m - n
If m is less than or equal to n, then it is undefined.
Lemma 1: Natural numbers are closed under addition.
(1) m+1 = S(m)
(2) Assume that there exists a value n such that m + n is a natural number.
(3) m + S(n) = S(m+n)
(4) Which must also be a natural number by Axiom I.
QED
Lemma 2: Natural numbers are closed under multiplication
(1) m*1 = m
(2) Assume that there exists a value n such that m * n is a natural number
(3) m*S(n) = m + (m*n)
(4) Which is a natural number by Lemma 1 above.
QED
Lemma 3: Natural numbers are not closed under subtraction.
m - n is undefined for the case where m ≤ n.
QED
Lemma 4: 1 + m = S(m)
(1) Case n=1:
1 + 1 = S(1)
(2) Assume that it is true up to n.
(3) 1 + (n+1) = 1 + S(n) = S(n+1)
(4) So, it is true by Axion IV.
QED
Lemma 5: Natural numbers are commutative under addition: m + n = n + m
(1) For case n=1:
m + 1 = S(m)
(2) From Lemma 4, 1 + m = S(m)
(3) Assume it is true up to n so that m+n=n+m
(4) m + (n+1) = m + S(n) = S(m+n)
(5) (n+1) + m = S(n) + m = S(n+m) = S(m+n)
(6) So, we apply Axiom IV and we are done.
QED
Lemma 6: 1*m = m*1
(1) 1*1 = 1*1
(2) S(m)*1 = S(m) [By Definition 2 above]
(3) 1*S(m) = 1 + m = m + 1 = S(m)
(4) We are done since all numbers are either 1 or a successor to another number. (by Axion II)
QED
Lemma 7: Distributive Law: (a + b)m = am + bm
(1) Case m = 1:
(a + b)1 = a + b [By Definition 2]
a(1) + b(1) = a + b [By Definition 2]
(2) So we assume that it is true up to n so that (a+b)n = an + bn.
(3) (a+b)S(n) = (a + b) + (a+b)n = a + b + an + bn = a + an + b + bn
(4) a(S(n)) + b(S(n)) = a + an + b + bn
(5) So by the Axiom of Induction we are done (see Axiom IV)
QED
Lemma 8: Natural numbers are commutative under multiplication: m * n = n * m
(1) Case n=1:
m * 1 = 1 * m [From Lemma 6 above]
(2) Assume that it is true up to n so that we have m*n=n*m
(3) m*(n+1) = m + mn [By definition 2]
(4) (n+1)*m = nm + m = m + nm = m + mn
(5) So we are done by the Axion of Induction (Axiom IV above)
QED
Lemma 9: Natural numbers are associative under addition:
(a + b) + n = a + (b + n)
(1) Case n = 1
(a + b) + 1 = S(a + b)
a + (b + 1) = a + S(b) = S(a + b)
(2) (a + b) + S(n) = S(a + b + n)
(3) a + (b + S(n)) = a + S(b + n) = S(a + b + n)
(4) It is true now in all cases since all numbers are either 1 or are a successor (by Axiom II above)
QED
Lemma 10: Natural numbers are associative under multiplication:
(a*b)*n = a*(b*n)
(1) Case n = 1
(a*b)*1 = a*b
a*(b*1) = a*b
(2) (ab)*S(n) = S(n)(ab) = (n+1)(ab) = abn + ab
(4) a*(b*S(n)) = a*(b*(n+1)) = a*((n+1)*b) = a*(bn+b) = (bn+b)*a = abn+ab
QED
References
- Peano Axioms, Wikipedia
- Peano Arithmetic, Planet Math
- Natural Numbers, Dr. Noach Dana Picard's Page
Thursday, January 12, 2006
Continued Fractions; Loose Ends
In today' s blog, I will provide details that are used in the general proof for Continued Fractions.
Lemma 1: If x is a positive integer, then x2 - 4 is not a square.
(1) First, I will show that for all positive integers greater than 2, the difference between one square and the next highest square is greater than 4 therefore no square x2 - 4 can exist.
(2) For n=2, the smallest difference is 9 - 4 = 5 which is greater than 4.
(3) We assume that this is true up to n ≥ 2.
(4) So (n+1)2 - n2 = n2 + 2n + 1 - n2 = 2n + 1 ≥ 2(2) + 1 = 5.
(5) In other words, the minimal difference between any two successive squares is at least 5.
(6) Now, I will show that all differences 2 or less don't work either.
32 - 22 = 9 - 4 = 5
21 - 12 = 1
12 - 02 = 1
The only possible differences then are 1, 2, or a number ≥ 5.
QED
Lemma 1: If x is a positive integer, then x2 - 4 is not a square.
(1) First, I will show that for all positive integers greater than 2, the difference between one square and the next highest square is greater than 4 therefore no square x2 - 4 can exist.
(2) For n=2, the smallest difference is 9 - 4 = 5 which is greater than 4.
(3) We assume that this is true up to n ≥ 2.
(4) So (n+1)2 - n2 = n2 + 2n + 1 - n2 = 2n + 1 ≥ 2(2) + 1 = 5.
(5) In other words, the minimal difference between any two successive squares is at least 5.
(6) Now, I will show that all differences 2 or less don't work either.
32 - 22 = 9 - 4 = 5
21 - 12 = 1
12 - 02 = 1
The only possible differences then are 1, 2, or a number ≥ 5.
QED
Wednesday, January 11, 2006
Quadratic Equation Solved
One of the most useful formulas of all time historically is the solution of the equation:
ax2 + bx + c = 0.
The equation above is known as the quadratic equation.
Theorem: (-b ± √b2 - 4ac)/2a is the solution to the quadratic equation.
(1) First, we multiply both sides by 4a and get:
4a2x2 + 4abx + 4ac = 0
(2) Next, we add b2 - b2 to the equation:
4a2x2 + 4abx + b2 + 4ac - b2 = 0
(3) Now, we add b2 - 4ac to both sides which gives us:
4a2x2 + 4abx + b2 = b2 - 4ac
(4) Further, we know that:
(2ax + b)2 = 4a2x2 + 4axb + b2
(5) Combining #4 and #3, gives us:
(2ax + b)2 = b2 - 4ac
(6) Now, taking the square root of both sides gives us:
2ax + b = ±√b2 - 4ac
(7) Now, using basic algebra, we get to:
x = (-b ±√b2 - 4ac)/2a.
ax2 + bx + c = 0.
The equation above is known as the quadratic equation.
Theorem: (-b ± √b2 - 4ac)/2a is the solution to the quadratic equation.
(1) First, we multiply both sides by 4a and get:
4a2x2 + 4abx + 4ac = 0
(2) Next, we add b2 - b2 to the equation:
4a2x2 + 4abx + b2 + 4ac - b2 = 0
(3) Now, we add b2 - 4ac to both sides which gives us:
4a2x2 + 4abx + b2 = b2 - 4ac
(4) Further, we know that:
(2ax + b)2 = 4a2x2 + 4axb + b2
(5) Combining #4 and #3, gives us:
(2ax + b)2 = b2 - 4ac
(6) Now, taking the square root of both sides gives us:
2ax + b = ±√b2 - 4ac
(7) Now, using basic algebra, we get to:
x = (-b ±√b2 - 4ac)/2a.
Sunday, January 01, 2006
Irrational Numbers
Irrational numbers are numbers that cannot be formed by the ratio of two integers. In Ancient Greece, the mathematician and philosopher Pythagoras created a secret society whose sole goal was to study the universe in terms of numbers. Pythagorus had discovered that musical harmonies result from perfect ratios between string sizes and became convinced that all the universe could be studied in terms of these perfect ratios. For example, the most famous discovery of his group was the Pythagorean Theorem which states that the hypotenuse (the diagonal) of a right triangle is equal to the sum of the squares of its sides. In other words: if c is the length of the hypotenus, a,b are the length of the other sides, then c2 = a2 + b2.
It turns out that the Pythagorean Theorem is itself a proof for the existence of irrational numbers. For example, if a=1, b = 1, then c = √2. Here in lies one of the most famous irrational numbers.
Theorem: if p is a prime then √p is irrational.
(1) Assume that there exists two values a,b such that: a/b = √p and such that a,b are the lowest positive fraction such that gcd(a,b)=1.
NOTE: We know that in fractions, if a,b had any common factors, then we could divide them off and still maintain the same ratio.
(2) Then a2/b2 = p and therefore a2 = pb2.
(3) So, we see that p divides a. So there exists a value a' such that a=pa'. [This is true by Euclid's Lemma since p is a prime and it divides either a or a]
(4) So, we get (pa')2 = pb2 which means that p2a'2 = pb2.
(5) Dividing both sides by p, we get: pa'2 = b2.
(6) But now we see that p divides b (again by Euclid's Lemma). This is a contradiction since a,b do not have any common divisors so we can reject our initial assumption.
QED
Lemma 1: if α is irrational, a,b are rational, and b ≠ 0, then a + bα is irrational
(1) Let x = a + bα
(2) bα = x - a
(3) α = (x - a)/b
(4) Now, this proves that x is not rational. Since if x is rational, then (x-a)/b would be rational, but this is impossible since (x-a)/b = α which is irrational.
QED
Lemma 2: if α is irrational, then 1/α is irrational
(1) Let y = 1/α
(2) Then, α = 1/y.
(3) This proves that y is not rational. If it were, then 1/y would be rational but it isn't since 1/y = α which is irrational.
QED
Lemma 3: if a,b are rational and α is irrational, and a + bα is rational, then a=b=0.
(1) By Lemma 1 above, if a + bα is rational, then b = 0.
(2) Since a + bα = 0 we know that a = 0 - bα = 0 - 0 = 0
QED
Lemma 4: For any positive real number ε, there exists a positive irrational number that is less than ε
Proof:
(1) Let p be a prime such that √p is greater than 1/ε [We can make this assumption based on Euclid's Theorem about infinite primes, see here]
(2) By the Theorem above, we know that √p is an irrational number.
(3) Now, if based on step #1, we know that:
1/√p is less than ε
(4) We also know that 1/√p is an irrational number from Lemma 2 above.
QED
Corollary 4.1: For any two distinct rational numbers, there exists an irrational number that is in between.
Proof:
(1) Let x,y be two distinct rational numbers where x is greater than y.
(2) We can see that if ε is any positive number less than x - y, then, y + ε lies in between x and y.
(3) By Lemma 4 above, we know that there exists an irrational number α that is less than ε.
(4) Further, we know that y + α is also irrational [by Lemma 1 above] and we know that y + α lies in between x and y.
QED
It turns out that the Pythagorean Theorem is itself a proof for the existence of irrational numbers. For example, if a=1, b = 1, then c = √2. Here in lies one of the most famous irrational numbers.
Theorem: if p is a prime then √p is irrational.
(1) Assume that there exists two values a,b such that: a/b = √p and such that a,b are the lowest positive fraction such that gcd(a,b)=1.
NOTE: We know that in fractions, if a,b had any common factors, then we could divide them off and still maintain the same ratio.
(2) Then a2/b2 = p and therefore a2 = pb2.
(3) So, we see that p divides a. So there exists a value a' such that a=pa'. [This is true by Euclid's Lemma since p is a prime and it divides either a or a]
(4) So, we get (pa')2 = pb2 which means that p2a'2 = pb2.
(5) Dividing both sides by p, we get: pa'2 = b2.
(6) But now we see that p divides b (again by Euclid's Lemma). This is a contradiction since a,b do not have any common divisors so we can reject our initial assumption.
QED
Lemma 1: if α is irrational, a,b are rational, and b ≠ 0, then a + bα is irrational
(1) Let x = a + bα
(2) bα = x - a
(3) α = (x - a)/b
(4) Now, this proves that x is not rational. Since if x is rational, then (x-a)/b would be rational, but this is impossible since (x-a)/b = α which is irrational.
QED
Lemma 2: if α is irrational, then 1/α is irrational
(1) Let y = 1/α
(2) Then, α = 1/y.
(3) This proves that y is not rational. If it were, then 1/y would be rational but it isn't since 1/y = α which is irrational.
QED
Lemma 3: if a,b are rational and α is irrational, and a + bα is rational, then a=b=0.
(1) By Lemma 1 above, if a + bα is rational, then b = 0.
(2) Since a + bα = 0 we know that a = 0 - bα = 0 - 0 = 0
QED
Lemma 4: For any positive real number ε, there exists a positive irrational number that is less than ε
Proof:
(1) Let p be a prime such that √p is greater than 1/ε [We can make this assumption based on Euclid's Theorem about infinite primes, see here]
(2) By the Theorem above, we know that √p is an irrational number.
(3) Now, if based on step #1, we know that:
1/√p is less than ε
(4) We also know that 1/√p is an irrational number from Lemma 2 above.
QED
Corollary 4.1: For any two distinct rational numbers, there exists an irrational number that is in between.
Proof:
(1) Let x,y be two distinct rational numbers where x is greater than y.
(2) We can see that if ε is any positive number less than x - y, then, y + ε lies in between x and y.
(3) By Lemma 4 above, we know that there exists an irrational number α that is less than ε.
(4) Further, we know that y + α is also irrational [by Lemma 1 above] and we know that y + α lies in between x and y.
QED
Monday, December 19, 2005
Review of Matrices
In today's blog, I will review some very basic results in 2x2 and 1x2 matrices.
This represents a very basic introduction that is meant to provide background for my larger blog on Fermat's Last Theorem: n = 5 (see here).
Today's blog is based on the work by Harold M. Stark in his book An Introduction to Number Theory.
1. Matrix defined
A matrix is a grouping of numbers that allows working on all the numbers at the same time.
For example, let's consider a 2 x 2 matrix that can be based on a set of numbers: 1, 2, 3, 4.
The matrix itself looks like this:
2. Addition and subtraction of matrices
Addition and subtraction of matrices are exactly the same as if you added and subtracted the numbers independently:
3. Multiplication of Numbers with Matrices
Multiplication with an integer just applies the integer to all the values involved so that:
4. Product of Two Matrices
In addition to these properites, matrices have there own special operations. The product of 2 matrices is a bit confusing. We define a product of a 1 x 2 matrix with a 2 x 2 matrix as the following:
We define a product a 2 x 2 matrix with a 2 x 2 matrix as the following:
Now, here's where it gets a bit confusing. We normally refer to a matrix using a capital letter. So let's say we have two matrices A,B such that: A is a 2x2 matrix and B is a 2x2 matrix. We cannot assume that AB = BA. For example, if we reverse the matrices above, we get the following equation:
Another important point is that there is no product defined for a 2x1 matrix and a 2x2 matrix or a 2x2 matrix and 1x2 matrix (since order is important in matrix products) and for that matter, there is no product defined a 2x2 matrix with a 1x2 matrix. In the case of 2x2 matrices, you can only get a product for a 2x2 matrix with a 2x2 matrix or a 1x2 matrix with a 2x2 matrix.
5. Determinant
A determinant is a value that is derived from a 2x2 matrix. Here is the definition:
Lemma 1: det(AB) = (detA)(detB)
(1) Let A =
Let B =
(2) AB =
(3) det(AB) = (ae+bg)(cf+dh) - (af+bh)(ce+dg) = (acef + adeh + bcfg + bdgh) - (acef + adfg + bceh + bdgh) = adeh + bcfg - adfg - bceh.
(4) det(A) = ad - bc
(5) det(B) = eh - fg
(6) So det(A)det(B) = (ad - bc)(eh - fg) = adeh + bcfg - adfg - bceh
QED
6. Identity Matrix
The Identity Matrix is referred to as I and defined as:
Lemma 2: AI = IA = A
(1) Let A =
(2) AI =
(3) IA =
QED
7. Inverse
Let A =
We denote the inverse of A as A-1 and we define it as:
A-1 =
Lemma 2: AA-1 = A-1A = I
(1)
(2)
QED
Lemma 3: det A-1 = 1/(det A)
(1) (det A)(det A-1) = det(AA-1) [From Lemma 1]
(2) det(AA-1) = det(I) [From Lemma 2]
(3) det(I) = 1*1 - 0*0 = 1. [Definition of I, Definition of Determinant]
(4) So, (det A)(det A-1) = 1
(5) And dividing both sides by (det A) gives us:
det A-1 = 1/(det A)
QED
7. Final Points
The last point here is that while AA-1 = I, it is not necessarily true that ABA-1 = B. The reason is that AB does not necessarily equal BA and we are not allowed to change the order of the matrix elements.
This represents a very basic introduction that is meant to provide background for my larger blog on Fermat's Last Theorem: n = 5 (see here).
Today's blog is based on the work by Harold M. Stark in his book An Introduction to Number Theory.
1. Matrix defined
A matrix is a grouping of numbers that allows working on all the numbers at the same time.
For example, let's consider a 2 x 2 matrix that can be based on a set of numbers: 1, 2, 3, 4.
The matrix itself looks like this:
2. Addition and subtraction of matrices
Addition and subtraction of matrices are exactly the same as if you added and subtracted the numbers independently:
3. Multiplication of Numbers with Matrices
Multiplication with an integer just applies the integer to all the values involved so that:
4. Product of Two Matrices
In addition to these properites, matrices have there own special operations. The product of 2 matrices is a bit confusing. We define a product of a 1 x 2 matrix with a 2 x 2 matrix as the following:
We define a product a 2 x 2 matrix with a 2 x 2 matrix as the following:
Now, here's where it gets a bit confusing. We normally refer to a matrix using a capital letter. So let's say we have two matrices A,B such that: A is a 2x2 matrix and B is a 2x2 matrix. We cannot assume that AB = BA. For example, if we reverse the matrices above, we get the following equation:
Another important point is that there is no product defined for a 2x1 matrix and a 2x2 matrix or a 2x2 matrix and 1x2 matrix (since order is important in matrix products) and for that matter, there is no product defined a 2x2 matrix with a 1x2 matrix. In the case of 2x2 matrices, you can only get a product for a 2x2 matrix with a 2x2 matrix or a 1x2 matrix with a 2x2 matrix.
5. Determinant
A determinant is a value that is derived from a 2x2 matrix. Here is the definition:
Lemma 1: det(AB) = (detA)(detB)
(1) Let A =
Let B =
(2) AB =
(3) det(AB) = (ae+bg)(cf+dh) - (af+bh)(ce+dg) = (acef + adeh + bcfg + bdgh) - (acef + adfg + bceh + bdgh) = adeh + bcfg - adfg - bceh.
(4) det(A) = ad - bc
(5) det(B) = eh - fg
(6) So det(A)det(B) = (ad - bc)(eh - fg) = adeh + bcfg - adfg - bceh
QED
6. Identity Matrix
The Identity Matrix is referred to as I and defined as:
Lemma 2: AI = IA = A
(1) Let A =
(2) AI =
(3) IA =
QED
7. Inverse
Let A =
We denote the inverse of A as A-1 and we define it as:
A-1 =
Lemma 2: AA-1 = A-1A = I
(1)
(2)
QED
Lemma 3: det A-1 = 1/(det A)
(1) (det A)(det A-1) = det(AA-1) [From Lemma 1]
(2) det(AA-1) = det(I) [From Lemma 2]
(3) det(I) = 1*1 - 0*0 = 1. [Definition of I, Definition of Determinant]
(4) So, (det A)(det A-1) = 1
(5) And dividing both sides by (det A) gives us:
det A-1 = 1/(det A)
QED
7. Final Points
The last point here is that while AA-1 = I, it is not necessarily true that ABA-1 = B. The reason is that AB does not necessarily equal BA and we are not allowed to change the order of the matrix elements.
Monday, October 10, 2005
Basic Lemmas Needed for FLT: n = 5
Here are some basic lemmas that are used by the proof for Fermat's Last Theorem: n=5.
Lemma 1: (p+q)5 + (p-q)5 = 2p(p4 + 10p2q2 + 5q4)
(1) Using the Binomial Theorem:
(p + q)5 = p5 + 5p4q + 10p3q2 + 10p2q3 + 5pq4 + q5
(p - q)5 = p5 - 5p4q + 10p3q2 - 10p2q3 + 5pq4 - q5
(2) Adding these two values together gives us:
2p5 + 20p3q2 + 10pq4 = 2p(p4 + 10p2q2 + 5q4)
QED
Lemma 2:
If:
t = q4 + 50q2r2 + 125r4
u = q2 + 25r2
v = 10r2
Then:
t = u2 - 5v2
(1) u2 = (q2 + 25r2)2 = q4 + 50q2 r2 + 625r4
(2) -5v2 = -5(10r2)2 = -500r4
(3) (q2 + 25r2)2 + -5(10r2)2 = q4 + 50q2 r2 + 625r4 + -500r4 = q4 + 50q2 r2 + 125r4
QED
Lemma 1: (p+q)5 + (p-q)5 = 2p(p4 + 10p2q2 + 5q4)
(1) Using the Binomial Theorem:
(p + q)5 = p5 + 5p4q + 10p3q2 + 10p2q3 + 5pq4 + q5
(p - q)5 = p5 - 5p4q + 10p3q2 - 10p2q3 + 5pq4 - q5
(2) Adding these two values together gives us:
2p5 + 20p3q2 + 10pq4 = 2p(p4 + 10p2q2 + 5q4)
QED
Lemma 2:
If:
t = q4 + 50q2r2 + 125r4
u = q2 + 25r2
v = 10r2
Then:
t = u2 - 5v2
(1) u2 = (q2 + 25r2)2 = q4 + 50q2 r2 + 625r4
(2) -5v2 = -5(10r2)2 = -500r4
(3) (q2 + 25r2)2 + -5(10r2)2 = q4 + 50q2 r2 + 625r4 + -500r4 = q4 + 50q2 r2 + 125r4
QED
Sunday, October 09, 2005
Some Simple Division Lemmas
In this blog, I want to outline some simple implications of the division which are very useful in basic mathematical reasoning:
Lemma 1:
If:
(a) c = a + b
(b) d divides a
(c) d divides b
Then:
d divides c
(1) By assumption (b) and (c), we know that there exists a',b' such that:
a = a'd
b = b'd
(2) So,
c = (a'd) + (b'd) = d(a' + b')
Lemma 2:
If
(a) c = a + b
(b) d divides c
(c) d divides a
Then
d divides b
(1) c = a + b → b = c -a = c + (-a)
(2) This results follows from Lemma 1 above.
Lemma 1:
If:
(a) c = a + b
(b) d divides a
(c) d divides b
Then:
d divides c
(1) By assumption (b) and (c), we know that there exists a',b' such that:
a = a'd
b = b'd
(2) So,
c = (a'd) + (b'd) = d(a' + b')
Lemma 2:
If
(a) c = a + b
(b) d divides c
(c) d divides a
Then
d divides b
(1) c = a + b → b = c -a = c + (-a)
(2) This results follows from Lemma 1 above.
Monday, September 19, 2005
Mathematical Induction
Mathematical induction is a method for proving a condition is true of an infinite set that obeys the well-ordering principle.
A set is considered well-ordered if for any subset of elements, one can always find one element which is the smallest. An example of a well-ordered set is the set of positive integers. One element is clearly the smallest. For example, if 1 is an element in the set, then it will be the smallest element.
Not all sets are well-ordered. For example, negative integers are not well-ordered. In such an infinite set, there is never one element which is the smallest. Likewise, real numbers are not a well-ordered set. For any number, it is possible to find another number which is smaller if only by a fraction. There is no smallest value.
It is useful to introduce some notation when talking about well-ordered sets. Sets are often refered to as capital letters such as S, T, R. Elements are often refered to as lowercase letters such as s,t,r.
We can imagine that s is an element of S, t is an element of T, and r is an element of R. Likewise, we can use a subscript to differentiate elements so that s1, s2, etc. are all elements of S. t1, t2, etc. are all elements of T.
When talking about induction, we are always trying to prove some proposition true about an entire set. When talking about a proposition or fact, I will use the following form p(). So, for example, p(s1) means that the proposition is true of the first element of the set S. Likewise p(S) means that the proposition is true of all elements of set S.
Finally, I need to use the concept of implication which is symbolized by →. Implication doesn't say something is true or false. Rather, it describes a relationship. If a certain condition is true, then another condition follows. If I were president, I would be living in Washington, D.C. This doesn't mean that I am president and it doesn't mean that if I am living in Washington, D.C., then I am the president. It simply means that if the first condition were true (if I were the president), then the second condition would follow (then I would live in Washington, D.C.).
With this notation, I can now state the Principle of Mathematical Induction:
Theorem: Principle of Mathematical Induction: if p(s1) is true and if p(sn) → p(sn+1), then p(S).
(1) Let's start by assuming that the theorem is false.
(2) Let's let si be the first element in order where p(si) is not true.
(3) Well i cannot be the first element since we are assuming that p(s1) is true.
(4) So, this means that p(si-1) must be true since i is the first element where the proposition is not true.
(5) But if p(sn) is true, then p(sn+1) is true, so therefore p(si) must be true since p(si-1) is true.
(6) But this is a contradiction so we reject (1) and conclude that the theorem is true.
QED
A set is considered well-ordered if for any subset of elements, one can always find one element which is the smallest. An example of a well-ordered set is the set of positive integers. One element is clearly the smallest. For example, if 1 is an element in the set, then it will be the smallest element.
Not all sets are well-ordered. For example, negative integers are not well-ordered. In such an infinite set, there is never one element which is the smallest. Likewise, real numbers are not a well-ordered set. For any number, it is possible to find another number which is smaller if only by a fraction. There is no smallest value.
It is useful to introduce some notation when talking about well-ordered sets. Sets are often refered to as capital letters such as S, T, R. Elements are often refered to as lowercase letters such as s,t,r.
We can imagine that s is an element of S, t is an element of T, and r is an element of R. Likewise, we can use a subscript to differentiate elements so that s1, s2, etc. are all elements of S. t1, t2, etc. are all elements of T.
When talking about induction, we are always trying to prove some proposition true about an entire set. When talking about a proposition or fact, I will use the following form p(). So, for example, p(s1) means that the proposition is true of the first element of the set S. Likewise p(S) means that the proposition is true of all elements of set S.
Finally, I need to use the concept of implication which is symbolized by →. Implication doesn't say something is true or false. Rather, it describes a relationship. If a certain condition is true, then another condition follows. If I were president, I would be living in Washington, D.C. This doesn't mean that I am president and it doesn't mean that if I am living in Washington, D.C., then I am the president. It simply means that if the first condition were true (if I were the president), then the second condition would follow (then I would live in Washington, D.C.).
With this notation, I can now state the Principle of Mathematical Induction:
Theorem: Principle of Mathematical Induction: if p(s1) is true and if p(sn) → p(sn+1), then p(S).
(1) Let's start by assuming that the theorem is false.
(2) Let's let si be the first element in order where p(si) is not true.
(3) Well i cannot be the first element since we are assuming that p(s1) is true.
(4) So, this means that p(si-1) must be true since i is the first element where the proposition is not true.
(5) But if p(sn) is true, then p(sn+1) is true, so therefore p(si) must be true since p(si-1) is true.
(6) But this is a contradiction so we reject (1) and conclude that the theorem is true.
QED
Tuesday, August 30, 2005
Useful Equations
I thought it would be useful to review some basic equations. These are presented as a series of lemmas.
Lemma 1: (a + b)2 = a2 + 2ab + b2
(a + b)2 = (a + b)(a + b) = a(a + b) + b(a + b) = a2 + ab + ab + b2 = a2 + 2ab + b2.
QED
Lemma 2: (a + b)(a - b) = a2 - b2
(a + b)(a - b) = a(a - b) + b(a - b) = a2 - ab + ab - b2 = a2 - b2
Corollary 2.1: a4 - b4 = (a - b)(a + b)(a2 + b2)
By Lemma 2, a4 - b4 = (a2 - b2)(a2 + b2)
Applying Lemma 2 again, gives us:
a4 - b4 = (a - b)(a + b)(a2 + b2)
Lemma 3: a3 + b3 = (a + b)(a2 - ab + b2)
(a + b)(a2 - ab + b2 ) = a(a2 - ab + b2) + b(a2 - ab + b2) =
a3 - a2b + ab2 + a2b -ab2 + b3 = a3 + b3
Corollary 3.1: a3 - b3 = (a - b)(a2 + ab + b2)
Let b' = -b so that a3 - b3 = a3 + (b')3
By Lemma 3: a3 + (b')3 = (a + b')(a2 - ab' + (b')2) = (a - b)(a2 + ab + b2)
QED
Lemma 4: a5 + b5 = (a + b)(a4 - a3b +a2b2 - ab3 + b4)
(a + b)(a4 - a3b +a2b2 - ab3 + b4) =
=a(a4 - a3b +a2b2 - ab3 + b4) + b(a4 - a3b +a2b2 - ab3 + b4) =
=a5 - a4b + a3b2 - a2b3 + ab4 + a4b - a3b2 + a2b3 - ab4 + b5 =
=a5 + b5
QED
Lemma 4: n ≥ 5 → an + bn = (a + b)(a(n-1) - a(n-2)b + ... - ab(n-2) + b(n-1))
(a + b)(a(n-1) - a(n-2)b + ... -ab(n-2) + b(n-1)) =
a(a(n-1) - a(n-2)b + a(n-3)b2... -ab(n-2) + b(n-1)) +
b(b(n-1)+a(n-1) - a(n-2)b + ...+a2b(n-3) -ab(n-2)) =
an - a(n-1)b + a(n-2)b2 + ... -a2b(n-2) + ab(n-1) +
bn + a(n-1)b - a(n-2)b2 + ... + a2b(n-2) - ab(n-1) =
an + bn
QED
Lemma 5: a - b divides an - bn
Proof:
(1) Let n = be the highest number where this is true.
(2) We know that n is at least 2 since a2 - b2 = (a - b)(a + b)
(3) To complete this proof, we need to show that a - b divides an+1 - bn+1
(4) We know that (a-b)(an) = an+1 - anb and we know that (a-b)(bn) = abn - bn+1
(5) So that an+1 - bn+1 - (a - b)(an) - (a-b)(bn) = anb - abn = ab(an-1 - bn-1)
(6) So that:
an+1 - bb+1 = (a-b)(an + bn) - ab(an-1 - bn-1)
(7) Since n ≥ 2, we know that a-b divides an-1 - bn-1.
QED
Lemma 1: (a + b)2 = a2 + 2ab + b2
(a + b)2 = (a + b)(a + b) = a(a + b) + b(a + b) = a2 + ab + ab + b2 = a2 + 2ab + b2.
QED
Lemma 2: (a + b)(a - b) = a2 - b2
(a + b)(a - b) = a(a - b) + b(a - b) = a2 - ab + ab - b2 = a2 - b2
Corollary 2.1: a4 - b4 = (a - b)(a + b)(a2 + b2)
By Lemma 2, a4 - b4 = (a2 - b2)(a2 + b2)
Applying Lemma 2 again, gives us:
a4 - b4 = (a - b)(a + b)(a2 + b2)
Lemma 3: a3 + b3 = (a + b)(a2 - ab + b2)
(a + b)(a2 - ab + b2 ) = a(a2 - ab + b2) + b(a2 - ab + b2) =
a3 - a2b + ab2 + a2b -ab2 + b3 = a3 + b3
Corollary 3.1: a3 - b3 = (a - b)(a2 + ab + b2)
Let b' = -b so that a3 - b3 = a3 + (b')3
By Lemma 3: a3 + (b')3 = (a + b')(a2 - ab' + (b')2) = (a - b)(a2 + ab + b2)
QED
Lemma 4: a5 + b5 = (a + b)(a4 - a3b +a2b2 - ab3 + b4)
(a + b)(a4 - a3b +a2b2 - ab3 + b4) =
=a(a4 - a3b +a2b2 - ab3 + b4) + b(a4 - a3b +a2b2 - ab3 + b4) =
=a5 - a4b + a3b2 - a2b3 + ab4 + a4b - a3b2 + a2b3 - ab4 + b5 =
=a5 + b5
QED
Lemma 4: n ≥ 5 → an + bn = (a + b)(a(n-1) - a(n-2)b + ... - ab(n-2) + b(n-1))
(a + b)(a(n-1) - a(n-2)b + ... -ab(n-2) + b(n-1)) =
a(a(n-1) - a(n-2)b + a(n-3)b2... -ab(n-2) + b(n-1)) +
b(b(n-1)+a(n-1) - a(n-2)b + ...+a2b(n-3) -ab(n-2)) =
an - a(n-1)b + a(n-2)b2 + ... -a2b(n-2) + ab(n-1) +
bn + a(n-1)b - a(n-2)b2 + ... + a2b(n-2) - ab(n-1) =
an + bn
QED
Lemma 5: a - b divides an - bn
Proof:
(1) Let n = be the highest number where this is true.
(2) We know that n is at least 2 since a2 - b2 = (a - b)(a + b)
(3) To complete this proof, we need to show that a - b divides an+1 - bn+1
(4) We know that (a-b)(an) = an+1 - anb and we know that (a-b)(bn) = abn - bn+1
(5) So that an+1 - bn+1 - (a - b)(an) - (a-b)(bn) = anb - abn = ab(an-1 - bn-1)
(6) So that:
an+1 - bb+1 = (a-b)(an + bn) - ab(an-1 - bn-1)
(7) Since n ≥ 2, we know that a-b divides an-1 - bn-1.
QED
Factorials
A factorial is an equation that is abbreviated by a number followed by an ! such as:
2!
The idea behind a factorial is very simple. It is a shorthand for a series of multiplications where each multiple is one less than the previous value.
For example:
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
Factorials are often used in problems of permutations.
Let's start with a situation where we won't need factorials. Assuming that we have 5 roles and 5 people and each person can take any role and can take as many roles as they want. How many different permutations are there?
There are 5 ways to divide up the first role, 5 ways to divide up the second role, and so on. The answer turns out to be: 5 * 5 * 5 *5 *5 = 55 [If you need a review of exponents, review here]
What if we say that each person can only take one role. In other words, we are taking 5 people and dividing them up into 5 roles. In this case, the following happens:
There are 5 ways to divide up the first role, but only 4 ways to divide up the second role, and then 3 ways to divide up the third role, etc. The answer turns out to be 5 * 4 * 3 * 2 * 1 = 5!.
We can generalize this point and make it into an exact equation. For any set of n elements,
there are exactly n! ways of ordering it. This is easy to show.
Lemma 1: For a set of n elements, there are n! ways of ordering all n elements.
For the first element, we have n possible choices.
For the second element, we have n-1 possible choices.
And so on until we get the last element and we have only 1 choice.
So, the total number of thoices is n * (n-1) * (n-2) * ... * 1 which equals n!
QED
Lemma 2: For a set of n elements, there are n!/(n-m)! ways to to order m elements.
(1) There are two cases that need to be considered.
Case I: m = n
Case II: m is less than n
(2) For m = n, we know that there are n! ways to order the elements (Lemma 1)
n!/(n-n)! = n!/(0!) = n!/1 = n!. (Note: 0! is defined to equal 1)
This proves Case I.
(3) For m is less than n, we start by dividing all combinations by the first m elements.
(4) When we do this, we find that for each m sequence of elements, there are (n-m)! ways to select the remaining elements after we have selected the first m elements. (Lemma 1)
(5) Now, if each of these groups have (n-m)! elements, then we can get the total number of groups by diving n! by this value, that is: n!/(n-m)!.
QED
Lemma 3: For a set of n elements, there are n!/[m!(n-m)!] ways to select an unordered set.
(1) We can prove this using the same two cases:
Case I: m = n
Case II: m is less than n
(2) For Case I, there is only 1 way to select n items from a set of n elements.
n!/[n!(n-n)!] = n!/[n!0!] = n!/n! = 1.
(3) For case II, we take our n!/(n-m)! sets and organize them into groups where they have the same set of elements. For example, if we had 3 elements, would group {1,2,3} in the same group as {2,1,3} and {3,1,2} and {3,2,1}.
(4) For each group of m elements, there are m! ways to order them (Lemma 1)
(5) This means that the total number of groups in (3) is [n!/(n-m)!]/m! which is mathematically the same as: n!/[m!(n-m)!].
QED
Factorials are also used in the very important Binomial Theorem which I will talk about in a future blog.
2!
The idea behind a factorial is very simple. It is a shorthand for a series of multiplications where each multiple is one less than the previous value.
For example:
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
Factorials are often used in problems of permutations.
Let's start with a situation where we won't need factorials. Assuming that we have 5 roles and 5 people and each person can take any role and can take as many roles as they want. How many different permutations are there?
There are 5 ways to divide up the first role, 5 ways to divide up the second role, and so on. The answer turns out to be: 5 * 5 * 5 *5 *5 = 55 [If you need a review of exponents, review here]
What if we say that each person can only take one role. In other words, we are taking 5 people and dividing them up into 5 roles. In this case, the following happens:
There are 5 ways to divide up the first role, but only 4 ways to divide up the second role, and then 3 ways to divide up the third role, etc. The answer turns out to be 5 * 4 * 3 * 2 * 1 = 5!.
We can generalize this point and make it into an exact equation. For any set of n elements,
there are exactly n! ways of ordering it. This is easy to show.
Lemma 1: For a set of n elements, there are n! ways of ordering all n elements.
For the first element, we have n possible choices.
For the second element, we have n-1 possible choices.
And so on until we get the last element and we have only 1 choice.
So, the total number of thoices is n * (n-1) * (n-2) * ... * 1 which equals n!
QED
Lemma 2: For a set of n elements, there are n!/(n-m)! ways to to order m elements.
(1) There are two cases that need to be considered.
Case I: m = n
Case II: m is less than n
(2) For m = n, we know that there are n! ways to order the elements (Lemma 1)
n!/(n-n)! = n!/(0!) = n!/1 = n!. (Note: 0! is defined to equal 1)
This proves Case I.
(3) For m is less than n, we start by dividing all combinations by the first m elements.
(4) When we do this, we find that for each m sequence of elements, there are (n-m)! ways to select the remaining elements after we have selected the first m elements. (Lemma 1)
(5) Now, if each of these groups have (n-m)! elements, then we can get the total number of groups by diving n! by this value, that is: n!/(n-m)!.
QED
Lemma 3: For a set of n elements, there are n!/[m!(n-m)!] ways to select an unordered set.
(1) We can prove this using the same two cases:
Case I: m = n
Case II: m is less than n
(2) For Case I, there is only 1 way to select n items from a set of n elements.
n!/[n!(n-n)!] = n!/[n!0!] = n!/n! = 1.
(3) For case II, we take our n!/(n-m)! sets and organize them into groups where they have the same set of elements. For example, if we had 3 elements, would group {1,2,3} in the same group as {2,1,3} and {3,1,2} and {3,2,1}.
(4) For each group of m elements, there are m! ways to order them (Lemma 1)
(5) This means that the total number of groups in (3) is [n!/(n-m)!]/m! which is mathematically the same as: n!/[m!(n-m)!].
QED
Factorials are also used in the very important Binomial Theorem which I will talk about in a future blog.
Saturday, August 06, 2005
Modular Arithmetic
Modular arithmetic is a notation and set of mathematics that were first introduced by Carl Friedrich Gauss.
The major insight is that equations can fruitfully be analyzed from the perspective of remainders. Standard equations use the '=' sign. Modular arithmetic uses the '≡' sign. Two values that are '≡' to each other are said to be congruent relative the modulus. In the case below, the modulus is 3.
Here's an example of a modular equation:
7 ≡ 1 (mod 3).
By definition, this means that 3 divides 7 - 1.
Here's a more formal definition of a modular equation:
Definition 1: a ≡ b (mod c) if and only if c divides a - b.
This definition tells us the following is true:
7 ≡ 1 ≡ 10 ≡ -2 (mod 3).
Now, one of the most interesting things about '≡' is that it follows many of the same relations as '='.
Lemma 1: For any value a,b,c,d,n where a ≡ b (mod n) and c ≡ d (mod n):
(a) a + c ≡ b + d (mod n)
(b) a - c ≡ b - d (mod n)
(c) ac ≡ bd (mod n)
(1) n divides a - b, and n divides c - d. [definition of ≡ ]
(2) We know that n divides (a + c) - (b + d) since this is equal to: (a -b) + (c - d).
(3) We know that n divides (a - c) - (b - d) since this is equal to: (a - b) - (c - d).
(4) We know that n divides ac - bd since this is equal to : c(a - b) + b(c - d).
QED
Lemma 2: If a ≡ b (mod n) then:
(a) a + c ≡ b + c (mod n)
(b) a - c ≡ b - c (mod n)
(c) ac ≡ bc (mod n)
(1) So, we are given that n divides a - b.
(2) We know (a) since n divides a + c - (b + c) = a - b.
(3) We know (b) since n divides a - c - (b - c) = a - b.
(4) We know (c) since n divides ac - bc = c(a - b)
QED
Corrolary 2.1: a ≡ d (mod n), b ≡ e (mod n), c ≡ f (mod n), then:
a + b + c ≡ d + e + f.
(1) We know that a + b ≡ d + e from above.
(2) We therefore know that (a + b) + c ≡ (d + e) + f.
QED
Lemma 3: a + b + c ≡ 0, a ≡ 0 (mod p), then b + c ≡ 0 (mod p).(1) a + b + c ≡ 0 (mod p) [Definition of ≡ ]
(2) b ≡ c (mod p) → a + b ≡ a + c (mod p) [See above]
(3) So, 0 ≡ a + b + c ≡ 0 + b + c ≡ b + c (mod p).
QED
Lemma 4: if gcd(k,p)=1 and kx ≡ ky (mod p), then x ≡ y (mod p)
Proof:
(1) Since kx ≡ ky (mod p), there exists a such that ap = kx - ky = k(x-y)
(2) Since gcd(k,p)=1, it follows that p divides (x-y)
(3) So that x ≡ y (mod p)
QED
The major insight is that equations can fruitfully be analyzed from the perspective of remainders. Standard equations use the '=' sign. Modular arithmetic uses the '≡' sign. Two values that are '≡' to each other are said to be congruent relative the modulus. In the case below, the modulus is 3.
Here's an example of a modular equation:
7 ≡ 1 (mod 3).
By definition, this means that 3 divides 7 - 1.
Here's a more formal definition of a modular equation:
Definition 1: a ≡ b (mod c) if and only if c divides a - b.
This definition tells us the following is true:
7 ≡ 1 ≡ 10 ≡ -2 (mod 3).
Now, one of the most interesting things about '≡' is that it follows many of the same relations as '='.
Lemma 1: For any value a,b,c,d,n where a ≡ b (mod n) and c ≡ d (mod n):
(a) a + c ≡ b + d (mod n)
(b) a - c ≡ b - d (mod n)
(c) ac ≡ bd (mod n)
(1) n divides a - b, and n divides c - d. [definition of ≡ ]
(2) We know that n divides (a + c) - (b + d) since this is equal to: (a -b) + (c - d).
(3) We know that n divides (a - c) - (b - d) since this is equal to: (a - b) - (c - d).
(4) We know that n divides ac - bd since this is equal to : c(a - b) + b(c - d).
QED
Lemma 2: If a ≡ b (mod n) then:
(a) a + c ≡ b + c (mod n)
(b) a - c ≡ b - c (mod n)
(c) ac ≡ bc (mod n)
(1) So, we are given that n divides a - b.
(2) We know (a) since n divides a + c - (b + c) = a - b.
(3) We know (b) since n divides a - c - (b - c) = a - b.
(4) We know (c) since n divides ac - bc = c(a - b)
QED
Corrolary 2.1: a ≡ d (mod n), b ≡ e (mod n), c ≡ f (mod n), then:
a + b + c ≡ d + e + f.
(1) We know that a + b ≡ d + e from above.
(2) We therefore know that (a + b) + c ≡ (d + e) + f.
QED
Lemma 3: a + b + c ≡ 0, a ≡ 0 (mod p), then b + c ≡ 0 (mod p).(1) a + b + c ≡ 0 (mod p) [Definition of ≡ ]
(2) b ≡ c (mod p) → a + b ≡ a + c (mod p) [See above]
(3) So, 0 ≡ a + b + c ≡ 0 + b + c ≡ b + c (mod p).
QED
Lemma 4: if gcd(k,p)=1 and kx ≡ ky (mod p), then x ≡ y (mod p)
Proof:
(1) Since kx ≡ ky (mod p), there exists a such that ap = kx - ky = k(x-y)
(2) Since gcd(k,p)=1, it follows that p divides (x-y)
(3) So that x ≡ y (mod p)
QED
Wednesday, July 27, 2005
Euclidean Coprime Integers: xn + yn = zn
In a previous blog, I showed that given rational integers x,y,z such that:
xn + yn = zn
We can assume that x,y,z are relatively prime. See here for the details.
It turns out that we can make the same statement about all Euclidean Integers. For those not familiar with Euclidean Integers, please review here.
Lemma 1: For Euclidean Integers, relatively prime divisors of n-powers are themselves n-powers.
This theorem says that if gcd(v,w) = 1 and vw = zn
Then, there exists x,y such that v = xn, w = yn
(1) So, we start with gcd(v,w) = 1, vw = zn
(2) Assume that v is not equal to any number xn
(3) v ≠ 1 since 1 is an xn power
(4) Now, v is divisible by a prime number p. [Fundamental Theorem of Arithmetic for Euclidean Integers]
(5) So, there exists k such that v = pk
(6) p divides z since zn = vw = pkw [By applying Euclid's Lemma for Euclidean Integers]
(7) So, there exists m such that z=pm
(8) So, zn = vw = pkw = (pm)n = pnmn
(9) Dividing p from both sides gives us:
kw = p(n-1)mn
(10) From Euclid's Lemma, p divides k or w.
(11) It can't divide w since it already divides v and gcd(v,w)=1. Therefore, it divides k
(12) We can apply this same argument for each p in p(n-1)
(13) So, we can conclude that p(n-1) divides k.
(14) So, there exists V such that k = p(n-1)*V
(15) So, kw = p(n-1)mn = p(n-1)*V*w
(16) Dividing p(n-1) from both sides gives us:
vW = mn
(17) Now, gcd(V,w)=1 since V is a divisor of v and gcd(v,w) = 1
(18) Likewise, V cannot be an n-power. If it were, then v = pnV would make v an n-power which goes against our assumption.
(19) Finally, V is less than v since p(n-1) > 1.
(20) Thus, we have a contradiction by infinite descent.
QED
Lemma 2: Given xn + yn = zn and x,y,z are Euclidean Integers, we can assume that x,y,z are relatively prime.
To prove this, we will need to prove two things:
(1) If a factor divides any two values of this equation, then the n-power of it divides the n-power of the third value.
(2) If an n-power of a factor divides the n-power of a value, then the factor divides the value itself.
Step 1: For xn + yn = zn, the n-power of any common factor of two divides the n-power of the third.
Case I: Let's assume d divides x, d divides y
(1) There exists x', y' such that: x = d(x'), y = d(y')
(2) zn = xn + yn = (dx')n + (dy')n
= dn(x')n + dn(y')n
= dn[(x')n + (y')n]
Case II: Let's assume d divides z and d divides x or d divides y
(1) Let's assume d divides x (the same argument will work for y)
(2) There exists x', z' such that: x = d(x'), z = d(z')
(3) We now say yn = zn - xn
(4) We can now follow the same reasoning as above.
QED
Step 2: dn divides xn → d divides x
(1) Let c be the greatest common denominator (gcd) for d,x.
(2) Let D = d / c, X = x / c.
(3) Now the gcd of (X,D) = 1. [See here for the proof.]
(4) So, the gcd of (Xn,Dn) = 1.
(5) We know that there exists k such that xn = k * dn [Since dn divides xn ]
(6) Applying (2), we get (cX)n = k*(cD)n
(7) Which gives us: cnXn = k * cnDn
(8) Dividing cn from each side gives: Xn = Dn*k
(9) Now it follows that gcd(Dn,k) = 1.
(11) Which means that there exists u such that un = k.
(12) And we get Dn * un = Zn
(13) And (Du)n = Zn
(14) Implying that Du = Z and multiplying by c that du=z.
(15) Which proves that d divides z.
QED
xn + yn = zn
We can assume that x,y,z are relatively prime. See here for the details.
It turns out that we can make the same statement about all Euclidean Integers. For those not familiar with Euclidean Integers, please review here.
Lemma 1: For Euclidean Integers, relatively prime divisors of n-powers are themselves n-powers.
This theorem says that if gcd(v,w) = 1 and vw = zn
Then, there exists x,y such that v = xn, w = yn
(1) So, we start with gcd(v,w) = 1, vw = zn
(2) Assume that v is not equal to any number xn
(3) v ≠ 1 since 1 is an xn power
(4) Now, v is divisible by a prime number p. [Fundamental Theorem of Arithmetic for Euclidean Integers]
(5) So, there exists k such that v = pk
(6) p divides z since zn = vw = pkw [By applying Euclid's Lemma for Euclidean Integers]
(7) So, there exists m such that z=pm
(8) So, zn = vw = pkw = (pm)n = pnmn
(9) Dividing p from both sides gives us:
kw = p(n-1)mn
(10) From Euclid's Lemma, p divides k or w.
(11) It can't divide w since it already divides v and gcd(v,w)=1. Therefore, it divides k
(12) We can apply this same argument for each p in p(n-1)
(13) So, we can conclude that p(n-1) divides k.
(14) So, there exists V such that k = p(n-1)*V
(15) So, kw = p(n-1)mn = p(n-1)*V*w
(16) Dividing p(n-1) from both sides gives us:
vW = mn
(17) Now, gcd(V,w)=1 since V is a divisor of v and gcd(v,w) = 1
(18) Likewise, V cannot be an n-power. If it were, then v = pnV would make v an n-power which goes against our assumption.
(19) Finally, V is less than v since p(n-1) > 1.
(20) Thus, we have a contradiction by infinite descent.
QED
Lemma 2: Given xn + yn = zn and x,y,z are Euclidean Integers, we can assume that x,y,z are relatively prime.
To prove this, we will need to prove two things:
(1) If a factor divides any two values of this equation, then the n-power of it divides the n-power of the third value.
(2) If an n-power of a factor divides the n-power of a value, then the factor divides the value itself.
Step 1: For xn + yn = zn, the n-power of any common factor of two divides the n-power of the third.
Case I: Let's assume d divides x, d divides y
(1) There exists x', y' such that: x = d(x'), y = d(y')
(2) zn = xn + yn = (dx')n + (dy')n
= dn(x')n + dn(y')n
= dn[(x')n + (y')n]
Case II: Let's assume d divides z and d divides x or d divides y
(1) Let's assume d divides x (the same argument will work for y)
(2) There exists x', z' such that: x = d(x'), z = d(z')
(3) We now say yn = zn - xn
(4) We can now follow the same reasoning as above.
QED
Step 2: dn divides xn → d divides x
(1) Let c be the greatest common denominator (gcd) for d,x.
(2) Let D = d / c, X = x / c.
(3) Now the gcd of (X,D) = 1. [See here for the proof.]
(4) So, the gcd of (Xn,Dn) = 1.
(5) We know that there exists k such that xn = k * dn [Since dn divides xn ]
(6) Applying (2), we get (cX)n = k*(cD)n
(7) Which gives us: cnXn = k * cnDn
(8) Dividing cn from each side gives: Xn = Dn*k
(9) Now it follows that gcd(Dn,k) = 1.
(a) Assume gcd(Dn,k) = a, a > 1(10) So, we can conclude that k is an n-power. [By the lemma above]
(b) Then, a divides Dn and Xn [From 8]
(c) But gcd(Dn,Xn) ≠ 1.
(d) But this contradicts (4)
(e) So, we reject our assumption.
(11) Which means that there exists u such that un = k.
(12) And we get Dn * un = Zn
(13) And (Du)n = Zn
(14) Implying that Du = Z and multiplying by c that du=z.
(15) Which proves that d divides z.
QED
Euclid's Method for the Greatest Common Denominator
The greatest common denominator (gcd) is the largest common factor shared by two or more positive integers. In the case of 4,2 the greatest common denominator is 2. Since all integers are divisible by 1, the greatest common denominator of any two integers is guaranteed to be at least 1. If the gcd of two integers is 1, those integers are said to be relatively prime or coprime. In other words, they do not have any common divisors.
It is perhaps obvious on the face there exists a gcd for any two integers and there exists a method for finding this value. Here is the proof. The method for finding the greatest common denominator is found in Euclid's Elements and is therefore known today as Euclid's algorithm. Here is a link to Euclid's proof in the Elements.
But what about quadratic integers? What about Gaussian Integers or Eisenstein Integers? (for those not familiar with quadratic integers, refer to here).
It turns out that if there is a division algorithm available, then for any two integers, there is necessarily a greatest common denominator. In other words, we can prove that Euclid's method for finding the gcd applies. Here is the proof (note: in the example referenced, it refers to Gaussian Integers, but the same proof applies to Eisenstein Integers and other types of quadratic integers that are characterized by a division algorithm).
For this reason, all quadratic integers that are characterized by a division algorithm are said to be Euclidean.
One result of this is that for any two Euclidean integers (quadratic integers that have a division algorithm) that are not relatively prime, it is possible to derive two smaller integers which are relatively prime.
Lemma: gcd(x,y)=d is greater than 1 → there exists X,Y such that x = Xd, y = Yd and gcd(X,Y)=1.
(1) Assume that gcd(X,Y) = D which is greater than 1.
(2) Then D divides X,Y such that there exists X = DX', Y=DY'
(3) And x = DX'd, y = DY'd
(4) So that Dd divides both x and y.
(5) But Dd > d which is impossible since d is the greatest common divisor.
(6) So we reject (1).
QED
Corollary: This result holds for all quadratic integers that are Euclidean.
This is true since the result only depends on the gcd which we showed above holds for all Euclidean Integers.
QED
Lemma: gcd(x,y)=1 → gcd(xn,yn)=1.
(1) Assume that gcd(xn,yn) = d which is greater than 1.
(2) Since d is greater than 1, there must exist a prime p that divides d. [See here for the proof of Fundamental Theorem of Arithmetic]
(3) if p divides xn, then p divides x. [See here for the proof of Euclid's Generalized Lemma]
(4) For the same reason, p would also divide y.
(5) But this is a contradiction since gcd(x,y)=1.
(6) So we reject (1).
QED
Corollary: This holds true for all Euclidean Integers
This proof depends on a proof for unique factorization and Euclid's Generalized Lemma.
(1) Euclid's Generalized Lemma holds true for all Euclidean Integers. [See here for proof].
(2) Unique Factorization holds true for all Euclidean Integers. [See here for proof].
QED
It is perhaps obvious on the face there exists a gcd for any two integers and there exists a method for finding this value. Here is the proof. The method for finding the greatest common denominator is found in Euclid's Elements and is therefore known today as Euclid's algorithm. Here is a link to Euclid's proof in the Elements.
But what about quadratic integers? What about Gaussian Integers or Eisenstein Integers? (for those not familiar with quadratic integers, refer to here).
It turns out that if there is a division algorithm available, then for any two integers, there is necessarily a greatest common denominator. In other words, we can prove that Euclid's method for finding the gcd applies. Here is the proof (note: in the example referenced, it refers to Gaussian Integers, but the same proof applies to Eisenstein Integers and other types of quadratic integers that are characterized by a division algorithm).
For this reason, all quadratic integers that are characterized by a division algorithm are said to be Euclidean.
One result of this is that for any two Euclidean integers (quadratic integers that have a division algorithm) that are not relatively prime, it is possible to derive two smaller integers which are relatively prime.
Lemma: gcd(x,y)=d is greater than 1 → there exists X,Y such that x = Xd, y = Yd and gcd(X,Y)=1.
(1) Assume that gcd(X,Y) = D which is greater than 1.
(2) Then D divides X,Y such that there exists X = DX', Y=DY'
(3) And x = DX'd, y = DY'd
(4) So that Dd divides both x and y.
(5) But Dd > d which is impossible since d is the greatest common divisor.
(6) So we reject (1).
QED
Corollary: This result holds for all quadratic integers that are Euclidean.
This is true since the result only depends on the gcd which we showed above holds for all Euclidean Integers.
QED
Lemma: gcd(x,y)=1 → gcd(xn,yn)=1.
(1) Assume that gcd(xn,yn) = d which is greater than 1.
(2) Since d is greater than 1, there must exist a prime p that divides d. [See here for the proof of Fundamental Theorem of Arithmetic]
(3) if p divides xn, then p divides x. [See here for the proof of Euclid's Generalized Lemma]
(4) For the same reason, p would also divide y.
(5) But this is a contradiction since gcd(x,y)=1.
(6) So we reject (1).
QED
Corollary: This holds true for all Euclidean Integers
This proof depends on a proof for unique factorization and Euclid's Generalized Lemma.
(1) Euclid's Generalized Lemma holds true for all Euclidean Integers. [See here for proof].
(2) Unique Factorization holds true for all Euclidean Integers. [See here for proof].
QED
Friday, July 22, 2005
Division Algorithm
One of the most important and underappreciated theorems is the Division Algorithm. You can usually find it in any book on number theory as Theorem 1. The proof for the Division Algorithm for Integers can be found here.
It states that for any given integer and nonzero divisor, there exists two unique integers: a quotient and a remainder where the remainder is smaller than the divisor.
Perhaps this theorem gets underappreciated because it is so obvious. It does not seem on the surface that there is anything surprising about this statement. Likewise, the proof, when it is first seen, may appear to the amateur like an exercise in the obvious.
The standard division algorithm for rational integers (positive and negative whole numbers) is based on the Well Ordering Principle.
And yet, there are subtleties regarding this theorem that have important implications for the theory of numbers. Consider the situation where we add imaginary numbers (numbers in which -1 has a square root known as i, that is, i2 = -1.
When a mathematician looks at a problem like x2 + y2, it would be really convenient if there was an easy way to factor it. If we extend integers to include Z[i], then we can. In this case, we have the following factor (note: Z[i] is used to define an extended set set of integers. These are integers that have the form a + bi where a,b are rational integers):
(x - iy)(x + iy) = x2 + y2.
And, then the question arises, are integers of the type Z[i] characerized by a Division Algorithm? If they are, we need a new proof because the Well-Ordering Principle only applies to rational integers.
The path to a Division Algorithm requires the introduction of a special function known as a norm. It applies to any Z[α] value where α2 is a rational integer (such as i). It is based on the very simple identity:
(a - b)(a + b) = a2 - b2
Since we know that α2 is rational integer, we know that there exists a value c such that c = α2.
So, let us assume that we have an integer of the form a + bα. If we multiply it with its conjugate (an equivalent value where we change the sign), then we get:
(a + bα)(a - bα) = a2 - cb2.
If we had a value of a - bα, then its conjugate would be a + bα. In either case, we have found a function that maps any Z[α] integer to a rational integer.
With this function in place, we can prove for that given any Gaussian Integer and a nonzero divisor, there exists two unique values: a quotient and a remainder where the absolute norm of the remainder is smaller than the absolute norm of the divisor. Here is the proof.
We might ask if we will always find a division algorithm for all possible values of α.
Let us consider this question with respect to quadratic integers. These are integers of the form Z[α] where α is a irrational solution to an equation of the form x2 + bx + c = 0 where x = α and b,c are rational integers (an irrational number is any number that is not equal to a rational fraction. For example -3/4 is rational since it is a ratio of -3 to 4. i on the other hand is not rational).
In this situation, it turns out there are only 21 different nonsquare values where Z[α] has a division algorithm (by nonsquare, I am excluding values such as Z[√-4] because 4 is a square of 2 and √-4 = 2i.
The 21 values are based on: -11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37,41, 57, and 73.
Now, here's one more of the subtleties. It turns out that the form of this integer depends on the remainder when the number is divided by 4. If the remainder is any value but 1, then the form is simple: Z[√-2], Z[i], Z[√2],Z[√3], Z[√6],Z[√7],Z[√11], Z[√19].
If the remainder with 4 is 1, then the value takes a stranger form: Z[(-1 + √-11)/2], Z[(-1 + √-7)/2], Z[(-1 + √-3)/2], Z[(-1 + √5)/2], Z[(-1 + √13)/2], Z[(-1 + √17)/2],
Z[(-1 + √21)/2], Z[(-1 + √29)/2], Z[(-1 + √33)/2]. The details for why these values have this form can be found here.
The proof that many of these values are characterized by a Division Algorithm can be found here.
It states that for any given integer and nonzero divisor, there exists two unique integers: a quotient and a remainder where the remainder is smaller than the divisor.
Perhaps this theorem gets underappreciated because it is so obvious. It does not seem on the surface that there is anything surprising about this statement. Likewise, the proof, when it is first seen, may appear to the amateur like an exercise in the obvious.
The standard division algorithm for rational integers (positive and negative whole numbers) is based on the Well Ordering Principle.
And yet, there are subtleties regarding this theorem that have important implications for the theory of numbers. Consider the situation where we add imaginary numbers (numbers in which -1 has a square root known as i, that is, i2 = -1.
When a mathematician looks at a problem like x2 + y2, it would be really convenient if there was an easy way to factor it. If we extend integers to include Z[i], then we can. In this case, we have the following factor (note: Z[i] is used to define an extended set set of integers. These are integers that have the form a + bi where a,b are rational integers):
(x - iy)(x + iy) = x2 + y2.
And, then the question arises, are integers of the type Z[i] characerized by a Division Algorithm? If they are, we need a new proof because the Well-Ordering Principle only applies to rational integers.
The path to a Division Algorithm requires the introduction of a special function known as a norm. It applies to any Z[α] value where α2 is a rational integer (such as i). It is based on the very simple identity:
(a - b)(a + b) = a2 - b2
Since we know that α2 is rational integer, we know that there exists a value c such that c = α2.
So, let us assume that we have an integer of the form a + bα. If we multiply it with its conjugate (an equivalent value where we change the sign), then we get:
(a + bα)(a - bα) = a2 - cb2.
If we had a value of a - bα, then its conjugate would be a + bα. In either case, we have found a function that maps any Z[α] integer to a rational integer.
With this function in place, we can prove for that given any Gaussian Integer and a nonzero divisor, there exists two unique values: a quotient and a remainder where the absolute norm of the remainder is smaller than the absolute norm of the divisor. Here is the proof.
We might ask if we will always find a division algorithm for all possible values of α.
Let us consider this question with respect to quadratic integers. These are integers of the form Z[α] where α is a irrational solution to an equation of the form x2 + bx + c = 0 where x = α and b,c are rational integers (an irrational number is any number that is not equal to a rational fraction. For example -3/4 is rational since it is a ratio of -3 to 4. i on the other hand is not rational).
In this situation, it turns out there are only 21 different nonsquare values where Z[α] has a division algorithm (by nonsquare, I am excluding values such as Z[√-4] because 4 is a square of 2 and √-4 = 2i.
The 21 values are based on: -11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37,41, 57, and 73.
Now, here's one more of the subtleties. It turns out that the form of this integer depends on the remainder when the number is divided by 4. If the remainder is any value but 1, then the form is simple: Z[√-2], Z[i], Z[√2],Z[√3], Z[√6],Z[√7],Z[√11], Z[√19].
If the remainder with 4 is 1, then the value takes a stranger form: Z[(-1 + √-11)/2], Z[(-1 + √-7)/2], Z[(-1 + √-3)/2], Z[(-1 + √5)/2], Z[(-1 + √13)/2], Z[(-1 + √17)/2],
Z[(-1 + √21)/2], Z[(-1 + √29)/2], Z[(-1 + √33)/2]. The details for why these values have this form can be found here.
The proof that many of these values are characterized by a Division Algorithm can be found here.
Wednesday, June 15, 2005
Fractions
A fraction is any ratio between whole numbers. In mathematical terms, it is called a rational number. An irrational number is any number such as π which cannot be represented as the ratio of two whole numbers.
In today's blog, I will go over a single lemma regarding fractions:
Lemma: for any given rational number let's say a/b, there exists an integer let's say c such that: absolute(a/b - c) ≤ (1/2).
(1) To prove this, we need only consider the case where abs(a) is greater abs(b). [If abs(a) ≤ abs(b), then the conclusion follows from Corollary 2.1, here]
(2) From the division algorithm (see Theorem 1, here), we know that a = bq + r where r ≥ 0 and less than abs(b).
[For example, if a=-3, b=-2, then q=2, r=1 where r is greater than b but less than abs(b).]
(3) Let a'=abs(a), b'=abs(b)
(4) We know that a' - b'q is less than b' (since a' - b'q = r and r is less than b')
(5) So, it follows that: a'/b' - q is less than 1.
(6) Now, if both a,b are positive or a,b are negative, it follows that a/b = a'/b' and abs(a/b - q) is less than 1.
(7) If a,b are of different sign, than -a/b = a'/b' and -a/b - q = -(a/b + q) so that abs(a/b + q) is less than 1.
(8) The conclusion follows from Lemma 2, here.
QED
Corollary: if a/b is a rational number, then there exists an integer c such that: absolute(a/b - c/2) ≤ (1/4).
(1) From the lemma above, we know that for 2*(a/b), there exists a number c such that:
abs(2*(a/b) - c) ≤ (1/2).
(2) Dividing both sides by 2, gives us:
abs(a/b - c/2) ≤ (1/4)
QED
Now, it turns out that any number with a repeating decimal can be represented as a rational number.
Let me start with an example
(1) Let's assume that we have a decimal such as 5.234523452345... We can represent this decimal as a repeating decimal such as 5.2345.
(2) Now, we know if we multiply the number by 104 we get:
52345.2345
(3) So, subtracting (2) by (1) gives us:
104 - 1 = 52345 - 5 = 52340.
(4) So, the rational form of this repeating decimal is:
52340/9999.
Now, let's look at the proof that demonstrates this:
Lemma: Any number with a repeating decimal is rational.
(1) Any number with a repeating decimal can be represented with the following form:
d1...dm.a1...an
NOTE: If a number has a nonrepeating portion, then we multiply this number by the number of nonrepeating digits, to get a number of the above form. Later, we divide our result by this same number.
(2) We can get an integer result by subtracting 10n*the number by the original number which after canceling for the repeating decimal gives us:
10n * (d1...dm.a1...an...) - (d1...dm.a1...an...) =
(d1..dma1..an) - (d1..dm).
(3) Now, our rational number is equal to the value in step #2 divided by 10n - 1.
QED
In today's blog, I will go over a single lemma regarding fractions:
Lemma: for any given rational number let's say a/b, there exists an integer let's say c such that: absolute(a/b - c) ≤ (1/2).
(1) To prove this, we need only consider the case where abs(a) is greater abs(b). [If abs(a) ≤ abs(b), then the conclusion follows from Corollary 2.1, here]
(2) From the division algorithm (see Theorem 1, here), we know that a = bq + r where r ≥ 0 and less than abs(b).
[For example, if a=-3, b=-2, then q=2, r=1 where r is greater than b but less than abs(b).]
(3) Let a'=abs(a), b'=abs(b)
(4) We know that a' - b'q is less than b' (since a' - b'q = r and r is less than b')
(5) So, it follows that: a'/b' - q is less than 1.
(6) Now, if both a,b are positive or a,b are negative, it follows that a/b = a'/b' and abs(a/b - q) is less than 1.
(7) If a,b are of different sign, than -a/b = a'/b' and -a/b - q = -(a/b + q) so that abs(a/b + q) is less than 1.
(8) The conclusion follows from Lemma 2, here.
QED
Corollary: if a/b is a rational number, then there exists an integer c such that: absolute(a/b - c/2) ≤ (1/4).
(1) From the lemma above, we know that for 2*(a/b), there exists a number c such that:
abs(2*(a/b) - c) ≤ (1/2).
(2) Dividing both sides by 2, gives us:
abs(a/b - c/2) ≤ (1/4)
QED
Now, it turns out that any number with a repeating decimal can be represented as a rational number.
Let me start with an example
(1) Let's assume that we have a decimal such as 5.234523452345... We can represent this decimal as a repeating decimal such as 5.2345.
(2) Now, we know if we multiply the number by 104 we get:
52345.2345
(3) So, subtracting (2) by (1) gives us:
104 - 1 = 52345 - 5 = 52340.
(4) So, the rational form of this repeating decimal is:
52340/9999.
Now, let's look at the proof that demonstrates this:
Lemma: Any number with a repeating decimal is rational.
(1) Any number with a repeating decimal can be represented with the following form:
d1...dm.a1...an
NOTE: If a number has a nonrepeating portion, then we multiply this number by the number of nonrepeating digits, to get a number of the above form. Later, we divide our result by this same number.
(2) We can get an integer result by subtracting 10n*the number by the original number which after canceling for the repeating decimal gives us:
10n * (d1...dm.a1...an...) - (d1...dm.a1...an...) =
(d1..dma1..an) - (d1..dm).
(3) Now, our rational number is equal to the value in step #2 divided by 10n - 1.
QED
Subscribe to:
Posts
(
Atom
)