phi(P*Q) = (P-1) * (Q-1)

Question

I was trying to understand RSA when I encountered the Euler Function. I do understand this: $\phi(P)$, where $P$ is a prime is $P-1$.

However it seems that for a number $N$ such at $N=P\cdot Q$ where $P$ and $Q$ are non-equal primes:

\begin{equation} \phi(P\cdot Q) = (P-1)\cdot(Q-1) \end{equation}

I'm having trouble understanding why that is so. Could someone point me toward the proof of the same?

Answer 1

This is actually a special case of a more general property of the Euler totient function: it is a multiplicative function, meaning that, for any two coprime numbers $p$ and $q$, $\phi(pq) = \phi(p)\phi(q)$.

The special case where $p$ and $q$ are (distinct) primes is easy to prove. By definition, $\phi(n)$ gives the number of positive integers coprime to and smaller than $n$, i.e. the number of integers $k$ satisfying $0 < k < n$ and $\gcd(k,n) = 1$.

Since $p$ and $q$ are the prime factors of $pq$, an integer $k$ is coprime to $pq$ if and only if it isn't a multiple of either $p$ or $q$. In the range $0 < k < pq$ there are $p-1$ distinct multiples of $q$, and $q-1$ distinct multiples of $p$, and a bit of thought shows that these two sets cannot overlap, as any positive number that was a multiple of both $p$ and $q$ would have to be at least as large as $pq$.

Thus, out of the total $pq-1$ integers $k$ in the range $0 < k < pq$, all but $(p-1) + (q-1)$ are coprime to $pq$, and so $$\begin{aligned}\phi(pq) &= (pq-1) - (p-1) - (q-1) \\ &= pq - p - q + 1 \\ &= (p-1)(q-1).\end{aligned}$$

Answer 2

A very simple explanation is that a prime number is co-prime with every number below it:

$$ϕ(P) = (P−1)$$

Because Euler Totient Function is multiplicative function, this means that:

$$ϕ(pq)=ϕ(p)ϕ(q)$$

Which can be written as:

$$ϕ(n) = (p-1)(q-1)$$

I hope this helps. Otherwise, just look at Ilmari Karonens answer.