This question is motivated by lhf's comment here .

"It'd be nice to relate this formula with the natural mapping $U_{mn} \to U_m \times U_n$ by proving that the kernel has size $d$ and the image has index $\varphi(d)$."

Here, $U_k$ denotes the group of units of the ring $\mathbb{Z} / k \mathbb{Z}$ whenever $k$ is a positive integer.

I'm trying to prove the formula $$ \varphi(mn) = \varphi(m)\varphi(n) \frac{d}{\varphi(d)} $$ by considering the natural map $\eta\colon U_{mn} \to U_m \times U_n$ (i.e. the map sending $\overline{x} \mapsto (\overline{x},\overline{x})$, where the bar denotes reduction mod $mn$, $m$, or $n$, respectively).

I've been able to show that the kernel has the right size as follows:

The kernel of $\eta$ consists of the elements $\overline{x} \in U_{mn}$ with $x \equiv 1 \bmod m$ and $x \equiv 1 \bmod n$. The integers $x$ which satisfy these conditions are those of the form $x = \frac{mn}{d}k + 1$ for $k \in \mathbb Z$. On the other hand, any such integer $x$ is relatively prime to $mn$, and hence gives and element $\overline{x} \in U_{mn}$. Therefore, $\ker \eta$ consists of the $d$ distinct elements $\overline{x}$, where $x = \frac{mn}{d}k + 1$ and $k \in \{1,\ldots,d\}$.

Once it has been shown that the image has index $\varphi(d)$, the first isomorphism theorem gives $$ \frac{U_{mn}}{\ker \eta} \cong Im(\eta), $$ and so $$ \frac{\varphi(mn)}{d} = \frac{|U_{mn}|}{|\ker \eta|} = |Im(\eta)| = \frac{|U_m \times U_n|}{|U_m \times U_n:Im(\eta)|} = \frac{\varphi(m)\varphi(n)}{\varphi(d)}, $$ or $$ \varphi(mn) = \varphi(m)\varphi(n) \frac{d}{\varphi(d)}. $$

I'm having trouble showing the image has the right index.

I've noticed that $\eta(\overline{x}) = \eta(\overline{x + \frac{mn}{d}})$, so the image consists the images of the elements $\overline{x}$ with $1 \leq x < \frac{mn}{d}$. I'm not sure if this is going anywhere, though. Any suggestions?


2 Answers 2


I'll adjust your notation a bit, using $x\in U_{mn}$ for an invertible element of $\mathbb{Z}/mn\mathbb{Z}$, using $\bar x\in U_m$ for the residue class of $x$ modulo $m$, and using $\tilde x \in U_n$ for the residue class of $x$ modulo $n$.

The image of your map $x \mapsto (\bar x,\tilde x)$ is generally smaller than $U_m \times U_n$ because $\bar x$ and $\tilde x$ will always be the same modulo $d$. We first choose a reduced residue system $\{a_1=1, a_2, \ldots, a_{\varphi(d)}\}$ modulo $d$ from the elements $U_{n}$ and consider the images of the maps $f_i: x \mapsto (\bar x, a_i\tilde x)$. (Note that each $a_i$ is invertible modulo $n$.) It's clear that the images of these maps are disjoint, have the same size, and that we are studying the special case $f_1:x \mapsto (\bar x, \tilde x)$. In fact, the union of these images is all of $U_m \times U_n$, as we now show.

Take any $(y,z) \in U_m \times U_n$. We show it is equal to some $f_i(x)$ where $a_i \equiv zy^{-1} \pmod{d}$. By a slight generalization of the Chinese Remainder Theorem, there is a unique $x$ modulo $\frac{mn}{d}$ such that $$x \equiv y \pmod{m}\qquad \qquad \text{and} \qquad \qquad x \equiv z{a_i}^{-1} \pmod{n}.$$ Then $f_i(x)=(\bar x, a_i \tilde x) =(y,z)$. (In fact, the $d$ preimages of $(y,z)$ are the elements $x+\frac{mn}{d} k$ with $0 \leq k \leq d-1$.)

A generalization of the Chinese Remainder Theorem is required because $m$ and $n$ share the factor $d$. Such systems of congruences have a solution as long as they are compatible modulo $d$, and this solution is unique modulo $\rm{lcm}(m,n)=\frac{mn}{d}$. Our system is compatible modulo $d$, since $y \equiv z {a_i}^{-1} \pmod{d}$.

Thus, the index of the image of $x \mapsto (\bar x, \tilde x)$ is $\varphi(d)$.


Jonas Kibelbek directly proved that the index of the image of $\eta$ is $\phi(d),$ and below is an alternative by proving an exact sequence, which I hope might clarify the matter somewhat.

The exact sequence I want to prove is

$$0\rightarrow \text{Ker}(f)\rightarrow U_{mn}\overset{f}{\rightarrow}U_m\times U_n\overset{g}{\rightarrow} U_d\rightarrow0,$$

where $f(x+mn\mathbb Z)=(x+m\mathbb Z, x+n\mathbb Z),$ and $g(x+m\mathbb Z, y+n\mathbb Z)=xy^{-1}+d\mathbb Z$ (Here the inverse is taken modulo $d$).
Firstly, $\forall (a+d\mathbb Z)\in U_d,$ we have that $g(a+m\mathbb Z, 1+n\mathbb Z)=(a+d\mathbb Z),$ so $g$ is surjective. Further, it is clear that $g\circ f$ vanishes. Conversely, if $(x+m\mathbb Z, y+n\mathbb Z)\in U_m\times U_n$ is such that $x\equiv y\pmod d,$ then, by a slight generalisation of Chinese rmainder theorem, as in Kibelbek's answer, $\exists z$ such that $\begin{cases}z\equiv x\pmod m\\z\equiv y\pmod n\end{cases}.$ Thus the sequence is exact. Q.E.D.

P.S. This sequence is in essence the sequence in this answer, with some reductions and modifications; I mark this answer as CW, for there is nothing new in this answer.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .