Why is the formula for calculating euler totient true?

Question

I know that the way to calculate Euler Totients of a number X is to take the prime factorization of X and then use the rule $φ(p^n) = p^n - p^{n-1}$ on each of those prime factorizations and multiply all of the results together. My question is why do these hold true. First, what allows you to say that $φ(A \cdot B) = φ(A) \cdot φ(B)$ and also why $φ(p^n) = p^n - p^{n-1}$.

Answer 1

The totient function is multiplicative, but not completely multiplicative, that is

We have that $\varphi(ab)=\varphi(a)\varphi(b)$ whenever $(a,b)=1$; but not in general.

Here's a proof of this:

P Suppose that $(a,b)=1$. We show that $(a,y)=(x,b)=1$ if and only if $(ax+by,ab)=1$. Indeed, suppose that there is a prime $p\mid (ax+by,ab)$. Then $p\mid ab$, so $p\mid a$ or $p\mid b$. We can assume $p\mid a$. Thus $p\not\mid b$, since $(a,b)=1$. It follows that $p\mid ax+by$ and $p\mid a$ so $p \mid by$, so $p\mid y$ since $p\not\mid b$. Thus $p\mid (a,y)$. In the case $p\mid b$ and $p\not\mid a$ we'd get $p\mid (x,b)$. In any case $(ax+by,ab)>1\implies (a,y)$ or $(b,x)>1$.

Now suppose $p\mid (a,y)$. Then $p\mid ax+by$, and $p\mid ab$, so $p\mid(ax+by,ab)$. Similarily, if $p\mid (b,x)$, $p\mid(ax+by,ab)$. Here we do not need the assumption that $(a,b)=1$.

Conclusion Suppose $(a,b)=1$. As $x$ and $y$ range over $\{x:(b,x)=1\}$ and $\{y:(y,a)=1\}$, $ax+by$ ranges over $\{z:(z,ab)=1\}$. Thus, whenever $(a,b)=1$ $$\varphi(ab)=\varphi(a)\varphi(b)$$

Further, we claim

If $p$ is prime, then $\varphi(p^n)=p^n-p^{n-1}$

P Consider the numbers $$\{1,2,3,\ldots,p^{n}\}$$

How many of those are not coprime to $p^n$? Well, we want those numbers $1\leqslant k\leqslant p^n$ such that $p\mid k$. This means $k=pj$, so $1\leqslant pj\leqslant p^n$, thus $1\leqslant j\leqslant p^{n-1}$ and there are $p^{n-1}$ such elements. Thus the number of elements which are coprime to $p^{n}$ is $p^n-p^{n-1}$. Thus

Let $p_1,\ldots, p_r $ be the prime factors of $n$. Then $$\varphi(n)=n\prod_{i=1}^r\left(1-\frac 1{p_i}\right)$$

ADD In general, $$\frac{\varphi(ab)}{ab}\frac{\varphi(d)}d=\frac{\varphi(a)}a\frac{\varphi(b)}b$$

where $d=(a,b)$.