Proof of a formula involving Euler's totient function.

The third formula on the wikipedia page for the Totient function states that $$\varphi (mn) = \varphi (m) \varphi (n) \cdot \dfrac{d}{\varphi (d)}$$ where $d = \gcd(m,n)$.

How is this claim justified?

Would we have to use the Chinese Remainder Theorem, as they suggest for proving that $\varphi$ is multiplicative?

-

1
There might be a direct proof, but of course if you show that $\varphi$ is multiplicative (using the Chinese Remainder Theorem) and that $\varphi(p^a) = p^a - p^{a-1}$, then you get your result. – Joel Cohen Feb 29 '12 at 15:18
@lhf: You mean the group of units mod (m, n, mn)? I certainly don't know how to do that! – The Chaz 2.0 Mar 13 '12 at 2:21
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 $\phi(d)$. – lhf Mar 13 '12 at 2:22
– lhf Mar 14 '12 at 12:07

2 Answers

You can write $\varphi(n) = n \prod_{p \mid n} \left( 1 - \frac 1p \right)$. Using this identity, we have

$$\varphi(mn) = mn \prod_{p \mid mn} \left( 1 - \frac 1p \right) = mn \frac{\prod_{p \mid m} \left( 1 - \frac 1p \right) \prod_{p \mid n} \left( 1 - \frac 1p \right)}{\prod_{p \mid d} \left( 1 - \frac 1p \right)} = \varphi(m)\varphi(n) \frac{d}{\varphi(d)}$$

-

Thanks, Dane. That is concise! – The Chaz 2.0 Feb 29 '12 at 15:26

Hint $\$ A multiplicative function $\rm\:f(n)\:$ satisfies said identity if for all primes $\rm\:p\:$

$$\rm\ j\le k\ \Rightarrow\ \ f(p^{j+k}) = \frac{f(p^j)\: f(p^k)\: p^j}{f(p^j)}\ =\ p^j f(p^k)$$

Indeed we have $\rm\ \ \phi(p^{j+k})\ =\ p^{j+k}-p^{j+k-1}\ =\ p^j (p^k-p^{k-1})\ =\ p^j \phi(p^k)$

-

Thanks, Bill. I'll try to wrap my head around that. It seems useful. – The Chaz 2.0 Feb 29 '12 at 16:44
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 12, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.905384361743927, "perplexity_flag": "middle"}