Primitive Pythagorean Triple

  • Thread starter kingwinner
  • Start date
  • #1
1,270
0

Main Question or Discussion Point

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! :)
 

Answers and Replies

  • #2
1,056
0
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:
  • #3
695
2
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.
 
  • #4
1,270
0
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?

Thanks!
 
  • #5
14
0
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.
Thus
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)
 
  • #6
1,270
0
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.
Thus
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)
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!!
 
  • #7
14
0
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.
 
  • #8
131
40
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.
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.
 
  • #9
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
17
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:

Related Threads on Primitive Pythagorean Triple

  • Last Post
Replies
7
Views
5K
Replies
4
Views
3K
Replies
11
Views
3K
Replies
1
Views
2K
  • Last Post
Replies
14
Views
3K
Replies
9
Views
5K
Replies
16
Views
10K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
9K
Top