Archive for March, 2012

Fermat’s Last Theorem for the case where the index is 4

March 23, 2012

Fermat’s Last Theorem, proved in 1995, is that the diophantine equation

x^n + y^n = z^n

has no solution in positive integers x, y, z when n > 2. Knowing the solution for n = 2 (see previous post) we can show that there is no solution for n = 4.  If

x^4 + y^4 = z^4   …………………………… (1)

has a solution x1, y1, z1 then

x^4 + y^4 = z^2    …………………………….   (2)

has a solution x1, y1, z12 and a solution x1/d, y1/d, z12/d2 where d = (x1, y1), the greatest common divisor of x1 and y1. This implies that (2) has a solution where (x, y) = 1. If we can show there is no such solution then by the contrapositive there is no solution to (1).

Suppose to the contrary there is such a solution x1, y1, z1. It is easy to see that these numbers have greatest common divisor 1. We use the method of infinite descent by showing that there exist x2, y2, z2 such that z2 < z1.

By the properties of Pythagorean Numbers (previous post) we know that

z_{1} = a^{2} + b^2   ;  x_{1}^{2} = a^2 - b^2   ;  y_{1}^{2} = 2ab

with a > b> 0, (a,b) = 1, and a, b of opposite parity.

x12 + b2 = a2 and it is not hard to show that that x1, b and a have the remaining properties of Pythagorean numbers. Thus

x_1 = p^2 - q^2   ;  b = 2pq   ;  and  a = p^2 + q^2

with (p,q) = 1, p > q > 0, and p,q of opposite parity. Consequently

y_{1}^2 = 2ab = 4pq(p^2 + q^2)

Furthermore p, q and p 2 + q2 have greatest common divisor one, so by the Unique Factorisation Theorem each is a square and we can write:

p = x_{2}^2   ;  q = y_{2}^2   ;  and p^2 + q^2 = z_{2}^2 and thus

x_{2}^4 + y_{2}^4 = z_{2}^2

with x2, y2, z2 > 0 and z1 = a2+b2 = (p2+q2)2+b2=z24+b2 > z2

To prove Fermat’s Last Theorem it suffices to prove it for every prime index.   If n > 2 is composite and has no prime factor other than 2 then it is a multiple of 4 and the Theorem is true for this index because if

x^n + y^n = z^n then \left( x^{n/4}\right)^4 + \left( y^{n/4} \right)^4 = \left( z^{n/4} \right)^4

which is impossible.   If n is composite and has an odd prime factor p and if

x^n + y^n = z^n then \left( x^{n/p} \right) ^p + \left( y^{n/p} \right) ^p = \left( z^{n/p} \right) ^p

thus by the contrapositive if the Theorem is true for p it is true for n.

A copy of this post in pdf form is here.

Advertisements

Pythagorean numbers

March 15, 2012

We consider the diophantine equation

x^2 + y^2 = z^2    …………………………………………………….   (1)

whose connection to Pythagoras’  Theorem is obvious.

In what follows we take (a1, a2, … an) to be the greatest common divisor of the integers in the brackets.

It is clear that any positive solution a, b, c determines an infinite number of solutions ± ta, ± tb, ± tc where t is any integer, and also that 0, 0, 0 and ±a, 0, ±a and 0, ±a, ±a are solutions so we can confine our attention to cases where (x, y, z) = 1 and x, y, z > 0. We call these solutions the Pythagorean Numbers.

Proposition: the complete set of Pythagorean numbers without duplicates is:

z = a^2 + b^2    ;   x = a^2 - b^2   ;   y = 2ab

where a, b run through all the positive integers such that

a > b > 0 ; (a, b) = 1 and one of a and b is even, one odd.

Note: The first few such numbers are:

a

b

x

y

z

2

1

3

4

5

3

2

5

12

13

4

1

15

8

17

4

3

7

24

25

Proof: We take as given the following Lemma: if (m, n) = 1 and p divides mn then either p divides m or p divides n. For a proof see ‘Common Factors and Linear Diophantine Equations’ accessible through ‘Notes on Numbers’ (see sidebar on the home page).

First we show that if the triplets x, y, z constructed as per the proposition are Pythagorean numbers. It is clear by substitution that they are solutions of (1). It is also clear that they are all positive. Suppose n > 1 is some common divisor of x, y and z. z = (a + b)2 – 4ab is odd so n is odd. Since n divides y =2ab, it must divide either a or b, but it cannot divide both. Thus n divides either a2 or b2 but cannot divide both. Thus n cannot divide z, a contradiction. Thus (x, y, z) = 1.

