Note that:
So starting from this point we can prove it as follows:
If , then since we have .
In particular, any common divisor of and is also a divisor of , hence mod , so . .
Conversely, let be any common divisor of and . Then mod , therefore is a common divisor of and as well.
Thus, since we showed the above two pairs have the same set of common divisors, it follows they have the same greatest commond divisor, i.e. .
Let be any common divisor of and . Let be any odd prime factor of . Then , being prime, divides at least one of . WLOG let us assume . Then mod . Recall that , therefore mod . But this means is a common nontrivial divisor of and , contradicting that .
Thus, our assumption that exists must have been wrong. Then this implies that .
Now, let be any common PRIME divisor of and . We already showed does not divide , therefore divides the only remaining factor of , which is . Thus, (since is prime). This implies that any common divisor is a power of . Notice that this also implies that both and are odd (whenever the GCD we are looking for is greater than 1). Thus, does not divide so the only possible nontrivial common divisor is . (IOW, other than , the only possible divisor is ).
We show by example that the GCD of is not only possible, but realized. Set . Then the problem's hypthoses are satisfied and , , which indeed have a GCD of .
The other possibility admitted by our proof is the case of the trivial GCD (i.e. GCD = 1). To see that this is realized, set . Then , , which indeed have a GCD of .