Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

up vote 3 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|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.