## A fact about residue systems

Fix a natural number $n$. A residue system mod $n$ is a set $S$ of integers such that every integer is congruent mod $n$ to a unique element of $S$. Suppose $S$ and $bS$ are both residue systems mod $n$; prove that $b$ and $n$ are relatively prime.

First suppose $n = 0$. In this case, the only residue system is $\mathbb{Z}$. Certainly then $b\mathbb{Z}$ is only a residue system if $b = \pm 1$; thus 1 is a greatest common divisor of $n$ and $b$, and hence these two are relatively prime.

Now suppose $n > 0$ and that $S$ and $bS$ are residue systems mod $n$. In particular, there exists $s \in S$ such that $bs \equiv 1$ mod $n$. Say $kn = bs - 1$, so that $bs - kn = 1$. Thus 1 is a greatest common divisor of $b$ and $n$, so that these are relatively prime.