From Euclid to Fermat

· Uncategorized

Primitive Pythagorean Triples, or PPT’s, are non-trivial integer solutions to the Pythagorean equation z2 = x2 + y2, where we assume that 0<x<y<z and that x, y and z are co-prime.

Euclid’s formulae allow PPT’s to be generated using 2 (positive integer) parameters, usually denoted by m and n. The PPT’s (usually) take the form ( m2– n2, 2mn, m2+n2) or ( 2mn, m2-n2, m2+n2), where m>n≥1, m and n are co-prime, and m-n is odd. Clearly, m2+n2 is the largest number in each triple.

Note: It is easier to spot patterns in generated triples if these are ordered as in (x, y, z) where x<y<z.

There are 2 cases that can occur, i.e. ( m2– n2, 2mn, m2+n2) where m2-n2< 2mn and

( 2mn, m2-n2, m2+n2) where 2mn < m2-n2. If m2-n2< 2mn then it is easy to show that

n < m < (1+√2)n. Hence if we wished to write a program to generate such triples we would first have to choose n from 1,2,3, … and then choose m from (n+1), …, int((1+√2)n).

Any proofs that I have seen that establish the above formulae for x, y and z make use of parity, factorisability and co-primeness, but interestingly do not make use of geometry.

It cannot be assumed of course that x, y, and z form the sides of a triangle. That has to be proved.

However the consequences of proving that x, y, and z form the sides of a triangle lead to a simple method of generating PPT’s which is also simply proved.

New Method

Returning to the equation z2= x2+ y2, it is easy to show that z<x+y, since x2+ y2 < (x+y)2 and so, since 0<x<y<z, x, y, and z do form the sides of a triangle. It follows, from z<x+y and x<y, that z<2y. Hence y<z<2y, and so there is an integer a, where 0<a<y, such that z=y+a. Also, since 0<x<y, there is an integer b, where 0<b<y, such that x=y-b.

So, z2= x2+ y2 becomes (y+a)2 = (y-b)2+ y2, where 0<a<y and 0<b<y.

After multiplying out and re-arranging (y+a)2 = (y-b)2+ y2 we get, 2a(a+b) = (y – (a+b))2.

Hence 2|(y-(a+b)) and so y-(a+b) = 2c, where c is an integer and it is easy to show that c>0.

Note: [2c = y – (a+b) = y – (z-y + y-x) = y + x – z > 0]

So, x = a+2c, y = a + b + 2c = (x+b) and z = 2a + b + 2c = (y+a), where a(a+b)= 2c2.

Note: it is easy to show that a<√2 c.

To generate PPT’s, first choose any integral c, c≥1;  then choose integral a in the range 1≤a<√2c so that a|2c2; then finally choose integral b , b≥1, using a(a+b)= 2c2, or b=(2c²)/a – a, making sure that the resulting x, y and z have no common factors.

For example:

If c=1 then a=1 and b = 1. Hence we get the PPT (3,4,5).

If c=2 then a=1 and b=7, and this gives the PPT  (5,12,13)

If c=3 then a=1 and b=17 or a=2 and b=7, giving PPT’s (7,24,25) and (8,15,17).

If c=4 then a=1 and b=31 giving PPT (9,40,41).

If c=5 then a=1 and b=49 or a=2 and b= 23 giving PPT’s ( 11, 60, 61) and ( 12, 35, 37).

If c=6 then a = 1 and b = 71 and we get the PPT (13,84,85).

Etc.

The following is a short Python program to generate PPT’s using this method.

 

import math
#Generating primitive Pythagorean Triples
#
def hcf(x,y):
    #assume y!=x
    while y!=x:
        if y>x:
            y=y-x
        else:
            x=x-y
        #endif
    #endwhile
    return x
#enddef
#
def generate_triples():
    for c in range(1,60):
        for a in range(1,int(math.sqrt(2)*c)+1):
            if int(2*c*c/a)==2*c*c/a:
                b=int(2*c*c/a)-a
                x=a+2*c
                y=a+b+2*c
                z=2*a+b+2*c
                if hcf(x,y)==1:
                    print ("c = ",c)
                    print ("x = ",x)
                    print ("y = ",y)
                    print ("z = ",z)
                    print ()
                #endif
            #endif
        #endfor
    #endfor
