# Monthly Archives: February 2012

## Math Exam ( just a poem )

## Coprime Numbers: More Results

In this blog, I will review some basic results regarding coprime numbers.

**Lemma 1: p,q coprime -> pq, p ^{2} – q^{2} are coprime.**

(1) Assume **gcd(pq,p ^{2} – q^{2}) = d** and

**d**is greater than

**1**

(2) So, there is some prime **P** which divides **d** [Fundamental Theorem of Artihmetic]

(3) Since **d** divides **pq**. **P** either divides **p** or **q**. [Euclid’s Lemma]

(4) Let’s assume **P** divides **p** and the same argument will apply if it divides **q**. So that, there exists**R** such that **p = PR**.

(5) Since **d** divides **p ^{2} – q^{2}**, there exists a value

**Q**such that

**p**

^{2}– q^{2}= PQ(6) This means that **q ^{2} = p^{2} – PQ = (PR)^{2} – PQ = P(PR^{2} – Q)**.

(7) But this means that **P** divides **q** by Euclid’s Lemma which is a contradiction since **P** also divides **p**. [Because **gcd(p,q)=1**]

(8) Therefore, we reject our assumption.

QED

Lemma 2: p,q are relatively prime and are of different parity (one is odd, one is even), then p + q, p – q are relatively prime.

(1) Assume that gcd(p+q,p-q) = d and d is greater than 1.

(2) Then there exists a prime x which divides d. [Fundamental Theorem of Arithmetic]

(3) We know that this x is odd since p+q and p-q are odd. [Since they are of different parity]

(4) Now x divideds 2p since 2p = (p + q) + (p – q) which means x divides p. [By Euclid’s LemmaSince x is odd]

(5) Likewise x divides 2q since 2q = (p + q) – (p – q) = p + q – p + q which means x divides q. [Same reason as above]

(6) But this is a contradiction since p,q are relatively prime.

QED

**Lemma 3: if S ^{2} = P^{2} + Q^{2} and P^{2} = T^{2} + Q^{2}, then Q,S,T are relatively prime.**

(1) We can assume that **S,P,Q** are relatively prime and **P,T,Q** are relatively prime. [See Lemma 1,here for details]

(2) We can also assume that **S,P** are odd which means that **Q** is even and that **T** is odd. [See details above]

(3) From the two equations, we can derive that:

**S ^{2} = T^{2} + 2Q^{2}**

(4) Now we need only prove that any factor that divides 2 values, will divide the third.

Case I: **f** divides **S,Q**

(a) There exists **s,q** such that **S = fs, Q = fq**

(b) **T ^{2} = S^{2} – 2Q^{2} = f^{2} [ s^{2} – 2q^{2} ]**

(c) Which means that

**f**divides

**T**[See here.]

Case II: **f** divides **T,Q**

(a) We can use the same argument as Case I.

Case III: **f** divides **S,T**

(a) There exists **s,t** such that **S = fs, T = ft**

(b) **2Q ^{2} = f^{2}[ s^{2} – t^{2} ]**

(c) Since

**S,T**are odd,

**f**must be odd and

**s,t**must be odd.

(d) Then,

**s**must be even.

^{2}– t^{2}(e) Then, there exists

**u**such that

**2u = s**

^{2}– t^{2}(f) So, we have:

**2Q**

^{2}= (2)u(f^{2})(g) And canceling out the

**2s**gives us:

**Q**

^{2}= f^{2}uQED

**Lemma 4: S,T relatively prime, both odd, 2u = S – T, 2v = S + T, then u,v are relatively prime.**

(1) Assume **f** divides **u,v** such that **u = fU, v = fV**.

(2) The **f **divides **S**

**S – T + S + T = 2S = 2u + 2v = 2f(U + V)**

(3) And **f** divides **T**

**S + T – (S – T) = 2T = 2v – 2u = 2f(V – U)l.**

(4) This contradicts our **S,T** beings coprime so we reject our assumption.

QED

## Fundamental Theorem Of Arithmetic

Before, we can provide this theorem, we will need an initial theorem on division and one lemma which will we borrow from Euclid.

