Generating Pythagorean Triples

by

500px-illustration_to_euclids_proof_of_the_pythagorean_theorem2svgA recent post at jd2718 noted that for all Pythagorean triples (a, b, c), that is to say, for all positive integer solutions to a^2 + b^2 = c^2, it turns out that 60 divides the product abc.

In the course of exploring proofs of that result, I suggested a proof using the representation (2uv, u^2-v^2, u^2+v^2), which generates all primitive Pythagorean triples (triples which have no common factors).  Proving that 60 divides their product proves the general result, as every Pythagorean triple has the form (ka, kb, kc), where k is a positive integer and (a, b, c) is primitive.

In the ensuing discussion, a question arose as to how we know that all possible Pythagorean triples can be found in this way.   Since it is easier for me to post LaTeX code to this blog rather than in the comments on the jd2718 blog, I’ll present the proof here.

Suppose that a^2 + b^2 = c^2, with positive integers a, b, c having no common factors.  This implies that exactly one of a and  b is even (since if both are even, then so is c, leading to a contradiction, while if both a and b are odd, then both a^2 and b^2 are congruent to 1 mod 4, while c^2 would be congruent to 0 mod 4, not 2 mod 4).

So without loss of generality, assume that a is even.  Thus a^2 = (c-b)(c+b) is also even, and since (c-b) and (c+b) differ by an even number, both of those factors must be even.

Furthermore, exactly one of (c-b) and (c+b) is 2x(an odd number), since if both factors are divisible by 4, it would follow that both b and c would be even (since b and c are \frac{ (c+b)\pm (c-b)}{2}.)   Likewise, any odd common factor of (c-b) and (c+b) would also then be a common factor of both b and c, from which it follows that

  • (c+b) and (c-b) have no odd common factors
  • one of these expressions is of the form 2 u^2 (for some odd u)
  • and hence the other expression is of the form 2 v^2, where v^2 = \frac{a^2}{4u^2}, where u and v are positive integers

It now follows that c = u^2 + v^2, and b = u^2 - v^2.  We can find a using a^2=(c+b)(c-b) = (2u^2)(2v^2), and thus a = 2uv.

Conclusion:  every primitive Pythagorean triple has the form (2uv, u^2-v^2, u^2+v^2), for positive integers u and v.