#enddef
#
generate_triples()
The advantage of this method is that it uses all of the information from the equation z2= x2+ y2 , together with the inequalities, and not just some of it. Also, the need to look at parity is removed and co-primeness only comes into play when choosing the values of a and b. The method is clearly exhaustive since c can range over all positive integers.It is rather mind-blowing to think that the simple triangle property of x, y and z has lain in plain view since 300 BC? and yet no-one has noticed, or used it, until now.
___________________________________________________________
In the case of the Fermat equation z3 = x3 + y3 we assume that a non-trivial solution exists and then try to arrive at a contradiction. So we can assume that there are x, y, z (positive integers) satisfying the equation where 0<x<y<z and gcd(x,y,z)=1. Clearly then z<x+y and so x, y and z form the sides of a triangle (actually an acute angled triangle). However, since x<y<z it follows that y<z<2y and so there is an integer a such that 0<a<y where z = y + a. Also since 0<x<y there is an integer b such that 0<b<y where x = y – b. Substituting into the Fermat equation we get (y+a)3 = (y-b)3 + y3
It is easily shown that a≠b.
Suppose not, then a=b, and so (y+a)3= (y-a)3+ y3 and therefore (y+a)3– (y-a)3= y3. Hence 2a((y+a)2 + (y+a)(y-a) + (y-a)2) = y3 . It follows from this that 2|y, and so y=2y1. Substituting for y, and dividing the result by 2, we get … a((2y1+a)2+ (2y1+a)(2y1-a) + (2y1-a)2) = 4y13. If 2|a then that contradicts gcd(x,y,z)=1, so 2|(2y1+a)2+ (2y1+a)(2y1-a) + (2y1-a)2 but, if that is true, then 2|a2 and so either way we have a contradiction. Hence a≠b.
Using arithmetic modulo 2 on (y+a)3= (y-b)3+ y3 it follows that y+a ≡ y-b + y mod 2 or 2| y-a-b. It is easily shown then that y = a+b+2c, where c>0.  
Using arithmetic modulo 3 on (y+a)= (y-b)3+ y3 it follows that y+a ≡ y-b + y mod 3 or 3| y-a-b. So 3|2c and therefore 3|c. Hence c = 3d where d is an integer>0.
We have now shown that there are positive integers a, b and d such that …
x = a + 6d, y = a+b+6d  and z = 2a+b+6d.
So the Fermat equation becomes (2a+b+6d)3 = (a+6d)3 + (a+b+6d)3 …………………..*
If we expand the 3 cubes and collect terms together we eventually get
3a(a+b)(2a+b+12d) = (6d)³ ………………..**
Some estimates involving a, b and d.
From the Fermat equation z³ = x³ + y³, and 0<x<y, it is straightforward to show that z-y<x/3 and from this that a<(a+6d)/3 or that a<3d.
We can also show that 3d<2a+b.
Suppose that 3d≥2a+b.  From ** it follows that 3a(a+b)15d≥(6d)³ or that 5a(a+b)≥24d².  But 9d² = (3d)²≥4a²+4ab+b² > 4a(a+b) and so 45d² > 20a(a+b) ≥ 96d² i.e impossible.

Hence 3d<2a+b.

These estimates can be refined a little.  For example, if m is the positive root of the equation 36 = m³ + 6m² then a<md<a+b/2.

Suppose that md≤a, then from ** we have 3a(a+b)(2a+b)+36a²d<(6d)³ and so

3a(a+b)(2a+b)<36d(6d² – a²).  Now md≤a implies that d≤a/m and so,

3a(a+b)(2a+b)<36d(6(a/m)² – a²) = 36a²d(6/m² – 1) = 6a²dm ≤ 6a³.

So, 3a(a+b)(2a+b) < 6a³ and therefore 3ab(3a+b)<0 and so 3a+b<0 which is not possible.

Hence a<md.