Theorem 1: Division Algorithm for Integers

This theorem shows that given any two integers, there exist a unique divisor and a unique remainder.

(1) Let S be a set such that { a – bc : c is an integer and a-bc ≥ 0}

(2) S is not empty.

Case I: b divides a

In this case, then there exists a c where a – bc = 0. Therefore, 0 is an element of this set.

Case II: b doesn’t divide a

In this case, there exists an c where a – bc has a remainder is greater than 0. This remainder is then an element of this set.

(3) Then, then there exists d such that d is the smallest element of the set. [Well Ordering Principle]

(4) We know that d is less than **b**.

(a) Assume that d is greater than or equal to b.

(b) Then d – b is greater than or equal to 0.

(c) Since

d – b = (a – bc) – b = a – bc – b = a – b(c+1)

(d) We conclude that a – b(c+1) must be an element of S.

(e) But a – b(c+1) is less than **d**

(f) Which is a contradiction since d is the smallest element from step #3.

(5) Finally, for any a,b, the lowest value d and the remainder c are unique.

(a) Assume C,D are integers that can be derived from a,b.

a = bc + d, d is greater than 0 and less than b.

a = bC + D, D is greater than 0 and less than b.

(b) So

bc + d = bC + D –> b(c – C) = d – D

(c) Which means that b divides (d – D).

(d) Since d – D is less than **b**, we know d – D = 0 and that d = D.

(e) Which gives us b(c – C) = 0 or that c – C = 0.

(f) We can therefore conclude that c = C.

QED

Lemma 2: Euclid’s Lemma

This lemma shows that given a prime that divides a product, either it divides one value or it divides the other.

(1) Let’s assume a prime p divides a product ab.

(2) Let’s assume that p does not divide a.

(3) Then gcd(p,a)=1. [See blog on Greatest Common Denominators for details]

(4) There exists s,t such that 1 = as + pt. [See blog on Greatest Common Denominators]

(5) Multiplying both sides with b gives us:

b(1) = b(as + pt) = b = abs + ptb

(6) Since p divides ab, there exists k such that ab = pk.

(7) Combining with (5), we get

b = pks + ptd = p(ks + td).

QED

We can also tag on a corollary.

Corollary 2.1: Generalized Euclid’s Lemma

The idea here is that if a prime divides a product of n elements, then it is necessarily divides at least one of those elements.

(1) Let’s assume that we have a product of n elements.

a = a_{1} * a_{2} * … * a_{n}

(2) We can take any one of these elements and get:

a = a_{1} * (a_{2} * … * a_{n})

(3)So, by Euclid’s Lemma (see Lemma 2 above), the prime either divides a_{1} or one of the rest of the elements.

(4) So, either it divides a_{1} or a_{2} etc.

(5) And we get to the last two elements, we are done by Euclid’s Lemma.

QED

Theorem 3: Fundamental Theorem of Arithmetic

This theorem proves that each integer greater than 1 is the product of a unique set of primes.

(1) Let S be a set S of {primes or products of primes > 1}.

(2) 2 is an element of S since 2 is prime.

(3) From (1), (2) there exists a value n which is 3 or greater where all values less than n and greater or equal to 2 are in S.

(4) If n is a prime, then it is a member of S.

(5) If n is not a prime, then it is also a member of S.

(a) If n is not a prime, then there exist a,b such that n=ab where **a,b** are greater than **1** and less than **n**. [Definition of a prime]

