# 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 assume that there are x, y, z (positive integers) satisfying the equation z3 = x3 + y3 where 0<x<y<z.  It is easily proved that x, y and z form the sides of an acute angled triangle, i.e. that z<x+y and z²<x²+y². 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.
It follows then that (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 …………………..*
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.
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 and so a<3d<2a+b.

It can also be shown that 4d<2a+b.

Suppose not, then 4d≥2a+b.

Using the inequality, 4d≥2a+b, in ** we get 3a(a+b)16d≥(6d)3 . This simplifies to

2a(a+b)≥9d².  From this it follows that (2a+b)² > 18d² or that 16d² > 18d² which is clearly not true.

Hence, 4d<2a+b.  From this it follows easily that a<(3√2)/2)d = 2.121320344d.

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³  which is clearly 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.
So, a<md and the value of m can be easily shown to be 6/(³√2 + ³√4) or 2.107243152.
Returning to 3a(a+b)(2a+b+12d) = (6d)³ , if we divide both sides by 3 we get
a(a+b)(2a+b+12d) = 72d³ .  Since a≠b, it follows that a+b≥3. If a+b = 3 then it is easily verified that we can’t have a=1 and b=2 or a=2 and b=1 and so  a+b≥4.  It is again easily verified that we can’t have a=1 and b=3 or a=3 and b=1 and so a+b≥5.  It follows from this that d≥2 and so d must have a prime divisor.

a+b can’t be a prime number ≥5.  Suppose a+b is a prime p ≥5. Then clearly p|d and so d=pq for some whole number q.  So, a(a+b)(2a+b+12d) = 72d³ becomes

ap(a+p+12pq) = 72p³q³  and reduces to a(a+p+12pq) = 72p²q³.  It is clear then that p|a, but this is not possible since a<p.  Hence the result.

A similar argument shows that 2a+b+12d can’t be prime.

The equation a(a+b)(2a+b+12d) = 72d³ can be re-arranged to give …

a(a+b)(2a+b) = 12d(6d² – a(a+b)).

Clearly 2 |a(a+b)(2a+b) and so 2 | exactly one of a, (a+b) and (2a+b), otherwise 2 | all three of a, (a+b) and (2a+b) and since 2 | 6d then 2 | x, y and z contradicting gcd(x,y,z)=1.  If 2 | a or (a+b) then it is clear that 8 | a or (a+b).

If 2| (2a+b) then (6d² – a(a+b)) must be odd and so 4| (2a+b) if d is odd and

2^(n+2) | (2a+b) if 2^n | d.

Since a≥1, a+b≥5 and a+b>2d,  12d(6d² – a(a+b))=a(a+b)(2a+b) >12d and so

(6d² – a(a+b))>1 or (6d² – a(a+b))≥2.  Hence (6d² – a(a+b)) has a prime factor.

If p is prime and p|d then p divides at least one of a, (a+b) and (2a+b).  If p| a or (a+b) then p² | a(a+b)(2a+b).  If p| any two of a, (a+b) and (2a+b) then it divides all three and since p|d that contradicts gcd(x,y,z)=1.  Hence if p|a or (a+b) then p² | a or (a+b) and therefore p³ | a or (a+b).  So it follows that d = ABC where a = fA³ , a+b =gB³  and C and a or (a+b) have no common factors.  If f or g is 1 then a or (a+b) is a cube.  So, suppose that f>1 and so has a prime divisor q (say).  Then q is 2, 3 or q|d or q|(6d² – a(a+b)).

If a has a prime divisor p(say) where p>3 then p|d and so p³ | a(a+b)(2a+b+12d).
If p | (a+b) or (2a+b+12d) then p | b (as well as a and d) which in turn contradicts gcd(x,y,z)=1. Hence p³|a.
So, a = k1f³ where k1 and f are positive integers such that a prime divisor of k1 can only be 2 or 3 while a prime divisor of f can only be >3.
Similarly, a+b = k2g³ and 2a+b+12d = k3h³ where prime divisors of k2 and k3 can only be 2 or 3 while prime divisors of g and h can only be >3.
It follows then that k1k2k3(fgh)³ = 72d³.  And k3h³ – k1f³ – k2g³ = 12d.
Clearly from k1k2k3(fgh)³ = 72d³, at least one of k1, k2, k3 must be divisible by 3.  From k3h³ – k1f³ – k2g³ = 12d it follows that only one of k1, k2, k3 can be divisible by 3 otherwise we contradict gcd(x,y,z)=1.
Hence only one of k1, k2, and k3 is divisible by 3. Similarly, only one of k1, k2, and k3 is divisible by 2.
It follows then that at least one of a, (a+b) and (2a+b+12d) is a cube, and at least one is not a cube otherwise 72d³ would be a cube.
3a(a+b)(2a+b+12d) = (6d)³  can also be written as 3a(a+b)(2a+b) = (6d)³ 6a(a+b)(6d) and then as (2a+b)³ – a³ – (a+b)³ = (6d)³ – 6a(a+b)(6d).
TBC >>>
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.
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

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

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<ya such that 0<ab such that 0<bn= (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.