9
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Jul 22, 2010 at 1:29
  • $\begingroup$ @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 :) $\endgroup$ Jul 22, 2010 at 1:32
  • $\begingroup$ 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 $\endgroup$
    – KConrad
    Jul 22, 2010 at 1:38
  • $\begingroup$ @Mariano: Thanks for the tip! @KConrad: Yes I realized this too -- a silly slip-up. Fortunately, the answerers got it right. $\endgroup$ Jul 22, 2010 at 1:38
  • $\begingroup$ KConrad: Thanks for improving the title! $\endgroup$ Jul 22, 2010 at 2:14

6 Answers 6

13
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – KConrad
    Jul 22, 2010 at 1:28
  • $\begingroup$ Thanks for both answers. I'm glad it was indeed elementary! $\endgroup$ Jul 22, 2010 at 1:43
  • 1
    $\begingroup$ It's a beautiful specimen in the collection of statements that become easier to prove after strengthening! $\endgroup$ Jul 22, 2010 at 7:27
9
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you very much! I wish I could have accepted both answers. $\endgroup$ Jul 22, 2010 at 1:45
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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: mathoverflow.net/questions/31495/… $\endgroup$ Jul 22, 2010 at 2:13
  • $\begingroup$ Added "commutative" to clarify. I don't actually know if it is necessary for the statement, but it is for the proof. $\endgroup$ Jan 28, 2023 at 3:52
  • $\begingroup$ Thanks. Back then I understood every ring to be commutative unless otherwise stated - which was of course bad. $\endgroup$ Jan 28, 2023 at 8:33
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Interesting. Thanks for the link to your course notes. $\endgroup$ Jul 22, 2010 at 1:47
  • 3
    $\begingroup$ Nice notes, Wadim. $\endgroup$
    – Will Jagy
    Jul 22, 2010 at 1:50
  • $\begingroup$ After the question was recently bumped, I noticed that the link is broken. I did not find it in the Wayback Machine, either. I browsed a bit the new website, but I did not see it: math.ru.nl/~wzudilin $\endgroup$ Jan 28, 2023 at 5:54
4
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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