Similarly, if 2md≥2a+b then from ** we get 3(2a+b)²(2a+b+12d)>4(6d)³.
This follows since (2a+b)² = 4a² + 4ab + b² > 4a(a+b).
If we now use 2md≥2a+b we get 12m²(2m+12) > 4.6³ or m³ + 6m² > 36 which contradicts the equation 36 = m³ + 6m².  Hence 2md<2a+b or md<a +b/2.
The value of m can be easily shown to be 6/(³√2 + ³√4) or 2.107243152.
Note: It is easy to show that 6d≠b, otherwise if 6d=b, * becomes 7(a+b)³ = (a+2b)³ implying that ³√7 is rational which is obviously not true.  It is also easy to show that 6d≠a.  
If we now define λ = (6d-b)/(a+b), it is clear that λ≠0 and λ is rational, i.e. λ∈Q.  Also, 6d = λ(a+b)+b, and so (substituting in the x and z terms for 6d) * becomes
((λ+2)³ – (λ+1)³ )(a+b)³ = (a+b+6d)³ and so,³√((λ+2)³ – (λ+1)³ ) = 1+6d/(a+b), i.e. rational.
Hence, if it can be shown that ³√((λ+2)³ – (λ+1)³ ) is irrational for all λ≠0, λ∈Q, we have a contradiction.
Suppose now that λ is any positive rational, i.e. λ = p/q, where p and q are positive integers and gcd(p,q)=1.  Suppose also that ³√((λ+2)³ – (λ+1)³ ) is also positive rational, so there are r and s positive integers with gcd(r,s)=1 such that ³√((λ+2)³ – (λ+1)³ ) = r/s.  
It follows easily from this that (r/s)³ = (p/q + 2)³ – (p/q + 1)³ or that
s³((p+2q)³ – (p+q)³) = r³ q³ which simplifies to  s³(q² + 3(p+2q)(p+q)) = r³ q² and so
3s³(p+2q)(p+q)) = q²(r³ – s³).  
From this last equation it follows that 3|q(r-s) and so that 3|q or 3|(r-s) but not both.
It also follows that r>s and so r≥2. Hence  r  must have a prime factor.  
If 3|r then 3 can’t divide s since gcd(r,s)=1 and so 3 can’t divide into r-s; hence 3|q.  
From s³q(q² + 3(p+2q)(p+q)) = r³ q³ it follows (from 3|r) that 3 divides the left and right hand sides of this equation a different number of times contradicting unique factorisation.
Similarly, if 2|r the left hand side of s³(q² + 3(p+2q)(p+q)) = r³ q² is odd while the right hand side is even.  So, r is odd.  This means that s is even, as is q, and p is odd.
tbc …
_______________________________________________________________
Lemma 1
Now let x and y be distinct positive integers such that 1<x+1<y, and let p be an odd prime.
Let ∑ = yp-1 + xyp-2 + … + xp-2y + xp-1. Assume that p|y-x.
If neither x nor y is divisible by p then p|∑.
Proof
Assume that neither x nor y is divisible by p.
∑ = yp-1+ (x-y)yp-2+ yp-1 … + (xp-2– yp-2)y + yp-1+ xp-1
= (p-1)yp-1 +(x-y)yp-2+ (x2-y2)yp-3 +… + (xp-2– yp-2)y + xp-1
By Fermat’s Little Theorem xp-1≡ 1 mod p as is yp-1≡ 1 mod p, since neither x nor y is divisible by p.
Hence ∑≡ 0 mod p and so p|∑.
_______________________________________________________________
Lemma 2
Suppose that x and y are integers such that 1<x+1<y. Suppose that p is an odd prime and that q is also prime such that q|y-x but that q is distinct from p.
Let ∑ = yp-1+ xyp-2+ … + xp-2y + xp-1. If q|∑ then it must follow that q|y as the following proof shows. 
Proof
If q|∑ and q|y-x it follows that q|yp-1+ xyp-2+ … + xp-2y + xp-1+ xp-2y -xp-1 or,
that q|yp-1+ xyp-2+ … + 2xp-2y. Similarly, q|yp-1+ xyp-2+ … + 3xp-3y2 . Continuing that theme we arrive at q|pyp-1 and since q can’t divide p it follows that q|y.
_________________________________________________________________
In the remaining cases of the Fermat equation zn= xn+ yn , where n is an odd prime ≥5, we assume again that a non-trivial solution exists and then try to arrive at a contradiction. So we can assume that there are x, y, z (positive integers) satisfying the equation and where 0<x<y<z and gcd(x,y,z)=1.
Clearly then z<x+y and so x, y and z form the sides of a triangle (again an acute angled triangle). However, since x<y<z it follows that y<z<2y and so there is an integer a such that 0<a<y where z = y + a. Also since 0<x<y there is an integer b such that 0<b<y where x = y – b. Substituting into the Fermat equation we get (y+a)n= (y-b)n+ yn. It follows easily using an argument applied in the case n=3 that a≠b.
Using arithmetic modulo 2 on (y+a)n= (y-b)n+ yn it follows that y+a ≡ y-b + y mod 2 or 2| y-a-b. Hence y=a+b+2c where c>0.  Since n is odd and ≥ 5, n=2k+1 where k≥2.
Now, xn – x = x(xn-1 – 1) = x(x2k – 1) = x(x2 – 1)(x2k-2 + … + ) and so the presence of the factor(s) x(x2 – 1) means that 3|xn -x.  So, using arithmetic modulo 3 on (y+a)n= (y-b)n+ yn it follows that y+a ≡ y-b + y mod 3 or 3| y-a-b in which case 3|2c and so there is an integer d>0 such that d=3c. It now follows that y = a + b + 6d.
Finally since n is an odd prime ≥ 5 it must also be the case that n|6d or that there is an integer e>0 such that d=ne.  So, x = a + 6ne, y = a + b + 6ne and z = 2a + b + 6ne.  Hence the Fermat equation becomes (2a+b+6ne)n = (a+6ne)n + (a+b+6ne)n where n is prime ≥ 5 and a, b and e are integers ≥ 1.We now rearrange this equation as (2a+b+6ne)n– (a+6ne)n = (a+b+6ne)n and then factorise the left-hand side as …(a+b)((2a+b+6ne)n-1 + (a+6ne)(2a+b+6ne)n-2 + … + (a+6ne)n-1) = (a+b+6ne)n. Again if we expand the RHS as a binomial in a+b and 6ne, it must follow that a+b|(6ne)n. A similar argument shows that a|(6ne)n.Now a+b ≥ 3, since a≠b, and so a+b must have a prime factor. Let q be any prime factor of a+b other than 2, 3 or n.It is clear then that q|e. If q|(2a+b+6ne)n-1+ (a+6ne)(2a+b+6ne)n-2+ … + (a+6ne)n-1 then by Lemma 2, q|2a+b+6ne and so q|a. It follows then that q|b and so q is a common factor of x, y and z, which contradicts gcd(x,y,z)=1.Hence if a+b has a prime factor a+b can only be divided by 2, 3 or n.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: