# 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?

Why is does euler’s totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime?
I had my own proof for it but I really don’t like it (it feels not intuitive at all because it requires factoring!) and I feel there must be a more direct way to do it by a different counting argument.

If anyone has one it would be greatly appreciated!

My “proof”:

Recall:

$\phi(N) =$ the number of elements that are relatively prime to $N$ (i.e. have a mod inverse)

$N = pq$ where $p$ and $q$ are prime.

Let’s count the number of elements between $1$ to $N-1$ that are NOT relatively prime to $p$ and $q$. Those elements must have at least $p$ or $q$ as one of its factors. So let include all number that have $p$ as a factor and $q$ as a factor and are in the given range.

thus:

$0p, 1p, 2p, …, kp, …, p(q-1)$

and

$0q,1q,2q,…,jp,…,q(p-1)$

That gives a count of:

$N – p – q + 1 = pq – p – q + 1 = (p -1)(q-1)$

QED as required.

The reason I am not happy with this argument is that it seems to me there should be a clear intuitive way of doing it without having to factor or substitute the definition of $N$. This seems clear because multiplying $(p-1)$ by $(q-1)$ seems to be a very cute formula and it I would be surprise that its a coincidence because $(p-1)$ and $(q-1)$ also have clear interpretations. I am looking for a more intuitive clear reasoning, because it seems evident from the form of the formula that it should exist.

#### Solutions Collecting From Web of "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?"

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.

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.