Let and
Thus . -----------------(1)
By Bezout's identity we know that there exists non negative integers x and y such that .
But
Thus -------------(2)
(1) and (2) imply
A slightly different way.
We have (as Moo points out) thus (1)
Now let be a common divisor of and i.e.
From the first congruence we get and from the second thus it must be that hence
So every common divisor divides and by (1) we are done (because it's the greatest possible)