Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Primitive Pythagorean Triple

  1. Mar 11, 2010 #1
    Definition: A primitive Pythagorean triple is a triple of natural numbers x,y,z s.t. [tex]x^2 + y^2 = z^2[/tex] and gcd(x,y,z)=1.

    note: d|gcd(x,y) => d|x and d|y
    => [tex]d^2|x^2[/tex] and [tex]d^2|y^2[/tex]
    Now [tex]z^2 = x^2 + y^2[/tex]
    => [tex]d^2|z^2[/tex]
    => d|z

    Thus, it follows that for any Pythagorean triple x,y,z, we must have that
    gcd(x,y)=gcd(x,z)=gcd(y,z)=gcd(x,y,z). Hence, we can replace gcd(x,y,z)=1 in the above definition by e.g. gcd(x,z)=1.

    [quote from my textbook]

    1) Why [tex]d^2|z^2[/tex] => d|z ? I tried writing down the meaning of divisibility and looked at the theorems about the basic properties of divisibility, but I still don't understand why it's true...

    2) The above shows that d|gcd(x,y) => d|z, but then why does it FOLLOW from the above that gcd(x,y)=gcd(x,z)=gcd(y,z)=gcd(x,y,z)? I don't understand this part at all.

    Any help is appreciated! :)
  2. jcsd
  3. Mar 11, 2010 #2
    The fundamental theorem tells us that d is composed of prime decomposition, and thus d^2 squares all these cases of prime decomposition. While the numerator may have primes not involved in this, it is still true in every case of division:

    [tex]\frac{(p^\alpha)^2}{(p^\beta)^2} [/tex] divides since the same primes must be involved in divisor and dividend.

    Actually, in the example given since x^2 +y^2 (assumed integers) is shown as divisible by d^2, then the other side of the equation must also be an integer.
    Last edited: Mar 11, 2010
  4. Mar 11, 2010 #3
    This will be a bit vague, but I hope I gives food for thought:

    1) If you asserted [tex]d \nmid z \implies d^2|z^2[/tex], you'd get into a contradiction.

    2) It may help to see "unique factorizations" as "collections of primes" (bags, actually), and to see "gcd" as the operation of intersection of those collections. So, f.i. if an element belongs to both collections A, B, then it belongs to the intersection of them. (Combine this with the definition of gcd for more than 2 arguments - associativity is involved.)

    Edit: Oops... Robert posted faster than me.
  5. Mar 11, 2010 #4
    1) I've already thought about it for quite a while before posting the question. Proof by contradiction definitely came to my mind before, but I'm not sure whether it will work here. In particular, I can't find where the contradiction is...and this is where I'm having trouble...
    Or perhaps there is an easy way to prove that [tex]d^2|z^2[/tex] => d|z?

    2) My textbook proved that d|gcd(x,y) => d|z, but I really don't see how it FOLLOWS that gcd(x,y)=gcd(x,z)=gcd(y,z)=gcd(x,y,z). How to prove it rigorously and formally?

  6. Mar 12, 2010 #5
    Reading through this thread just help me solved my HW that I am turning in an hour so thanks.

    1.) d^2|z^2 => d|z is a self-evident statement, as long as you think in lines of prime factorization. i.e if 2 is a divisor of 4, then 2^2 is a divisor of 4^2. Or, if (A^r)/(B^s) then (A^r)^2/(B^s)^2. Any description more formal would make use of what robert Ihnot said.

    2.) by the time you arrived at d|gcd(x,y) => d|z,
    you have demonstrated that d|x, d|y and d|z.
    d = gcd(x,y): using the fact that d|x and d|y
    d = gcd(y,z): using the fact that d|y and d|z
    d = gcd(x,z): using the fact that d|x and d|z
    d = gcd(x, y, z): using the fact that d|x, d|y and d|z

    This is true for the same reason that "note: d|gcd(x,y) => d|x and d|y" (quote of your text book)
  7. Mar 12, 2010 #6
    1) By definition, [tex]d^2|z^2[/tex] means there is an integer n such that [tex]z^2=nd^2[/tex]. Now I was thinking of taking the square root of both sides, but then we'll have √n which I'm worrying it may not be an integer, or will it even be defined? How to prove that n is the square of an integer? This is where I got stuck.

    2) I'm sorry, but I don't follow your idea...
    I think d is just a common divisior of x and y (not necessarily the greatest one)
    After showing that d|gcd(x,y) => d|z, why does it follow that gcd(x,y)=gcd(x,y,z)?? I really have no idea why this is true...

    Thanks for any help!!
  8. Mar 13, 2010 #7
    1.) I never think in terms of "d^2|z^2 => d|z" but instead the reverse: d|z => d^2|d^2. If you're convinced that the reverse (given the previous discussion of prime factorization from the fundamental theorem of arithmetic) is true then the former is implied. I can't demonstrate the derivation because I don't know how to input the mathematical notation.

    2.) Starting from the ppt: <x y z>
    This says two things:

    i) x^2 + y^2 = z^2
    ii) gcd(x,y,z) = 1

    There is a theorem that allows you to say: gcd(x,y,z) = gcd( gcd(x,y), z ) = 1.
    By convention, we define d = gcd(x,y),
    so we have gcd(x, y, z) = gcd( gcd(x,y), z ) = gcd(d, z) = 1.

    Because gcd(x,y) = d,
    d|x and d|y
    => d^2|x^2 and d^2|y^2
    => d^2|gcd(x^2, y^2)

    At this point we have that d|x and d|y, we want to show also that d|z in the following way:

    since gcd(x^2, y^2)
    there exist s, r (that live in the natural number set) such that
    gcd(x^2, y^2) = (x^2)*(s) + (y^2)*(r).

    => d^2 | (x^2)*(s) + (y^2)*(r)

    we can take advantage of the fact that x^2 + y^2 = z^2 and the fact that s, r could be any positive integer, so we choose s=r=1 to obtain:

    d^2 | z^2
    => d|z.

    Now we know that d|x, d|y, and d|z, we can then claim the following:

    i) because d|x and d|y, d = gcd(x,y); (Note, this is actually what we started with to get d|z)
    ii) similarly, because d|y and d|z, d = gcd(y,z)
    iii) similarly, because d|x and d|z, d = gcd(x,z)
    iv) similarly, because d|x and d|y and d|z, d = gcd(x,y,z) = 1 (by definition of ppt)

    thus d = gcd(x,y) = gcd(y,z) = gcd(x,z) = gcd(x,y,z) = 1.
  9. Mar 13, 2010 #8
    Factor everything into primes and consider the exponents on the left side. They're all even, and so all the exponents on the right side must also be even, by the fundamental theorem of arithmetic. This observation should help.
  10. Mar 14, 2010 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Note also, that the proof in the OP can be accomplished (try it later) without ever having to get into d^2 in the first place. But the key is to write out the prime factorization, which you have been avoiding so far. Why don't you start by writing out the prime factorization of x and y?

    Also, please use the homework section for such questions in the future.

    To others: Please only provide hints and suggestions, not complete solutions/derivations.
    Last edited: Mar 14, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook