Results 1 to 6 of 6

Math Help - Primitive Pythagorean Triple

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Arrow Primitive Pythagorean Triple

    Definition: A primitive Pythagorean triple is a triple of natural numbers x,y,z s.t. x^2 + y^2 = z^2 and gcd(x,y,z)=1.

    note: d|gcd(x,y) => d|x and d|y
    => d^2|x^2 and d^2|y^2
    Now z^2 = x^2 + y^2
    => d^2|z^2
    => 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 d^2|z^2 => 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.

    Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236
    1) By definition, d^2|z^2 means there is a positive integer n such that z^2=nd^2. You can prove by contradiction that n is the square of an integer, so that n=m^2 and z^2=m^2d^2 and since z and d are positive and you can choose m positive, z=md, which is the definition of d|z.

    2) If you extend the previous proof by a minor step, you can get gcd(x,y)=gcd(x,y,z) (Prove that a divisor of one is a divisor of the other, in both directions). And a similar argument would apply for gcd(x,z) and gcd(y,z).

    Post again if you're still having trouble.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    Quote Originally Posted by hollywood View Post
    1) By definition, d^2|z^2 means there is a positive integer n such that z^2=nd^2. You can prove by contradiction that n is the square of an integer, so that n=m^2 and z^2=m^2d^2 and since z and d are positive and you can choose m positive, z=md, which is the definition of d|z.

    2) If you extend the previous proof by a minor step, you can get gcd(x,y)=gcd(x,y,z) (Prove that a divisor of one is a divisor of the other, in both directions). And a similar argument would apply for gcd(x,z) and gcd(y,z).

    Post again if you're still having trouble.
    1) I got to the point z^2=nd^2 using the definition of divisibility. 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 exactly where I got stuck. I don't see why it's necessarily true...

    2) Why d|gcd(x,y) => d|z means that gcd(x,y)=gcd(x,y,z)?? Once you have this, the other ones gcd(x,y)=gcd(x,z)=gcd(y,z)=gcd(x,y,z) just follow by symmetry. But I have no idea how to establish the first one, namely, how to prove that gcd(x,y)=gcd(x,y,z)?

    Thanks for helping!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236
    1) Suppose n is not the square of an integer. Let n=ms^2, where m>1 has no square divisors. Let p be a prime divisor of m. We have z^2 = nd^2 = ms^2d^2, and since the powers of p in z^2, s^2, and d^2 are even, the power of p in m must be even. But then m has a square factor. By contradiction, therefore, n must be the square of an integer.

    2) We need to prove that if d divides gcd(x,y) then d divides gcd(x,y,z) (forwards) and that if d divides gcd(x,y,z) then d divides gcd(x,y) (backwards). Then the set of divisors of gcd(x,y) will be the same as the set of divisors of gcd(x,y,z), so gcd(x,y)=gcd(x,y,z)

    Forwards: if d divides gcd(x,y) then the previous proof shows that d divides z, so d is a common factor of gcd(x,y) and z, so d divides gcd(gcd(x,y),z) = gcd(x,y,z).

    Backwards: if d divides gcd(x,y,z) = gcd(gcd(x,y),z), then it is a common factor of gcd(x,y) and z, and therefore divides gcd(x,y)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    Quote Originally Posted by hollywood View Post
    1) Suppose n is not the square of an integer. Let n=ms^2, where m>1 has no square divisors. Let p be a prime divisor of m. We have z^2 = nd^2 = ms^2d^2, and since the powers of p in z^2, s^2, and d^2 are even, the power of p in m must be even. But then m has a square factor. By contradiction, therefore, n must be the square of an integer.

    2) We need to prove that if d divides gcd(x,y) then d divides gcd(x,y,z) (forwards) and that if d divides gcd(x,y,z) then d divides gcd(x,y) (backwards). Then the set of divisors of gcd(x,y) will be the same as the set of divisors of gcd(x,y,z), so gcd(x,y)=gcd(x,y,z)

    Forwards: if d divides gcd(x,y) then the previous proof shows that d divides z, so d is a common factor of gcd(x,y) and z, so d divides gcd(gcd(x,y),z) = gcd(x,y,z).

    Backwards: if d divides gcd(x,y,z) = gcd(gcd(x,y),z), then it is a common factor of gcd(x,y) and z, and therefore divides gcd(x,y)
    1) I think we may also prove directly from z^2=nd^2. All prime factors of z^2 and d^2 must have even exponents, so by unique prime factorization, ALL prime factors of n must have even exponents (i.e. n is a perfect square), and so n is an integer. (So the key is to use unique prime factorization theorem which I was missing before. The definition of divisibility alone is not enough.)
    Thus, d|x <=> d^2|x^2


    2) I am not familiar with the propery gcd(gcd(x,y),z)=gcd(x,y,z), so I'm trying a different proof.

    Let d=gcd(x,y) => d|x and d|y
    => d^2|x^2 and d^2|y^2
    Now z^2 = x^2 + y^2
    => d^2|z^2
    => d|z
    So d|x, d|y, and d|z
    => d is a common divisor of x,y,z, so d gcd(x,y,z)
    i.e. gcd(x,y) ≤ gcd(x,y,z).

    Conversely, let g=gcd(x,y,z) => g|x, g|y, g|z
    => g|x, g|y
    => g is a common divisor of x and y
    => g ≤ gcd(x,y)
    i.e. gcd(x,y,z) ≤ gcd(x,y)

    Hence, gcd(x,y,z) = gcd(x,y)

    Is this a valid proof, too? Can someone confirm my work, please?

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236
    Well done!!!

    Your proofs for both 1) and 2) are not only correct, but I like them a lot better than my attempts.

    For 1), I think you are correct - prime factorization is the key to recognizing n is a perfect square. And for 2), you don't depend on that gcd(gcd(x,y),z)=gcd(x,y,z) property or that the set of divisors of a number is unique.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. About Pythagorean triple...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 8th 2010, 09:15 PM
  2. Infinite number of primitive Pythagorean triples
    Posted in the Number Theory Forum
    Replies: 13
    Last Post: March 29th 2010, 03:39 PM
  3. Solving Primitive Pythagorean Triangle
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: August 5th 2009, 12:32 PM
  4. Pythagorean Triple
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 13th 2009, 10:44 AM
  5. Pythagorean triple
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 8th 2009, 07:51 PM

Search Tags


/mathhelpforum @mathhelpforum