The set of triplets so constructed contains no duplicates since if y = 2a1b1 = 2a2b2 then by the lemma and the Unique Factorisation Theorem a1 = a2 and b1 = b2.

Now we show that if x, y, z is a Pythagorean triplet then it either has the form given in the Proposition, or is a duplicate

(x,y) = 1 because if n > 1 divides x and y it divides z, a contradiction. Thus x,y cannot both be even. If x is odd then x2 leaves remainder 1 on division by 4, and similarly with y, so x,y cannot both be odd. Therefore z must be odd.

Suppose x is odd. We can factor (1) as y2 = z2 – x2 = (z + x)(z – x). Clearly 2 divides both z + x and z – x. Suppose there is a larger common divisor n. Then n divides (z + x) + (z – x) = 2z and (z + x) – (z – x) = 2x, so n/2 divides both z and x, and so (n/2)2 divides z2 – x2 = y2 and (x, y, z) = n/2 > 1, a contradiction.

Consequently we can write (y/2)2 = ((z + x)/2)((z – x)/2) where ((z + x)/2,(z – x)/2) = 1. Then as a consequence of the Unique Factorisation Theorem, (z + x)/2 and (z – x)/2 must both be squares.

So we can write (z + x)/2 = a2, (z – x)/2 = b2, (a,b) = 1. Therefore z = a2 + b2, x = a2 – b2, y = 2ab. Since x > 0, a > b and since x,z are both odd, one of a and b must be even.

Likewise, if we suppose y is odd we can factor (1) as x2 = z2 – y2 = (z + y)(z – y) and show that the triplet x, y, z has the duplicate form given above.

A pdf version of this post can be found here.

Prime Numbers and the Unique Factorisation Theorem

March 6, 2012

For present purposes a prime number is understood to be a positive number other than 1 that is only divisible by itself or ±1. It is easy to see inductively that every positive number is either a prime or can be expressed as a product of primes. A positive number (other than 1) that is not prime is composite.

The ancient Greeks showed that the number of primes is infinite. The proof (by contradiction) is worth repeating:

Suppose the contrary, that there is a largest prime pn. Consider N = p1p2 … pn + 1. N leaves remainder 1 on division by pn and every lesser prime, and thus is not divisible by any of them. Since N is greater than pn it is by hypothesis not prime and thus must be divisible by a prime. Hence there is a contradiction.

The sieve of Eratosthenes yields a list of primes less than or equal to some given number N: We write out a list of the numbers, starting with 2 and ending with N. We take the first number, 2 and assume that it is prime but strike out all its multiples. Then we go to the next number, assume it is prime, and repeat the process. The numbers remaining when we have finished are all prime. An animated demonstration of the sieve can be found at its Wikipedia entry.

Let us denote as π(n) the number of primes less than or equal to n. If the primes were approximately evenly distributed among the integers, then π(n)/n would approximate a constant less than 1. It was conjectured around 1800, and proved in the 1890s, following a proof outline given by Riemann in 1859, that the density of the primes tails off slowly, in such a manner that as n becomes larger the value of π(n)/n becomes progressively closer to 1/ln n.

The Unique Factorisation Theorem (also known as the Fundamental Theorem of Arithmetic) tells us that the expression of a composite number as a product of primes is unique except for the order of the primes. It can be proved with the aid of Euclid’s Lemma (for a proof see pdf link at ‘Common Factors …’ under ‘Notes on Numbers’ – via the sidebar on the home page) which tells us that if p divides mn and (m, n) = 1 then p divides n. It follows that if p is a prime and p divides mn, then either p divides m or p divides n. This can be easily generalised as follows:

If p1, … , pn are primes and if p divides p1p2 … pn then p = pi for one of p1, … , pn.

From here it is easy to prove the Unique Factorisation Theorem by induction on the composite numbers.

An interesting and useful corollary to the theorem is that, if the prime compositions of m and n contain the primes p1, … , pn then the greatest common divisor and least common multiple of m and n consist of the same prime composition with the index of a given prime being the minimum or maximum respectively of the indexes of that prime in the prime compositions of m and n. From this it is easy to show that the product of the gcd and lcm of m and n is mn.

The content of this post in pdf form, and in a little more detail, can be found via the link with the same title in ‘Notes on Numbers’ via the side-bar on the home page.