wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> medium >> #Primitive pythagorean triples, given hypotenuse
(Message started by: Aryabhatta on Feb 4th, 2010, 9:40am)

Title: #Primitive pythagorean triples, given hypotenuse
Post by Aryabhatta on Feb 4th, 2010, 9:40am
Prove/Disprove:

Given a positive integer c, the number of primitive pythagorean triples (a,b,c) with c as hypotenuse is either 0 or a power of 2.

Note, we only count the triples where a >0, b>0 and c > 0.

Primitive pythagorean triples are triples where gcd(a,b) = 1 and a2 + b2 = c2

Example:

c = 3 : number of triples = 0.
c = 5:  Number of triples = 2. (3,4,5) and (4,3,5).

Title: Re: #Primitive pythagorean triples, given hypotenu
Post by SMQ on Feb 5th, 2010, 5:51am
Proof by MathWorld (http://mathworld.wolfram.com/PythagoreanTriple.html): see equations (25) and (26). ;D

I'm still working on tracing that statement back to elementary principles...

--SMQ

Title: Re: #Primitive pythagorean triples, given hypotenu
Post by Obob on Feb 5th, 2010, 8:16am
I found that page as well, but why it should be true eludes me.

Title: Re: #Primitive pythagorean triples, given hypotenu
Post by rmsgrey on Feb 5th, 2010, 9:08am
It's obvious that it has to be even - if a,b,c is a primitive triple, so is b,a,c - it's obvious that no triple can be a,a,c.

Title: Re: #Primitive pythagorean triples, given hypotenu
Post by SMQ on Feb 5th, 2010, 10:00am
Alright, so, not so elementary, and still incomplete, but at least based on other "well known" proofs:

Consider the factorization of c as 2lp1m1p2m2...prmrq1n1q2n2...qsns where each pi is a prime of the form 4x - 1 and each qi is a prime of the form 4x + 1 (where x is an integer). We are interested in the number of ways c2 = 22lp12m1p22m2...pr2mrq12n1q22n2...qs2ns can be represented as the sum of two squares.

1) 22l cannot be represented by the sum of two squares which are not both divisible by 4. 22l http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 0 (mod 4). Any square is congruent to 0 or 1 (mod 4), therefore any two squares which sum to 22l must be congruent to 0 (mod 4) and so divisible by 4.

1a) If l > 0, no primitive Pythagorean triple exists with c as an hypotenuse. By (1), any squares which sum to c2 must have 4 as a common factor and therefore are not relatively prime.

2) No odd prime p of the form 4x - 1 (where x is an integer) can be represented as the sum of two squares. p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 3 (mod 4), but the sum of two squares can only be 0, 1, or 2 (mod 4).

2a) If r > 0, no primitive Pythagorean triple exists with c as an hypotenuse. By (2), any squares which sum to c2 must have each pi2mi as a common factor and therefore are not relatively prime.

3) Every prime q of the form 4x + 1 (where x is an integer) can be represented as the sum of two squares. This is Fermat's theorem on sums of two squares (http://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares), first proven by Euler.

3a) No prime q of the form 4x + 1 (where x is an integer) can be represented as the sum two odd squares nor two even squares. This follows trivially from the fact that q is odd.

3b) Every prime q of the form 4x + 1 (where x is an integer) can be represented as the sum of two squares in only one way (up to order and negation). This is known as Thue's Lemma (http://planetmath.org/encyclopedia/ThuesLemma2.html) and an elementary proof of uniqueness can be found at the top of this page (http://planetmath.org/encyclopedia/ProofOfThuesLemma.html).

4) Every power of q can be represented as the sum of two squares. By (3b) there exist some unique positive integers u, v such that u2 + v2 = q. By the Brahmagupta-Fibonacci identity (http://en.wikipedia.org/wiki/Brahmagupta-Fibonacci_identity) (hereafter B-F identity), (u2 - v2)2 + (2uv)2 = q2. Proof for arbitrary powers is by induction in the B-F identity.

4a) Every representation of a power of q as a sum of two squares is generated by iteratively applying the B-F identity. I do not yet have a proof of this step.

4b) Every power of q can be represented as the sum of two coprime squares in exactly one way (up to order and negation). I believe this can be proven by induction using (4a) and divisibility by lower powers (showing that one of the two solutions generated by iteratively applying the B-F identity is always divisible by q), but the details are more-than-a-little messy.

5) For qi2ni and qj2nj, the solutions generated by applying the B-F identity to uni2 + vni2 and unj2 + vnj2 are distinct. The B-F identity yeilds (uniunj - vnivnj)2 + (univnj + vniunj)2 and (uniunj + vnivnj)2 + (univnj - vniunj)2. Of these, uniunj - vnivnj and uniunj + vnivnj clearly have the same parity but are distinct, while by (3a) the other terms have the opposite parity. By symmetry all four terms must be distinct.

5a) Both solutions found in (5) are primitive. I have no proof of this step: the result of (4b) does not suffice.

5b) Continuing in the same manner, the product of qi2ni, qj2nj, and qk2nk has four distinct primitive solutions, etc. I have no proof for this step, neither for distinctness nor for primitiveness.

5c) All integral solutions to the original equation a2 + b2 = c2 can be enumerated in the manner of (5b).  And, again no proof.

6) Therefore, either a2 + b2 = c2 = 22lp12m1p22m2...pr2mrq12n1q22n2...qs2ns has no primitive solutions if either l > 0 or r > 0, by (1a) and (2a), or there are 2s - 1 distinct (up to order and negation) primitive solutions by (4b) and (5b).

--SMQ

Edit: found a few more holes...
Edit 2: changes (3b) to reference Thue's Lemma
Edit 3: found one more hole, added (5c)...

Title: Re: #Primitive pythagorean triples, given hypotenu
Post by Aryabhatta on Feb 6th, 2010, 11:49am
4a and 4b are true.

Title: Re: #Primitive pythagorean triples, given hypotenu
Post by SMQ on Feb 8th, 2010, 5:48am

on 02/06/10 at 11:49:48, Aryabhatta wrote:
4a and 4b are true.

And given those, if (5c) is true (which seems very likely), (5a) and (5b) must be true in order to obtain the "correct" answer.  I'm confident in the reasoning, I just haven't yet found or devised proofs for the later steps...

--SMQ

Title: Re: #Primitive pythagorean triples, given hypotenu
Post by Aryabhatta on Feb 8th, 2010, 7:40am

on 02/08/10 at 05:48:50, SMQ wrote:
And given those, if (5c) is true (which seems very likely), (5a) and (5b) must be true in order to obtain the "correct" answer. I'm confident in the reasoning, I just haven't yet found or devised proofs for the later steps...

--SMQ


I think 5a,b,c are all true too.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board