# 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. Commented Sep 21, 2011 at 23:55
• @UnreasonableSin Can you point out where it's proven?
– yydl
Commented Sep 21, 2011 at 23:57
• Right underneath "Computing Euler's function". But on second glance it's kind of a high level sketch of a proof. Commented Sep 21, 2011 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. Commented Sep 22, 2011 at 0:10
• You meant where $p$ and $q$ are distinct prime numbers. The formula is false if $p = q$.
– KCd
Commented Sep 22, 2011 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$ Commented Sep 22, 2011 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.