(mod n) for some integer k

Now we show the set of divisors of a and n are the same as the set of divisors of b and n.

Let d divide a and n.

then d divides the RHS so it divides b as well.

Let d divide b and n.

then d divides the LHS so it divides a as well.

Thus the set of divisors is the same, so their greatest element is the same. so (a,n)=(b,n)