One important fact:
- If and and , then
Basically, any common divisor of two numbers will divide the gcd of those two numbers.
___________
Let .
Multiply both sides by :
Since and , then . (Why?)
But this means and which implies because of .
But . Can you conclude?