Prove that for distinct prime numbers $p$ and $q$, and natural numbers $m$ and $n$, $\phi(p^{m}q^{n}) = (p^{m} − p^{m−1})(q^{n} − q^{n−1})$. So we have to prove that for distinct prime numbers $p$ and $q$, and natural numbers $m$ and $n$, $$\phi(p^{m}q^{n}) = (p^{m} − p^{m−1})(q^{n} − q^{n−1})$$
I have already proved that for a prime, $p$, and a natural number $k$, $$\phi(p^k) = p^k −1−(p^{k−1}−1) = p^k − p^{k−1}$$ since there are $p^k − 1$ natural numbers less than $p^k$, and a natural number
is not relatively prime to $p^k$ if and only if it is a multiple of $p$. The natural numbers less than $p^k$ which are multiples of $p$ are the numbers of the form $p·m$ where $m$ is a natural number less than $p^{k−1}$. Since there are $p^{k−1}−1$ natural numbers less than $p^k−1$, there are $p^{k−1}−1$ multiples of p which are less than $p^k$.
How do I get to my final proof using this result?
 A: We need to find how many numbers in $A=\{1,2,\ldots,p^{m}q^{n}-1\}$ are coprime to $p^{m}q^{n}$. A number $k$ has a common factor with $p^{m}q^{n}$ if and only if it's divisible by $p$ or $q$. As you argued, the number of of naturals less than $p^{m}q^{n}$ multiple of $p$ are of the form $p\cdot m$, where $m\leq p^{m-1}q^{n}-1$. So we have $p^{m-1}q^{n}-1$ multiples of $p$. In a completely analogous fashion we find $p^{m}q^{n-1}-1$ multiples of $q$. But we counted the multiples of $pq$ twice, so we need to factor them out. The number of multiples of $pq$ would be of the form $pq\cdot m$, $m\leq p^{m-1}q^{n-1}-1$. So, the number of naturals divisible by $p$ or $q$ in $A$ is
$$
\left(p^{m-1}q^{n}-1 \right)+ \left( p^{m}q^{n-1}-1\right) - \left( p^{m-1}q^{n-1}-1\right)=p^{m}q^{n-1}+p^{m-1}(q^{n}-q^{n-1})-1.
$$
Then, we calculate
$$
\phi(p^{m}q^{n}) = (p^{m}q^{n}-1) - \left(p^{m}q^{n-1}+p^{m-1}(q^{n}-q^{n-1})-1 \right) = \\
=p^{m}(q^{n}-q^{n-1})-p^{m-1}(q^{n}-q^{n-1}) = (p^{m}-p^{m-1})(q^{n}-q^{n-1}).
$$
