Prove that if for , then .

Let be any common divisor of and . Then we have and therefore Similarly, let be any common divisor of and . Then we have and therefore How does it follow that and have the same common divisors?

Printable View

- July 2nd 2010, 04:52 PMDemandeurgcd Lemma
Prove that if for , then .

Let be any common divisor of and . Then we have and therefore Similarly, let be any common divisor of and . Then we have and therefore How does it follow that and have the same common divisors? - July 2nd 2010, 05:16 PMChris L T521
- July 2nd 2010, 07:24 PMmelese

When you wrote "therefore you should also notice that (by hypothesis). The same thing for . You should also note that (by hypothesis).

Now what you have is that if is a common divisor of and , then it's also of and . Similarly, if is a common divisor of and , then it's also of and .

Therefore, the pair has the same common divisors as the pair . In particular, the greatest common divisor.