(b) But a,b must be elements of S since they are less than n. [From step #3 above]

(c) Then, n must also be a member of S since n is a product of two numbers which are either primes or products of primes.

(6) Now, all the primes that make up n are necessarily unique.

(a) Let **n = p _{1} * p_{2} * … p_{r} = q_{1} * q_{2} * … q_{s}** where p,q are all primes.

(b) Let’s start with **p _{1}**

(c) Either **p _{1}** divides

**q**or

_{1}**q**or someother value. [see Euclid’s Generalized Lemma above]

_{2}(d) Likewise, each value **p _{r}** can be matched by some value

**q**.

_{s}(e) In other words, they must necessarily be the same combination.

QED

## greatest common divisor

The Greatest Common Divisor or **gcd** is the largest common factor between two numbers. In what follows, I will write this as function such as **gcd(9,6) = 3**. The **gcd** cannot be applied to **0**.

For example, the **gcd(2,4) = 2** and **gcd(5,7)=1**.

One assumption that I will use below is the **Well Ordering Principle.**

**Postulate 1: Well Ordering Principle**

For any set of positive integers, one value is the lowest.

For a small set of numbers, this principle is clearly true.

For the set of all negative numbers, it is not true. No matter which negative number we choose, we can always find another negative number which is lower.

For the set of all positive numbers, it is true. It is **1**. Likewise, it is true for all subsets of this set.

This principle is normally called a **postulate**. A postulate is an assumption that mathematicians use without proof. It is the foundation of a proof.

**Lemma 1: Bezout’s Identity: If gcd(a,b) = c, then there exists s,t such that: c = as + bt.**

(1) Let **S** be a set **{ am + bn : m,n are integers, am + bn > 0 }**

In other words, let **S** be the set of all sums that can be created from **am + bn**. This includes (1)m + (1)n, (2)m + (1)n, etc. It includes any combination. So, we can also assume that (1000)m + (99)n are elements of this set if the sum is greater than 0.

(2) This set is not empty

In other words, for any **a**, **b**, we know that there is at least one element in this set.

If **a + b > 0**, then choose **m=1,n=1**.

If **a + b = 0**, then either **a** or **b** is negative. Let’s assume **a**. Then choose **m=-1,n=1**.

If **a + b** is less than **0**, then either **a** or **b** is the lowest. Let’s assume **a**. Then choose **m=-1,n=1**.

(3) We know that one of these elements in the set is the smallest. [By the Well Ordering Principle]

(4) Let’s call the smallest element **d**.

(5) **d** divides both **a,b**.

I will now show that **d** divides **a**. The same argument will also apply to **b**.

We know that there exists **q,r** such that **a = dq + r **where **r** is a positive integer less than **d**. [By the Division Algorithm]

In other words, **q** is the quotient and **r** is the remainder.

**r = a – dq = a – (as + bt)q = a – asq – btq = a(1 – sq) – btq = a(1-sq) + b(-tq).**

Assume that **r > 0**.

Then a(1 – sq) + b(-tq) is an element of the above set.

But this is a contradiction. **d** is the lowest element and yet here is an element smaller than **d**.

So, **r = 0**.

(6) **d** is the **gcd** for **a,b**.

Let **d’** **= gcd(a,b)**

Let’s define **h,k: a = d’h, b = d’k**

So, **d = as + bt = (d’h)s + (d’k)t = d'(hs + kt)**

Which means **d’ **divides **d**.

So, **d’ = d** since **d’** is the gcd.

QED

Lemma 2: For all pairs of numbers, it is possible to reduce them to a form that is coprime.

(1) Assume that we have two numbers: x, y that are not coprime.

(2) Then there exists d such that d = gcd(x,y) and d > 1.

(3) Then there exists X,Y such that x = dX, y = dY.

(4) And finally, gcd(X,Y)=1

(a) Assume gcd(X,Y) = D and D > 1

(b) Then there exists a,b such that X = aD, Y = bD.

(c) And x = d(aD), y = d(bD)

(d) From this, we see that dD divides both x and y.

(e) We also know dD > d since d > 1 and D > 1.

(f) But this is a condradiction since d is the greatest common denominator.

(g) So we reject our assumption.

QED

## CoPrime Numbers : x^n + y^n = z^n

This post is about the equation:

**x^{n} + y^{n}= z^{n}**

I will show that given any three integers that satisfy this equation, either:

(a) all three of them are coprime with each other

or

(b) it is possible to cancel out common components and derive three numbers that are coprime.

Two numbers are coprime if they do not share any common divisors.

**Definition 1: Coprime**

Two numbers

x,yare said to becoprimeif and only ifddividesx, ddividesy -> d = 1Two numbers

x,yare said to not becoprimeif and only if there exists a valued > 1such thatddividesx, ddividesy

Now, here’s the proof that was promised:

**Lemma: We can reduce any solution to x ^{n} + y^{n} = z^{n} to a form where x,y,z are coprime.**

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 x^{n} + y^{n} = z^{n}, 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) z^{n} = x^{n} + y^{n} = (dx’)^{n} + (dy’)^{n}

