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?
 A: 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.
A: 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)$.
