Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

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

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?

share|cite|improve this question
I got stuck at the same point... Thanks for turning my comment to a question. – lhf Mar 14 '12 at 12:04
up vote 4 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

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.