$φ(n)=(p-1)(q-1)(r-1)$

Question

Let $p, q, r$ be three distinct primes. Show that $φ(n)=(p-1)(q-1)(r-1)$

So far I have:

There are $qr-1$ multiples of $p$ in $1,...,pqr$

There are $pr-1$ multiples of $q$ in $1,...,pqr$

There are $pq-1$ multiples of $r$ in $1,...,pqr$

We counted $pqr$ 3 times

$p$ & $q$ share $r-1$ multiples

$q$ & $r$ share $p-1$ multiples

$p$ & $r$ share $q-1$ multiples

Therefore, $φ(n)=pqr-(qr-1)-(pr-1)-(pq-1)+(r-1)+(p-1)+(q-1)-2$

Which does not simply down to $φ(n)=(p-1)(q-1)(r-1)$

What am I missing? Thanks for any help!

Answer 1

What you are missing is that it does simplify down to $(p-1)(q-1)(r-1)$:

\begin{align*} (p-1)(q-1)(r-1) &= pqr -qr-pr-pq+p+q+r-1\\ &=pqr-(qr-1)-(pr-1)-(pq-1) -3 \\ &\qquad +(p-1)+(q-1)+(r-1)+3 -1\\ &=pqr-(qr-1)-(pr-1)-(pq-1) \\ &\qquad+ (p-1)+(q-1)+(r-1) -1. \end{align*}

Answer 2

Alternate approach: For any prime $p$, we have $\phi(p)=p-1$.

Then use the fact that $\phi$ is multiplicative. That is, $\operatorname {gcd}(m,n)=1\implies \phi(mn)=\phi(m)\phi(n)$. (See the Chinese remainder theorem for a proof of this property.)

Answer 3

Your error seems to be that you count up to but not including $pqr$.

The multiples of $p$ are $p,2p, 3p,.....,(qr-2)p,(qr-1)p,$ AND $pqr$. So there are $qr$ multiples; not $qr -1$.

If we redo those numbers, inclusion-exclusion gives us $pqr - pq-qr-pr +p+q+r -1$ which is $(p-1)(q-1)(r-1)$.

If we omit $pqr$ and say there are $qr-1$ multiples of $p$ in $1,....,pqr-1$ then we would, by inclusion-exclusion have:

$(pqr-1) - (pq-1) -(pr-1)-(qr-1) + (p-1)+(q-1)+(r-1) - 0$ which is the same result.