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?


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!

  • $\begingroup$ Please consider reading my answer and give your comment. $\endgroup$ – 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.