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

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?

## 2 Answers

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!

• Please consider reading my answer and give your comment. – Maged Saeed Dec 18 '18 at 19:45

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?