Saturday, May 07, 2005

Pythagorean Triples: Solution

OK, here's the solution for Diophantus's problem of determining the solution for:
x2 + y2 = z2

(1) We know that we can assume that x,y,z are coprime. [See my previous blog for details]

(2) The second important insight is that z has to be odd.

(a) Assume the opposite that z is even.

(b) Then, there exists another value Z such that z = 2 * Z

(c) Also, z2 is then divisible by 4 since:

z2 = (2 * Z)2 = 4 * (Z2)

(d) We know that x,y must both be odd because of (1).

(e) Since they are odd, there must also exist values X,Y such that:

x = 2 * X + 1
y = 2 * Y + 1

(f) But x2 + y2 cannot be divisible by 4 since:

x2 + y2 = (2 * X + 1)2 + (2 * Y + 1)2 =
= 4X2 + 4X + 1 + 4Y2 + 4Y + 1 =
= 4[ X2 + X + Y2 + Y ] + 2


(g) So, we have a contradiction and we reject our assumption.

(3) Since z is odd, either x or y must be even since an odd number is always the sum of an odd and an even number.

(4) Let's assume x is even. The same argument will also work if y is even.

(5) Now, we know that:

x2 = z2 - y2 = (z - y)(z + y)

(6) And, z - y and z + y must be even since z,y are odd.

(7) So, we know that there must exist u,v,w such that:
x = (2u)
z + y = (2v)
z - y = (2w)


(8) Which means that:
(2u)2 = (2v)(2w) [From (5) and (7)]

(9) Dividing both sides by 4 gives us:
u2 = v * w

(10) We need 1 more insight before the solution. Here it is: v,w are coprime

(a) Assume that v,w are not coprime.

(b) Then, there exists d such that d > 1 and d divides both v,w

(c) Then d divides both v + w and v - w

(d) But:

z + y + z - y =
2v + 2w

So 2z = 2v + 2w which means that z = v + w
So d divides z

(e) And:

z + y - (z - y) = 2v - 2w
So 2y = 2v - 2w which means that y = v - w
So d divides y

(f) Which is a contradiction since z,y are coprime [by (1)].

(g) So, we reject our assumption.

(11) By the properties of coprimes, we know from (9),(10) that v,w are themselves squares (see here for proof). [For those who need a review of coprimes, here is a link.]

(12) So, there exists p,q such that:

v = p2
w = q2

(13) And, we have our solution since:

z = v + w = p2 + q2
y = v - w = p2 - q2
x = 2u = 2pq [Since u2 = vw means u = pq]

We also know that:

(a) p,q are relatively prime. [Otherwise, z,x,y would not be relatively prime]

(b) p,q are opposite parity (that is, one is odd and one is even) [Since z is odd]

(14) For sure enough:

(p2 + q2)2 = (2pq)2 + (p2 - q2)2

(15) Now, to generate our answer, we can pick any p,q we want so long as they are integers.

For example, if p = 2 and q = 1, we get:

z = (2)2 + (1)2 = 5.
y = (2)2 - (1)2 = 3.
x = 2pq = 2*2*1 = 4

(16) We can do even better than this because we know that for each x,y,z, if they have common factors, the relation still holds.

z = d[p2 + q2]
y = d[p2 - q2]
x = d[2pq]

For example, if p = 2 and q = 1 and d = 2, we get:
z = (2)(5) = 10
y = (2)(3) = 6
x = (2)(4) = 8

And sure enough, 62 + 82 = 36 + 64 = 100.

QED

What's also nice about this result is that it is not too difficult to apply Fermat's method of infinite descent and prove Fermat's Last Theorem for n=4.

17 comments:

kkraz said...

Larry -

I am definitely a math amateur, but have been thinking about this for a while and have a couple of questions.

kkraz said...

I've been thinking about this for a while and have a simple way to identify whole number pythagorean triples. Consider any odd number x.

Then, y = (x2 - 1)/2

and z = (x2 + 1)/2

For example if x = 5 (x2 = 25)
then y = 12 and z = 13.

For x = 7 (x2 = 49)
y = 24 and z = 25.

This works because x2 = y + z
and y + 1 = z

So x2 + y2
= (y + z) + y2
= z + (y + y2)
= z + (y * z)
= z2

For example,
if x = 5
25 + (12 * 12) = (13 * 13)
(12 + 13) + (12 * 12) = (13 * 13)
13 + (13 * 12) = (13 * 13)
(13 * 13) = (13 * 13)

So, basically, x2 + y2 = z2 works with whole numbers because there is
a number, which when squared is the difference between n2 and (n-1)2.

kkraz said...

Does this make sense?

Larry Freeman said...

Thanks for your post.

Yes, that also works since:

Let p be any positive integer.
Let x = 2p+1 (so, x is odd)
So, x^2 = (2p+1)^2 = 4p^2+4p+1

