Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime in a clean intuitive way?

Solution 1:

Turning my comment into an answer: Some elementary results in number theory emerge from counting elements in group theory. For every integer $n$ we can construct the group $(\mathbb{Z}/n\mathbb{Z},+)$, whose elements are the integers modulo $n$, and whose operation is addition.

You can also think about making a group out of the integers modulo $n$ where the operation is multiplication. However, the major concern is that there are nonzero elements that are not invertible (zero is obviously not invertible). For example, you cannot find an $x$ for which $3x \equiv 1 (\operatorname{mod} 6)$, so $3$ is not invertible modulo $6$. To make a multiplicative group modulo $n$ we have to throw away the non-invertible elements. We write this group as $((\mathbb{Z}/n\mathbb{Z})^{\times},\times)$. It is an easy exercise that $m$ is multiplicatively invertible modulo $n$ if $m$ and $n$ are coprime. Thus, the order of $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is $\varphi(n)$.

Your result is that if $p,q$ are primes, then $$\varphi(pq) = (p-1)(q-1) = \varphi(p)\varphi(q)$$

$\varphi(pq)$ is the order of $(\mathbb{Z}/(pq)\mathbb{Z})^{\times}$, whereas $\varphi(p)\varphi(q)$ is the order of $(\mathbb{Z}/p\mathbb{Z})^{\times} \times (\mathbb{Z}/q\mathbb{Z})^{\times}$. Your result says that these groups have the same size. In fact, more is true: they are the same group (isomorphic)! This is part of (one form of) the Chinese Remainder Theorem. So, for a more "wholesome" argument (if you're unhappy with your current proof), you can say that these numbers are the same because they are counting the elements of the same object, but in different ways.

Solution 2:

A very different solution uses the classical formula $$ \sum_{d \mid n} \phi(d) = n. $$ One way to see this is to consider the fractions $1/n, \ldots, n/n$ in lowest terms. For $d \mid n$, group those fractions with denominator $d$ together; there are $\phi(d)$ of them, as is easily checked. Hence summing $\phi(d)$ over all such $d$ counts each of the $n$ fractions once.

You can deduce your particular case immediately from here without factoring: $(1+\phi(p))(1+\phi(q)) = pq = 1+\phi(p)+\phi(q)+\phi(pq)$. Expand the left-hand side and cancel to get $\phi(p)\phi(q) = \phi(pq)$.

This works in general: first note $$ \sum_{d \mid n,\ e \mid m} \phi(d) \phi(e) = \sum_{d \mid n} \phi(d) \sum_{e \mid m} \phi(e) = nm = \sum_{f \mid nm} \phi(f). $$ Now suppose ${\rm gcd}(n, m) = 1$, so ${\rm gcd}(d, e) = 1$ always. Inductively suppose $\phi(de) = \phi(d)\phi(e)$ for $(d, e) \neq (n, m)$ (the base case is trivial). You can check the operation $f \mapsto (d, e) = ({\rm gcd}(f, n), {\rm gcd}(f, m))$ maps the RHS's index set bijectively onto the LHS's, with the property that $de=f$. Hence inductively every term except the "topmost", where ($f=nm, d=n, e=m$), cancels. But that says $\phi(n)\phi(m) = \phi(nm)$, as needed.