# Thread: Euclidean Algorithm Proof

1. ## Euclidean 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,

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

3. 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?