phi(P*Q) = (P-1) * (Q-1) 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?
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 &lt; k &lt; 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 &lt; k &lt; 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 &lt; k &lt; pq$, all but $(p-1) + (q-1)$ are coprime to $pq$, and so $$\begin{aligned}\phi(pq) &amp;= (pq-1) - (p-1) - (q-1) \\ &amp;= pq - p - q + 1 \\ &amp;= (p-1)(q-1).\end{aligned}$$