Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime? I had my own proof for it but I really don't like it (it feels not intuitive at all because it requires factoring!) and I feel there must be a more direct way to do it by a different counting argument.
If anyone has one it would be greatly appreciated!
My "proof":
Recall:
$\phi(N) = $ the number of elements that are relatively prime to $n$ (i.e. have a mod inverse)
$N = pq$ where $p$ and $q$ are prime.
Let's count the number of elements between $1$ and $N-1$ that are NOT relatively prime to $p$ and $1$. Those elements must have at least $p$ or $q$ as one of its factors. So let include all number that have $p$ as a factor and $q$ as a factor and are in the given range. Thus:
$$0p, 1p, 2p, ..., kp, ..., p(q-1)$$
and
$$0q,1q,2q,...,jp,...,q(p-1)$$
That gives a count of: $$N - p - q + 1 = pq - p - q + 1 = (p -1)(q-1)$$
QED as required.
The reason I am not happy with this argument is that it seems to me there should be a clear intuitive way of doing it without having to factor or substitute the definition of N. This seems clear because multiplying $(p-1)$ by $(q-1)$ seems to be a very cute formula and it I would be surprise that its a coincidence because $(p-1)$ and $(q-1)$ also have clear interpretations.
Here is a grid representing all integers mod $pq$.
$$\begin{array}{ccccc} 0&q&2q&\cdots&(p-1)q\\ p&p+q&p+2q&\cdots&p+(p-1)q\\ 2p&2p+q&2p+2q&\cdots&2p+(p-1)q\\ \vdots&\vdots&\\ (q-1)p&(q-1)p+q&(q-1)p+2q&\cdots&(q-1)p+(p-1)q\\ \end{array}$$
You can confirm that there is no double representation here by considering what $mp+nq\equiv\hat{m}p+\hat{n}q$ would imply.
Now note that the top row and left column are precisely the numbers in the table that are not relativelty prime to $pq$. The rest is a $(p-1)\times(q-1)$ rectangle, consisting of the values that are relatively prime to $pq$.