MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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$.


Is there an elementary (and preferably group-theoretical) proof of this result?

share|cite|improve this question
Doesn't this just follow from the Chinese Remainder Theorem? Take some $s$ coprime to $m$. Then the system of congruences $x \equiv r \, mod \, n$, $x \equiv s \, mod \, m$ has a solution $x$ which is coprime to $m$ and $n$, hence to $mn$. Or am I utterly mistaken? – Eben Freeman Jul 22 '10 at 1:29
@Eben, you can use \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
Eben, you missed the point: m and n may have a factor in common. The point is not to just lift a number from modulus n to modulus mn but to lift a unit mod n to a unit mod mn. For example, consider lifting 3 mod 5 to a unit mod 30. The mod 30 lifts of 3 mod 5 are 3, 8, 13 -- okay, we can lift to 13 as a unit but we can't lift to 3 or 8 as units mod 30. – KConrad – KConrad Jul 22 '10 at 1:38
@Mariano: Thanks for the tip! @KConrad: Yes I realized this too -- a silly slip-up. Fortunately, the answerers got it right. – Eben Freeman Jul 22 '10 at 1:38
KConrad: Thanks for improving the title! – José Figueroa-O'Farrill Jul 22 '10 at 2:14
up vote 13 down vote accepted

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$.

share|cite|improve this answer
My solution and zeb's are more or less the same but I made a reduction step to avoid the messy handling of the prime power exponents. But it is the exact same idea. – KConrad Jul 22 '10 at 1:28
Thanks for both answers. I'm glad it was indeed elementary! – José Figueroa-O'Farrill Jul 22 '10 at 1:43
It's a beautiful specimen in the collection of statements that become easier to prove after strengthening! – Victor Protsak Jul 22 '10 at 7:27

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})$.

share|cite|improve this answer
Thank you very much! I wish I could have accepted both answers. – José Figueroa-O'Farrill Jul 22 '10 at 1:45

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.

share|cite|improve this answer

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.

share|cite|improve this answer
Interesting. Thanks for the link to your course notes. – José Figueroa-O'Farrill Jul 22 '10 at 1:47
Nice notes, Wadim. – Will Jagy Jul 22 '10 at 1:50

More generally, we have the following result: If $R$ is an artinian 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.

share|cite|improve this answer
Just to avoid misunderstanding... not every preimage of a unit in $\mathbb{Z}/n$ is a unit in $\mathbb{Z}/mn$, but that's alright because $\mathbb{Z}/mn$ is not local for $m,n>1$. This answer would also be appropriate for this other related question of mine:… – José Figueroa-O'Farrill Jul 22 '10 at 2:13

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.

share|cite|improve this answer
Thanks. This answers another question of mine:… The link to Li's paper is… – José Figueroa-O'Farrill Jul 22 '10 at 2:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.