**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?

`\mod`

and`\pmod`

here (and using amsmath, elsewhere) That'll save you the typing of all those spaces and get you prettier output :) – Mariano Suárez-Alvarez♦ Jul 22 '10 at 1:32