**Background**


In [his beautifully short answer](https://mathoverflow.net/questions/30647/fibered-products-of-cyclic-groups/30656#30656) to [a previous question of mine](https://mathoverflow.net/questions/30647/fibered-products-of-cyclic-groups), 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](http://tinyurl.com/l3a7lp)). 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?



Lifting units from modulus n to modulus mn.
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$.


