Proof that $\sum_{d\mid n}\phi(d)=n$

Question

I am trying to understand a particular proof of the fact that $\sum_{d|n}\phi(d)=n$. I've seen different proofs of this statement, but I'm having trouble understanding the following one, given in "A Classical Introduction to Modern Number Theory". It goes as follows

"Consider the n rational numbers $1/n,2/n,...,n/n$. Reduce each to lowest terms; i.e, express each number as a quotient of relatively prime integers. The denominators will all be divisors of n. If d|n, exactly $\phi(d)$ of our numbers will have $d$ in the denominator after reducing to lowest terms"

In particular, I'm having trouble seeing why exactly $\phi(d)$ of the numbers will have d in the denominator. What am I missing?

Answer 1

This is a good step to understand thoroughly, so let's work through it in detail.

What has to be true about the numerator $a$ so that $a/n$ will have denominator $d$ in lowest terms—that is, so that $a/n = b/d$ with $\gcd(b,d)=1$?

• First of all, $a$ needs to be a multiple of $n/d$. You can either intuit this property from working on small examples (like $n=12$), or else note that $a/n = b/d$ means that $a=b(n/d)$. That means that $a=b(n/d)$ for some $b$ in the range $\{1, \dots, n/\frac nd\} = \{1, \dots d\}$ (since $1\le a\le n$ to begin with).
• Then, this number $b$ has to be relatively prime to $d$, by definition.

So we simply have to count how many integers in the range $\{1,\dots,d\}$ are relatively prime to $d$ ... and that's exactly what $\phi(d)$ measures!

Answer 2

I tried to understand the argument and @Greg Martin answer was really helpful. However, I feel that it will be better if his answer includes the following as details:

after writing the numbers:

$\frac{1}{n}, \cdots \frac{b_i}{d_j}, \cdots, (\frac{n}{n} = 1)$ where $d_j$ is obviously a divisor of $n$. Now, since every fraction $\frac{b_1}{d_1}$ is irreducable i.e. with $\gcd(b_i,d_j) = 1$, how many numbers of the form $\frac{b_i}{d_j}$ are there? In other words, how many numbers $b_i$ that are relatively prime to $d_j$ exist?