Exercise 4.2.11 (Number of positive irreducible fractions $x =a/d\leq 1$ with denominator $d \leq n$)

Proof. If $d$ is a positiver integer, let $A_d$ denote the set of positive irreducible fractions $x=a∕d$ with denominator $d$ such that $x\le 1$, and let $A$ be the set of positive irreducible fractions $x=a∕d$ where $x\le 1$ and $1\le d\le n$.

Then

thus

Let $d$ be any fixed positive integer. The map

is a bijection:

• If $a∕d=b∕d$, then $a=b$, so $\phi$ is injective.
• By definition of $A_d$, every $x\in A_d$ is of the form $x=a∕d$, where $a\wedge d=1$ and $1\le a\le d$, thus $x=\phi (a)$, so $\phi$ is surjective.

This shows that

Then the equality (1) gives

The number of positive irreducible fractions $x=a∕d\le 1$ with denominator $d\le n$ is $\varphi (1)+\varphi (2)+\varphi (3)+\cdots +\varphi (n)$. □