Background
In his beautifully short answer to a previous question of mine, Robin Chapman asserted the following.
Let $m,n,r$ be natural numbers with $r$ coprime to $n$. Then there is $r' \equiv r \mod n$ which is coprime to
$mn$.
Letting $C_n$ denote the cyclic group of order $n$, the above statement is equivalent to this:
Every automorphism of $C_n$ lifts to an automorphism of $C_{nm}$ for all $m$.
Since that is the context of the question I asked, I thought that this fact ought to have an elementary group-theoretical derivation, but alas I have been unable to find one. I asked a number theorist colleague of mine and he gave me this "sledgehammer proof" (his words):
Since $r$ is coprime to $n$, the arithmetic progression $r + kn$ for $k=1,2,\ldots$ contains an infinite number of primes (by a theorem of Dirichlet's). Since only a finite number of those primes can divide $m$, there is some $k$ for which $r'= r+kn$ is a prime which does not divide $m$, and hence neither does it divide $nm$.
Question
Is there an elementary (and preferably group-theoretical) proof of this result?
Best Answer
This can be done in an elementary way using the Chinese remainder theorem. First of all, note $m$ only appears in the conclusion in the context of the product $mn$. For any common prime factor of $m$ and $n$ suck that prime's contribution to $m$ into $n$ instead, which changes the meaning of $m$ and $n$ but does not alter $mn$ nor alter the meaning of $r$ being coprime to $n$. It does change the meaning of what a congruence mod $n$ is, but only by making the condition even stronger. Thus we are reduced to the case that $m$ and $n$ are relatively prime, so now solve $r' \equiv r \bmod n$ and $r' \equiv 1 \bmod m$.