Let be an integer that divides both and . Then and for some pair of integers . So,

Similarly, .

So, clearly divides both and for any common divisor of . So, is a common divisor of both and . All that is left is to show that any other common divisor of and must divide