1

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!

NoLand'sMan
  • 856
Sarah
  • 57
  • "We counted pqr 3 times" um, no you haven't counted $pqr$ any times yet. You said there are $qr-1$ multiples of $p$. That only takes you to $pqr-p$. – fleablood Sep 26 '19 at 01:53
  • And $p,q$ share $r$, not $r-1$ multiples. So you should have $pqr -pq-pr-pq +p+q+r - 1$. Purposely omit the $pqr$ term then you never count $pqr$ and you answer is $(pqr-1)-(pq-1)-(pr-1)-(qr-1) +(p-1)+(q-1)+(r-1) - 0$ – fleablood Sep 26 '19 at 01:59

3 Answers3

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*}

kccu
  • 20,808
  • 1
  • 22
  • 41
  • I'm sorry, that -1 should be a -2 right? Since we counted pqr 3 times we need to subtract 2 of those? – Sarah Sep 26 '19 at 00:52
  • No, it should be $-1$. You counted $pqr$ $3$ times when counting multiples of $p$, $q$, and $r$. But you also counted it $3$ times when counting multiples of $pq$, $pr$, and $qr$. Since you subtracted those latter counts, now we have counted $pqr$ a net number of $0$ times. So we need to add it back in, hence a $+1$. Finally, since we counted numbers $\leq pqr$ that are not relatively prime to $pqr$, all of this gets subtracted from $pqr$, hence $-1$. See the principle of inclusion-exclusion. – kccu Sep 26 '19 at 00:58
  • So I changed it so that there are $qr$ multiples of $p$ in $pqr$ and so on and that $p$ & $q$ share $r$ multiples and so on. Does this have the same argument to subtract 1 at the end for pqr? – Sarah Sep 26 '19 at 01:10
  • Nevermind, I just take one out to count $pqr$ I was looking at it the wrong way. Thanks for the help! – Sarah Sep 26 '19 at 01:12
0

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

  • 2
    I'm assuming that as they are even giving this as a question, that $\phi$ hasn't yet been proven to be multiplicative. I'd assume that that the entire point of the exercise is to prove it is multiplicative. – fleablood Sep 26 '19 at 01:49
  • You could be right. But as I recall it is essentially equivalent to CRT, which they might be able to just use. It does make the problem very simple. Let's see what the OP says. @fleablood –  Sep 26 '19 at 02:16
0

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.

fleablood
  • 124,253