# Why does $\phi(pq)=\phi(p)\phi(q)$?

In an RSA paper I am reading it is assumed that where $p$ and $q$ are distinct prime numbers:

$\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$

I would love to know why/how this is so? Is there some way to prove this?

-
The totient function is a multiplicative function. The wikipedia page has a proof. –  Unreasonable Sin Sep 21 '11 at 23:55
@UnreasonableSin Can you point out where it's proven? –  yydl Sep 21 '11 at 23:57
Right underneath "Computing Euler's function". But on second glance it's kind of a high level sketch of a proof. –  Unreasonable Sin Sep 21 '11 at 23:59
Huh. I hadn't realized we already had the specialized tag for the totient, so I thought to remove it. Oh well. –  Ｊ. Ｍ. Sep 22 '11 at 0:10
You meant where $p$ and $q$ are distinct prime numbers. The formula is false if $p = q$. –  KCd Sep 22 '11 at 0:38

The positive integers less than $pq$ that are not relatively prime to $pq$ are the positive multiples of $p$ less than $pq$ and the positive multiples of $q$ less than $pq$. The positive multiples of $p$ less than $pq$ are the numbers $kp$ for $k=1,2,\dots,q-1$, so there are $q-1$ of them. Similarly, the positive multiples of $q$ less than $pq$ are the numbers $kq$ for $k=1,2,\dots,p-1$, so there are $p-1$ of them. Thus, there are altogether $(p-1)+(q-1) = p+q-2$ positive integers less than $pq$ that are not relatively prime to $pq$.
There are altogether $pq-1$ positive integers less than $pq$, so there must be $$(pq-1)-(p+q-2) = pq-p-q+1 = (p-1)(q-1)$$ positive integers less than $pq$ that are relatively prime to $pq$. Thus, $\varphi(pq) = (p-1)(q-1) =$ $\varphi(p)\varphi(q)$.
Crucial is that the two sets of multiples are disjoint, since $\rm\ p\:\mathbb Z\cap q\:\mathbb Z\ =\ p\:q\:\: \mathbb Z\$ by $\rm\:(p,q)=1\:.\quad$ –  Bill Dubuque Sep 22 '11 at 0:50
What you are asking about is a special case of the multiplicativity of the totient function $\varphi$. In general, a function $f: \mathbb{Z}^+ \rightarrow \mathbb{R}$ is multiplicative if for all $n_1$ and $n_2$ with $\operatorname{gcd}(n_1,n_2) = 1$, $f(n_1 n_2) = f(n_1) f(n_2)$. (One might not have expected the definition to include the restriction that $n_1$ and $n_2$ have no common factor: functions which satisfy $f(n_1 n_2) = f(n_1) f(n_2)$ for all $n_1,n_2 \in \mathbb{Z}^+$ are called completely multiplicative. But this latter property is somehow too strong: many of the most common "arithmetical functions" studied in elementary / analytic number theory are multiplicative, but very few are completely multiplicative. For instance $\varphi$ is not completely multiplicative: for any prime number $p$, $\varphi(p^2) = p^2 -p = p(p-1) \neq (p-1)^2 = \varphi(p) \varphi(p)$.)
An elementary proof (well, I have never seen any other kind...) of the multiplicativity of $\varphi$ using the Chinese Remainder Theorem can be found in $\S 2.4$ of these notes. Knowing that $\varphi$ is multiplicative leads to an explicit formula for $\varphi(n)$ in terms of the prime factorization of $n$, since for any prime power $p^a$, the numbers between $1$ and $p^a$ which are relatively prime to $p^a$ are precisely the ones which are not multiples of $p$, so $\varphi(p^a) = p^a - p^{a-1} = p^{a-1}(p-1)$. For a second (still elementary!) proof of the multiplicativity of $\varphi$, see $\S 2.1$ of these notes. This latter proof uses the Möbius Inversion Formula.