Proving formula involving Euler's totient function

Question

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?

Answer 1

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

Answer 2

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$).
Proof:
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.