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?
Best Answer
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)$.