0

Of course we are familiar with the notion that if $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$ ($p_{i}$ distinct primes; $k_{i}>0$), then $$\varphi\left(n\right)=n\left(1-1/p_{1}\right)\left(1-1/p_{2}\right)\cdots\left(1-1/p_{r}\right),$$ where $\varphi$ is the Euler totient function.

The goal is to prove this using the fact that $\varphi$ is multiplicative, that is, $$\varphi\left(mn\right)=\varphi\left(m\right)\varphi\left(n\right),$$ given that $m$ and $n$ are coprime.

Proving the former notion from the multiplicative property. But how do we prove the multiplicative property of $\varphi$ without using that notion?

Andrés E. Caicedo
  • 77,517
  • 9
  • 216
  • 343
vantonio1992
  • 546
  • 4
  • 8
  • What is the definition of $\varphi$ you are using? – Zev Chonoles Sep 06 '13 at 04:50
  • 4
    Note that $\phi(mn)=\phi(m)\phi(n)$ if and only if $m$ and $n$ are coprime. For example, $\phi(2)=1$, but $\phi(2\cdot2)=\phi(4)=2\ne1\cdot1=1$. That might make things easier. – William Ballinger Sep 06 '13 at 04:51
  • 1
    here: http://www.proofwiki.org/wiki/Euler_Phi_Function_is_Multiplicative – Salech Alhasov Sep 06 '13 at 04:54
  • @AnthonyCarapetis, the goal this time is to prove it the other way around. So I need to prove the multiplicative property first. – vantonio1992 Sep 06 '13 at 05:05
  • @vantonio1992: oh sorry, I clearly skimmed too fast. – Anthony Carapetis Sep 06 '13 at 05:08
  • You can try Chinese remainder theorem, or equivalently, the Bézout's identity. Of course you can also use induction. As an aside, try prove the more general identity: $$\frac{\phi(mn)}{\phi(m)\phi(n)}=\frac{P}{\phi(P)},$$ where $P$ is the product of primes dividing both $m$ and $n$. :) – awllower Sep 06 '13 at 05:18
  • Duplicate of [What's the proof that the Euler totient function is multiplicative?](http://math.stackexchange.com/questions/192452/whats-the-proof-that-the-euler-totient-function-is-multiplicative) and http://math.stackexchange.com/questions/454154 and ... just google the title and add "stackexchange", in most of the cases it's a duplicate. – Martin Brandenburg Sep 06 '13 at 18:42

2 Answers2

4

Let us start from the definition of Euler's Phi: $$ \varphi(n)=|\{x\in [1,n-1] | \gcd(x,n)=1\}|, $$ i.e., $\varphi(n)$ is the number of positive integers at most equal to $n$ and prime to $n$.

Now, if $n$ and $m$ are coprime, we want to show that $\varphi(mn)=\varphi(n)\varphi(m)$. For this, let us denote: $$ \Phi(n)=\{x\in [1,n-1] | \gcd(x,n)=1\}. $$ We just want to show that $\Phi(mn)$ has the same cardinality as $\Phi(m)\times\Phi(n)$. To do this, we can use the Chinese Remainder Theorem (since $m$ and $n$ are coprime) to construct a bijection between the two sets. This bijection is given by $x \rightarrow (x\bmod{m},x\bmod{n})$.

The only thing you need to check is that $x$ is prime to $mn$, if and only if, $x \mod {m}$ is prime to $m$ and $x \mod {n}$ is prime to $n$.

minar
  • 781
  • 4
  • 11
1

The group $(\mathbb{Z}/n\mathbb{Z})^*$ has order $\phi(n)$. Because $(\mathbb{Z}/nm\mathbb{Z})^*\simeq (\mathbb{Z}/n\mathbb{Z})^*\times (\mathbb{Z}/m\mathbb{Z})^*$ for coprime $n$ and $m$ it follows $\phi(nm)=\phi(n)\phi(m)$.

Dietrich Burde
  • 124,904
  • 8
  • 79
  • 146