24 Responses to “Generating Pythagorean Triples”

  1. jd2718 Says:

    why must one of (c+b) and (c-b) be of the form 2u^2 ?

    I see twice an odd number, not twice an odd square. What have I missed?

    (oh, and for the wordpress installation of LaTeX in wordpress comments, if it’s easy, I just do it. If it’s hard, I write a dummy post and preview it.. I still screw up, but not all the time)

    Jonathan

  2. TwoPi Says:

    All of the prime factors of a^2 occur to even powers. Any odd prime factor of c+b (say) cannot also be a factor of c-b, and so must occur to an even power in c+b. Thus both c+b and c-b must be a power of 2 multiplied by an odd square.

  3. Todd Trimble Says:

    I much prefer the classic geometric proof, based on stereographic projection. First, one notes that primitive Pythagorean triples (a, b, c) are in bijective correspondence with rational pairs (a/c, b/c) on the unit circle. So it suffices to parametrize rational points (u, v) on the unit circle.

    Consider the point where the line through (0, 1) and (u, v) intersects the line y = -1. Since these two lines have rational coefficients, the point of intersection has rational coordinates, say (2t, -1) [the factor of 2 makes the arithmetic come out nicer]. You can work out what (x, y) is in terms of t: just note that the point (x, y) on the circle is the intersection of two lines, the first one through (0, 1) and (2t, -1), which is

    \displaystyle y - 1 = -\frac1{t}x

    and the second is the line perpendicular to that through (0, -1), which is

    y + 1 = t x.

    [That is, we use here a famous result from Euclidean geometry: that a right triangle is formed when you draw the chords from a point on the circle to the endpoints of a diameter.]

    Solving for the intersection of those two lines, one quickly finds

    \displaystyle (u, v) = (\frac{2t}{t^2 + 1}, \frac{t^2 - 1}{t^2+1}

    Putting t = m/n, this gives

    \displaystyle (u, v) = (\frac{2mn}{m^2 + n^2}, \frac{m^2 - n^2}{m^2 + n^2})

    and voila! there’s your Pythagorean triple. Neat, isn’t it?

  4. Todd Trimble Says:

    Edit: the (x, y) in the fourth and fifth lines of the second paragraph should have been (u, v).

  5. Carnival of Mathematics #44 « Maxwell’s Demon Says:

    […] can learn how to bound binomial coefficients at the Endeavour, or generate Pythagorean triples at 360.  To stretch your mathematical muscles a little more look for Terry Tao, considering polynomials […]

  6. Harbey Says:

    Here is the original Pythagorean formula: For any pair of positive integers “y > x” odd and coprime,

    where the product “xy = i” is the odd leg and “(y2 − x2) / 2 = p” is the even leg,

    being “(y2 + x2) / 2 = h” the hypotenuse and the radius of the incenter is “r = x(y − x) / 2”.

    Remembering that “h − p = x2” is easy to get “h + p = y2” from a known primitive triple.

    By the way “n + m = y”, then “(y − x) / 2 = n” and “y − ((y − x) / 2) = m”.

  7. David Gillies Says:

    (2 u v, u^2 – v^2, u^2 + v^2) (or (u v, (u^2 – v^2)/2, (u^2 + v^2)/2) for that matter) is not primitive for non-coprime u, v.

    Harbey’s form is correct.

    It is trivial to show that 8|(u^2 – v^2) for odd u, v

    u^2 – v^2 = (u + v)(u – v)
    =(2m + 1 + 2n + 1)(2m + 1 – 2n – 1)
    =4(m + n + 1)(m – n)
    2|(m + n + 1) or (m – n)

    8|(u^2 – v^2)
    4|((u^2 – v^2)/2)

    The divisibility of one of the legs by 3 arises from the fact that 2 is not a quadratic residue mod 3. A similar approach shows that 5 divides one of the sides, whence the divisibility by 60 of the product of the sides.

  8. Juxtaposition: Millionaire Triangles « 360 Says:

    […] What would come next?  Is there even an ordering for Pythagorean triples?  (Well, maybe:  TwoPi wrote earlier about how every Pythagorean triple can be written as , for positive integers u and v, so we could […]

  9. Keith Raskin Says:

    Re:Juxtaposition: Mill’s question above: Is there an ordering for Pythagorean triples?

    Please check out my hastily written online paper, “Ordering the Primitive Pythagorean Triples by Leg Difference and Size Using Generalized Pell Sequences”, in the Rational Argumentator!

  10. Ξ Says:

    Thanks Keith! I found a copy of your paper here.

  11. Keith Raskin Says:

    This question came up in a blog: Can there be two Pythagorean triples of the form {a,b,c} and {2a,d,c}. After much pondering and failed attempts to prove it impossible (see Natural Blogarithms — comments on Pythagorean triples — for details), my last response was this:

    Fascinating question, Chris. It amounts to being able to stack two inscribed rectangles in a circle (of whole number radius) with the same heights and expect whole number lengths. Stacking on a horizontal diameter

    We could generalize it to triples of the form {a,b,c}, {na,d,c} and get similarly inscribed rectangles, one with height n -1 times the other.

    I suspect that not only would an irrational crop up, but that the big transcendental pi itself would come out to contradict this.

    It also amounts to getting that the sinp = a/c, sinq =2a/c, cosp = b/c, cosq = d/c.

    Anybody out there know if there’s a proof regarding this?

  12. Math Teachers at Play and some other stuff « 360 Says:

    […] speaking of reading things, after reading Keith Raskin’s comment I headed over to Natural Blogarithms to look for Pythagorean Triple stuff, and I was immediately […]

  13. Keith Raskin Says:

    Answer (I think) to prime number problem referred to above by 360:

    Time for a solution yet? Given A and B are primes.

    Either A or B must be 2 in order for A + B to be prime (odd > 2)

    It must be B in order for A – B to be prime (assuming primes are positive: 2, 3, 5 …)

    The only prime bracketed between primes like this: A – 2, A, A + 2
    is 5, since A must be 1 or 2 mod 3, and either A – 2 or A + 2 is 0 mod 3, divisible by 3, which is only okay if it is 3 itself. A can’t be 3, since 1 is not prime; that’s how I know it’s got to be 1 or 2 mod 3.

    So, A = 5, b = 2

    A + B + A – B + A + B = 3A + B = 17 prime.

  14. Keith Raskin Says:

    My latest thoughts: If there exist Pyth. triples of the form {a, b, c}, {2a, d, c}; and if we can assume (which I think we can) that they are primitive and that the a and 2a can be represented as the even legs in the Euclidean Algorithm, then

    {a, b, c} = {n^2 – m^2, 2nm, n^2 + m^2}

    {2a, d, c} = {v^2 – u^2, 4nm, n^2 + m^2}.

    This implies that (n^2 + m^2)^2 – (4nm)^2 is a square, since it’s root must be v^2 – u^2 (an odd leg).

    So, n^4 – 14n^2m^2 + m^4 is a square, while n^4 – 14n^2m^2 + 49m^4 must also be a square, as its a squared binomial.

    This corresponds to x^2 – 14x + 1 and x^2 – 14x + 49 being squares, where x = n^2 and m= 1. They differ by 48. The only squares that differ by 48 are 1 and 49, 16 and 64, and 121 and 169, which respectively correspond to n^2 = 0, 15, and 20, none of which are permissible.

    Don’t know if this really leads anywhere.

    Anyone with knowledge or rumor of a proof, please come forward.

  15. Keith Raskin Says:

    Pythagorean Triples Summary and Clarification:

    Regarding the question about whether or not two Pythagorean triples of the form {a,b,c} and {2a,d,c} exist. I don’t think so — still don’t have a proof — but the question leads to lots of interesting questions about squares and rationals.

    Let’s assume such triples exist. We can also assume without loss of generality that they are both primitive triples. If we now assume that a is odd, we get a contradiction. Observe:

    {a,b,c} = {u^2 – v^2, 2uv, u^2 + v^2}
    {2a,d,c} = {2xy, x^2 – y^2, x^2 + y^2}

    for some u,v and x,y such that each pair is relatively prime and of opposite parity.

    That means 2xy = 2a ⇒ xy = a, which means a is even, since either x or y is even.

    Therefore a must be even and

    {a,b,c} = {2uv, u^2 – v^2, 2uv, u^2 + v^2}
    {2a,d,c} = {2xy, x^2 – y^2, x^2 + y^2}

    where 2xy = 4uv and x^2 + y^2 = u^2 + v^2.

    From here we get that c – 2a, c – a , c + a, and c + 2a are squares, because these are really

    x^2 – 2xy + y^2, u^2 – 2uv + v^2, u^2 + 2uv + v^2, and x^2 + 2xy + y^2

    OR (x – y)^2, (u – v)^2, (u + v)^2, and (x + y)^2.

    I suspect that no set of squares are spaced out like that. In other words, I seriously doubt that there exist four squares of the form n^2, n^2 + k, n^2 + 3k, and n^2 + 4k. However, that’s just my mathematical intuition. I just don’t think that a parabola or a square root function will bend through those four linearly spaced points without hitting an irrational.

    If such triples do exist, though, we would get the following bonus set of triples:

    {4m, 4(u^2 – 4uv + v^2) – 1, 4(u^2 – 4uv + v^2) + 1}
    {4(u – v), 4(u – v)^2 – 1, 4(u – v)^2 + 1}
    {4(u + v), 4(u + v)^2 – 1, 4(u + v)^2 + 1}
    {4w, 4(u^2 + 4uv + v^2) – 1, 4(u^2 + 4uv + v^2) + 1}

    for m, w that equal the square roots of c – 2a, c + 2a, respectively.

  16. Keith Raskin Says:

    LOOKS LIKE WE HAVE OUR PROOF (THANKS TO HENK)!

    I buy Henk’s assumptions about the factors of c. They must be primitive hypotenuses as long as they are prime, which we can assume. This has been proven by Euler and the proof can be found in Richard Friedberg’s “An Adventurer’s Guide to Number Theory.”

    AND it looks like the identities (below, also provided by Henk) provide our contradiction! If we assume that x and z are odd, then {xw – yz, yw + xz, kl} and {yw – xz, xw + yz, kl} represent
    {a, b, c} and {d, 2a, c}. Therefore a = 2yz = xw – yz. So, 3yz = xw.

    This is impossible, since x, y and w,z are relatively prime and x cannot be equal to w or z (nor can y be w or z). Yet if 3yz = xw, then x = 3z. But this forces y = w. Impossible!

    Maybe I’m missing something, as I’m coming up with this as I’m writing this submission (which I really shouldn’t be doing!) But this looks like the contradiction I’ve been looking for.

    THANKS HENK!!!

    PROBLEM RESOLVED?

    identities:

    (x^2 + y^2)(w^2 + z^2) = (xw – yz)^2 + (yw + xz)^2

    = (yw – xz)^2 + (xw + yz)^2

  17. Keith Raskin Says:

    Re: My August 30th post

    I think I thought I had good reason to assert that neither x nor y could equal to z or w, but i can’t see that reason at all now.

    Don’t know if there’s a solid contradiction there after all.

  18. Keith Raskin Says:

    HEY! How about a contest???

    Who can either unearth or craft a proof that no pair of Pythagorean triples of the form {a, b, c} and {2a, d, c} exists?

    Without loss of generality, I believe, we can safely assume that the triples are primitive and the doubled leg is the even one, ie a is even.

    We could extend this to any or all n such that no pair of Pythagorean triples of the form {a, b, c} and {na, d, c} exists.

    Whaddayou think???

  19. Keith Raskin Says:

    Full Disclosure: At the time I posted the above challenge a fairly esteemed blogger outlined a proof using the Fibonacci Box method that triples cannot be transformed to get the above result. I argued that I needed more than inability to transform; I needed proof of the impossibility of the existence of the triples above. We agreed to disagree.

    But perhaps the blogger is right and there is a proof resting on the use of Fibonacci Boxes and/or Ternary Trees.

  20. Keith Raskin Says:

    Please post the above comment under Keith Raskin.
    Thanks!

  21. Keith Raskin Says:

    The proof I’m discussing directly above using the Fibonacci Box method is definitely invalid for our purposes. We need to go beyond proving that modified triples will not result in the same hypotenuse, unless the modifications are totally unlimited, which they are not in the proof given.

  22. Keith Says:

    Corollaries and conjecture:
    If a pair of triples of the form {a,b,c} and {2a,d,c} exist, then it is easy to show that
    c – 2a, c -a, c + a and c + 2a are squares. Just look at their forms in Euclid’s algorithm,
    given that a must be even (must equal 2mn, c – a = m^2 – 2mn + n^2,
    c – 2a = r^2 – 2rs + s^2, etc.)
    Let these squares be represented as M^2, N^2, O^2 and P^2. The first and last two
    differ by a = N^2 – M^2, and the middle two differ by 2a. So, we can represent them
    as M^2, N^2, 3N^2 – 2M^2 and 4N^2 – 3M^2, with M and N odd. It appears from
    inspection of tables that when 3N^2 – 2M^2 or 4N^2 – 3M^2 is a square, the other
    misses being an odd square by a factor of 8. In other words, either O or P must be irrational, it appears. In still other words, if you take an interval with perfect square
    endpoints and advance it by double its length, one of the new endpoints is not a
    perfect square; the image of the original interval under the square root function has
    integral length, while the image of the new one has irrational length. If this conjecture is proven true, it would suffice in proving that the original triples could not
    exist.
    Also, if we represent O as N +q and P as N + p, then we get that q^2 + 2Nq over
    p^2 + 2Np must equal 2/3. There are some inherent constraints: p and q are even
    integers, with p bigger, and N must be greater than or equal to 1/2q^2 + Nq + 1.
    If that quotient can never be exactly 2/3 for qualifying entries of p, q and N, then no
    such original triples exist.

  23. Keith Raskin Says:

    Corollaries and conjecture:
    If a pair of triples of the form {a,b,c} and {2a,d,c} exist, then it is easy to show that c – 2a, c -a, c + a and c + 2a are squares. Just look at their forms in Euclid’s algorithm, given that a must be even (must equal 2mn, c – a = m^2 – 2mn + n^2, c – 2a = r^2 – 2rs + s^2, etc.)
    Let these squares be expressed as M^2, N^2, O^2 and P^2. The first and last two differ by a = N^2 – M^2, and the middle two differ by 2a. So, we can express them as M^2, N^2, 3N^2 – 2M^2 and 4N^2 – 3M^2, with M and N odd. It appears from inspection of tables that when 3N^2 – 2M^2 or 4N^2 – 3M^2 is a square, the other misses being an odd square by a factor of 8. In other words, either O or P must be irrational, it appears. In still other words, if you take an interval with perfect square endpoints and advance it by double its length, one of the new endpoints is not a perfect square; the image of the original interval under the square root function has integral length, while the image of the new one has irrational length. If this conjecture is proven true, it would suffice in proving that the original triples could not exist.
    Also, if we represent O as N +q and P as N + p, then we get that q^2 + 2Nq over p^2 + 2Np must equal 2/3. There are some inherent constraints: p and q are even integers, with p bigger, and N must be greater than or equal to 1/2q^2 + Nq + 1. If that quotient can never be exactly 2/3 for qualifying entries of p, q and N, then no such original triples exist.

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: