gr.group theory - Lifting units from modulus n to modulus mn.

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?