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?
 A: This is obvious by the Chinese Remainder Theorem: factor $n$ as $p_1^{e_1}\cdots p_k^{e_k}$, factor $mn$ as $p_1^{f_1}\cdots p_l^{f_l}$, so $l \ge k$ and $f_i \ge e_i$, and for $e_i > 0$ set $r' \equiv r (\mod p_i^{f_i})$, otherwise set $r' \equiv 1 (\mod p_i^{f_i})$.
A: More generally, we have the following result: If $R$ is an artinian commutative ring and $R \to S$ is a surjective ring homomorphism, then also $R^* \to S^*$ is surjective.
Proof: We may assume that $R$ is local (otherwise $R$ is a direct product of such rings and $R \to S$ decomposes into a product of such homomorphisms, etc.), and also $S \neq 0$. Then $S = R/p$ for some nilpotent ideal $p$. Since $1+p$ consists of units, it is even true that every preimage of a unit in $S$ is also a unit in $R$.
In the special case $R=\mathbb{Z}/mn$ this gives the proofs above using the Chinese Remainder Theorem.
A: There is an explicit formula for $r'$, and no need to invoke the Chinese Remainder Theorem; $$r'=r+kn{\rm\ where\ }k=\prod_{p\mid m,p\nmid r}p.$$ We need to show that $r'$ is relatively prime to $mn$. It suffices to show that $r'$ is relatively prime to $m$. Let $p$ be a prime dividing $m$. If $p$ divides $r$, then it doesn't divide $n$ (since $r$ and $n$ are relatively prime), and it doesn't divide $k$ (by construction of $k$), so it doesn't divide $kn$, so it doesn't divide $r'$. If $p$ doesn't divide $r$, then, by construction, it divides $k$, so it divides $kn$, so it doesn't divide $r'$. 
Schinzel showed me this construction 35 years ago. 
A: In my course on Modular forms (Lemma 11.5, p. 31) I use the same argument as Keith and zeb but in a different group theoretic context.
A: The answer with the chinese remainder theorem has already been given so I wanted to mention the following group theoretical remark. A group with the property that any subgroup isomorphism lifts to an automorphism of the group is called homogeneous. One of the motivations for studying homogeneous groups comes from model theory. You can see in "A complete classification of finite homogeneous groups" by C.H. Li that any abelian group whose sylow groups are homocyclic is homogeneous and in particular so are all cyclic groups.
A: 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$.