So, y = (4p^2 + 4p + 1 - 1)/2 = 2p^2 + 2p

So, z = (4p^2 + 4p + 1 + 1)/2 = 2p^2 + 2p + 1

Now, z^2 = (2p^2 + 2p + 1)^2 = 4p^4 + 8p^3 + 8p^2 + 4p + 1

And y^2 + x^2 = (2p^2 + 2p)^2 + 4p^2 + 4p + 1 = 4p^4 + 8p^3 + 8p^2 + 4p + 1.

Cheers,

-Larry

jenny said...

Hi Larry,

Could you please teach me how to solve the below Diophantine equation?

Find all solutions to the Diophantine equation x^2 + y^2 = 7z^2.

Thank you very much.

Jenny

Larry Freeman said...

Hi Jenny,

Are you sure that you have stated the problem correctly.

There are no integer solutions to the problem x^2 + y^2 = 7*z^2.

The reason for this is that any prime of the form 4n+3 that divides the sum of two pairs must itself have an even power in the prime factorization.

Unfortunately, it is impossible for 7=(4*1+3) to have an even power in the prime factorization 7*z^2.

Here is a web page that provides the proof.

Here is another proof in pdf format.

-Larry

jenny said...

Hi Larry,

Thank you very much.

The question is right. It should be no integer solution. Thanks again for show me the way to solve it.

Jenny

Chin Foo said...

Hi, Larry.

I discovered below equations to calculate Pythagorean triples when I was a secondary school student.

For x = odd numbers. 1, 3, 5, 7,...
y = (x^2-1)/2, z = (x^2+1)/2

Eg.
1, 0, 1
3, 4, 5
5, 12, 13
7, 24, 25

For x = even numbers which could be divided by 4. 4, 8, 12, 16,...
y = (x^2/4)-1, z = (x^2/4)+1

Eg.
4, 3, 5
8, 15, 17
12, 35, 37
16, 63, 65

It is easy to proof that those above equations are correct for all intergers.

But until now I still can't find the phythegorean triple equations for all even numbers including, 2, 6, 10, 14....

Is it impossible?
Please advise.

thanks and best regards
cf

Larry Freeman said...

Hi Chin Foo,

I'm not clear on your question.

A Pythagorean Triple that consists of all even numbers is 6,8,10 since

36 + 64 = 100

There are in fact an infinite number of them which can be derived from the formula in my blog.

Please let me know if I am misunderstanding your question.

Cheers,

-Larry

Chin Foo said...

Good day, Larry.
Sorry for not stated my question clearly.

I never consider (6,8,10), (10,24,26) are original Pythagorean Triple since it is 2*(3,4,5) and 2* (5,12,13).

My question, is it possible to have a equation to find out Pythagorean Triple for x = 6 (but y not 8 and z not 10), x = 10 (but y not 24 and z not 26)?

Please advise.

thanks and best regards
cf

Larry Freeman said...

Hi Chin Foo,

If I understand your question correctly, the answer is no.

While it is easy to find an all even solution by doubling any solution you would like, to get a primitive solution, all three integers need to be relatively prime. This means that at most, only 1 of the integers can be even.

Please let me know if I misunderstood your question.

I wasn't sure if this is what you are asking or if you are asking if x=6, how many different possible solutions are there.

Cheers,

-Larry


-Larry

Chin Foo said...

Thanks, Larry.
You have answered my question.

best regards
cf

Eva said...
This comment has been removed by the author.
pichkari said...

Hi Larry,

For finding the pythagorean triplet involving a given number i use this way. take the number square it and then factorize it in such a way that both factors are even or both odd.

Ex: for 8
8^2 = 64 = 1*64 (1 odd ,1 even)
2*32 (2 even)
4*16 (2 even)

2*32 implies the other two numbers are (32+2)/2 and (32-2)/2

4*16 implies (4+16)/2 and (16-4)/2

so we can find all the triplets involving the given number.

pichkari said...

Hi Larry,

For finding the pythagorean triplet involving a given number i use this way. take the number square it and then factorize it in such a way that both factors are even or both odd.

Ex: for 8
8^2 = 64 = 1*64 (1 odd ,1 even)
2*32 (2 even)
4*16 (2 even)

2*32 implies the other two numbers are (32+2)/2 and (32-2)/2

4*16 implies (4+16)/2 and (16-4)/2

so we can find all the triplets involving the given number.

olaf said...

There is an algorith to ind ALL Pythagorean triples. I found it during my play around to find Fermat's original proof of his last theorem. For some reason, the pro's are not very interested, the silence is overwhelming. For those interested, I will be happy to publish it properly here, as long as its origin is never doubted. It will also show why Fermat's last theorem (the proof) is closely coupled to the same algoritm.

april said...

greetings!

can you give me an algorithm or formula that generate any pythagorean triple leg a and b wherein both legs could still be expressed as a sum of 2 squares ?

regards