Hello, I'm really confused about how to show the following proof.

* Let a,b,n∈Z(all real integers) .Prove that if n>0,then gcd(an,bn)= n·gcd(a,b).

I'm confused on how to start this proof, and would greatly appreciate any help/tips.

Thanks,

Printable View

- October 10th 2010, 02:14 PMspoc21Euclidean Algorithm Proof
Hello, I'm really confused about how to show the following proof.

* Let a,b,n∈Z(all real integers) .Prove that if n>0,then gcd(an,bn)= n·gcd(a,b).

I'm confused on how to start this proof, and would greatly appreciate any help/tips.

Thanks, - October 10th 2010, 07:59 PMTinyboss
Since n divides an and bn, you know that n divides gcd(an,bn). So gcd(an,bn)=nk for some k. Clearly k must divide a and b, and the largest k that does is gcd(a,b).

- October 11th 2010, 04:16 AMHallsofIvy
If m= gcd(a,b) then b= pm and a= qm for some integers p and q. Then an= qmn and bn= pmn so that nm is a divisor of both an and bn. Suppose there were a larger common divisor. That is, suppose there exist integer u such that u> n and an= ux, bn= uy for integers x and y. Can you show that u is a common divisor of a and b as well?