Properties of Euler's totient function

Question

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

Answer 1

Let $(a,b)$ denote the gcd of $a$ and $b$, then

$$ \varphi(n)\triangleq\sum_{k\le n,(k,n)=1}1=\sum_{k\le n}\left\lfloor1\over(k,n)\right\rfloor $$

where $k$ runs from 1 to $n$. By the property that

$$ \sum_{d|n}\mu(d)=\left\lfloor\frac1n\right\rfloor $$

we obtain

$$ \begin{aligned} \varphi(n) &=\sum_{k\le n}\sum_{d|k,d|n}\mu(d)=\sum_{d|n}\mu(d)\sum_{k=jd\le n}1 \\ &=\sum_{d|n}\mu(d)\sum_{j\le n/d}1=\sum_{d|n}\mu(d)\cdot\frac nd \\ \end{aligned} $$

Because the $n$ and Mobius function $\mu(n)$ are multiplicative, we deduce that $\varphi(n)$ is multiplicative as well due to the property of Dirichlet convolution.

For prime power $p^n$ ($n\ge1$), we have

$$ \varphi(p^n)=\sum_{k=0}^n\mu(p^k)p^{n-k}=\mu(1)p^n+\mu(p)p^{n-1}=p^n-p^{n-1} $$

Answer 2

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