= d^{n}(x’)^{n} + d^{n}(y’)^{n}

= d^{n}[(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 y^{n} = z^{n} – x^{n}

(4) We can now follow the same reasoning as above.

QED

**Step 2: d ^{n} divides x^{n} → 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 explanation]

(4) So, the gcd of **(X ^{n},D^{n}) = 1**.

(5) We know that there exists

**k**such that

**x**[Since

^{n}= k * d^{n}**d**divides

^{n}**x**]

^{n}(6) Applying (2), we get

**(cX)**

^{n}= k*(cD)^{n}(7) Which gives us:

**c**

^{n}X^{n}= k * c^{n}D^{n}(8) Dividing

**c**from each side gives:

^{n}**X**

^{n}= D^{n}*k(9) Now it follows that gcd(

**D**) =

^{n},k**1**.

(a) Assume gcd(D

^{n},k) = a, a > 1

(b) Then,adivides D^{n}and X^{n}[From 8]

(c) But gcd(D^{n},X^{n}) ≠ 1.

(d) But this contradicts (4)

(e) So, we reject our assumption.

(10) So, we can conclude that **k** is an n-power. [See blog on Infinite Descent for the proof]

(11) Which means that there exists **u** such that **u ^{n} = k**.

(12) And we get

**D**

^{n}* u^{n}= X^{n}(13) And

**(Du)**

^{n}= X^{n}(14) Implying that

**Du = X**and multiplying by

**c**that

**du=x**.

(15) Which proves that

**d**divides

**x**.

QED

## Exponents

### Exponents

**1. Introduction to Exponents**

An exponent is an elegant shorthand for multiplication.Instead of 5 * 5 * 5, you can write 5

^{3}

Instead of 3 * 3 * 3 * 3 * 3 * 3 * 3, you can write 3^{7}

The number that gets multiplied is called the base. The number of multiplications that occur is called the power. So, in the above example, 3 is the base and 7 is the power.

Of course, this method only applies when the power is a positive integer. Later on, I will discuss what it means when a power is 0, positive, or even a fraction.

So 4^{2} = 4 * 4 = 16

And 4^{3} = 4 * 4 * 4 = 64

And 4^{1} = 4 = 4

2. x and y notation

In mathematics, when we want to talk about “any”, we use a letter such as x or y or **z**. For example, if we wanted to say that **1** to any power equals **1**, we could write this as follows:

1^{x} = 1

Using x-and-y notation, we can create a definition for the positive exponents.

Definition 1: Positive Exponents

xmeans^{y}xmultiplied with itselfytimes.

xis called thebase

yis called thepower

**3. Multiplication of Exponents**

Multiplying exponents of the same base can be determined based on the above definition.

4^{2} * 4^{3} =

= (4 * 4) * (4 * 4 * 4)

= 4 * 4 * 4 * 4 * 4

= 4^{5}

So, when exponents get multiplied, if they have the same base, you can add the powers and create a new exponent.

Here are some more examples:

5^{5} * 5^{10} = 5^{15}

2^{10} * 2^{1000} = 2^{1010}

Of course, this does not work if two exponents have a different base.

In mathematics, a method such as this can be presented as a theorem. A theorem is any statement that can be derived from previous results.

In this case, we are able to prove a theorem regarding the method of adding the powers of the same base. Here’s the theorem

Theorem 1: x^{y} * x^{z} = x^{(y+z)}^{
}

(1) We know that x

^{y}= x multipled to itself y times and that x^{z}= x multipled to itself z times. (Definition of Positive Exponents).

(2) Multiplying all those x’s, we have (y + z) x’s multiplied together.

(3) Now x multiplied to itself (x + z) times = x^{(y + z)}by the Definition of Positive Exponents.QED

QED is put at the end of a proof to show it is done. It is an abbreviation for a latin phrase that means basically that the proof is finished. It serves the same purpose in a proof as a period does in a sentence.

4. Division of Exponents

To talk about division, it is useful to introduce the following definition:

Definition 2: Division

a = b / c means a is equal to b divided by c.

a is refered to as the quotient.

b is refered to as the dividend.

c is refered to as the divisor.

Division with exponents of the same base can also be determined based on the definition for positive exponents:

4^{2} / 4^{1} =

= ( 4 * 4 ) / ( 4 ) =

= 16 / 4 = 4

= 4^{1}

To divide two exponents of the same base, you simply subtract the two powers.

Here are some examples:

5^{3} / 5^{1} = 5^{2}

4^{10} / 4^{5} = 4^{5
}

Now, what happens if we are dividing by a number greater than the top (in other words, where thedivisor is greater than the dividend)? In this case, we are left with a fraction.

5^{1} / 5^{3} = 1 / 5^{2}

4^{5} / 4^{10} = 1 / 5^{5}

This leads us to a third definition:

Definition 3: Negative Exponents

x

^{(-y)}means that we have a fraction of 1 over x multiplied by itself y times.

Here are some examples.

5^{-1} = 1 / 5

4^{-3} = 1 / 4^{3}

And what happens if the subtraction results in 0?

We can answer this with the following theorem:

**Theorem 2: x ^{0} = 1**

(1) By basic arithemitic, we know that

x^{0}= x^{(1 – 1)}

(2) Since 1 – 1 = 1 + (-1), we can rewrite this as:

x^{(1 + -1)}

(3) Now x^{(1 + -1)}= x^{1}* x^{(-1)}by Theorem 1.

(4) Now,x, by Definition 3.^{(-1)}= 1/x

(5) So, we are left withx * (1/x) = 1QED

We can also introduce a corollary to this theorem. A corollary is a small proof that is derived directly from the logic of a theorem.

Corollary 2.1: x^{0} = 1 implies that x ≠ 0

(1) Now

x^{0}= x^{(1 – 1)}

(2) Which means thatx^{0}= x / x

(3) But this implies that x ≠ 0 since division by 0 is not allowed.QED

Another way of saying this result is that 0^{0} just like 0/0 or even 1/0 is undefined.

We can summarize division of exponents with the following theorem.

**Theorem 3: x ^{y} / x^{z} = x^{(y – z)}**

Case I:

y = zIn this case

x.^{y}/ x^{z}= 1 = x^{0}= x^{(y – z)}Case II:

y > zIn division, we are able to cancel out all the common factors. Since

y > z, we cancel out z factors from both dividend and divisor and we are left withx.^{(y-z)}Case III:

y < z

Again, we cancel out common factors. Sincez > y, we are left with a fraction of

1 / [xwhich, by definition 3, equals^{(z-y)}]x^{(-(z-y))}= x^{(y-z)}QED

**5. Fractional Exponents**

There is more that we can talk about. What about fractional exponents such as **x ^{(1/2)}**?

It turns out that based on our definitions, corrolaries, and theorems, we are now ready to take on fractional exponent.

Let’s start with 1/2.

We know that x^{1/2} * x^{1/2} = x^{(1/2 + 1/2)} by Theorem 1.

Now x^{(1/2 + 1/2)} = x^{(1)} = x.

So x^{1/2} is none other than the square root of x.

Let’s start out by looking at a definition for what a root is.

**Definition 4: an nth root of x is a number that multiplied n times equals x.**

Sometimes, nth roots are whole numbers. The cube root of 27 is 3 since 3 * 3 * 3 = 27.

Likewise, the 4th root of 16 is 2.

1 is its own 5th root since 1 * 1 * 1 * 1 * 1 = 1.

This gives us our last theorem:

**Theorem 4: x ^{1/n} = the nth root of x**

(1) x

^{1/n}multiplied by itself n times equals x^{1/n + 1/n + 1/n + etc.}.

(2) Now 1/n + 1/n + etc. n times equals n/n which equals 1.

(3) Therefore x^{1/n}multipled by itself n times equals x^{1}

(4) And this is the very definition of an nth root.QED