Show that: and
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)