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
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,
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).
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?
