Properties of Euler’s totient function

elementary-number-theoryintuitiontotient-function

I'm having some trouble understanding the following proposition:

Let $\phi$ be the Euler's totient function. If $p$ is a prime number and $n,m \in \mathbb N$, then:

  1. $\phi(p)=p-1$
  2. $\phi(p^n) = p^n – p^{n – 1}$
  3. If $\gcd(m,n) = 1$, then $\phi(mn)=\phi(m)\phi(n)$

I can understand and prove proposition number (1), but as for (2) and (3) I'm not understanding intuitively what they are saying and why they are true. Can someone explain to me the intuition behind proposition (2) and (3) and show me the proof? Thanks

Best Answer

Why (3) is true intuitively:

For each $m_{i}$, $n_{j}$ respectively coprime and less than $m$, $n$, we can build one and only one $x_{ij}$ less than $m.n$ such that $x_{ij}$ has as remainder $m_{i}$ modulo $m$, and $n_{j}$ modulo $n$ (this is essentially the chinese remainder theorem). Such number $x_{ij}$ is coprime with $m$ and $n$, so coprime with $m.n$. The $x_{ij}$ are mutually different as they produce different remainders modulo $m$ and $n$. And their number is the number of couples $(m_i, n_j)$ so $ϕ(m).ϕ(n)$.

Related Question