1. ## 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!

2. 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.

3. Originally Posted by hollywood
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!

4. 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)

5. Originally Posted by hollywood
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!

6. 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.