200. Let $t$ be an arbitrary positive number; the number of irreducible fractions $\frac{p}{q}$, where the numerator $p$ and the denominator $q$ do not exceed $t$, is denoted by $d(t)$,

## What is the sum

$-S=d\left(\frac{100}{1}\right)+d\left(\frac{100}{2}\right)+d\left(\frac{100}{3}\right)+\ldots+d\left(\frac{100}{99}\right)+d\left(\frac{100}{100}\right) ?$
200. To each irreducible fraction $\frac{p}{q}$, where

$$
0<p \leqslant 100, \quad 0<q \leqslant 100
$$

we associate a point $M$ with coordinates $p$, $q$; the inequalities ( ${ }^{*}$ ) indicate that the point $M$ is located inside the shaded square $\mathscr{K}=O A C B$ bounded by the coordinate axes and the lines $x=100$ and $y=100$ (or, in the extreme case, $M$ belongs to the side $A C$ or the side $B C$ of the square $\mathscr{K}$ ), and the irreducibility of the fraction $\frac{p}{q}$ means that there are no other "integer" points (points with integer coordinates) on the segment $O M$ (indeed, the equalities $p=k p_{1}, q_{1}=k q_{1}$, indicating that the fraction $\frac{p}{q}$ can be reduced by $k$, mean that the segment $O M$ also contains the integer point $M_{1}\left(p_{1} q_{1}\right)$). In this case, if the segment $O P$ cut out by the square $\mathscr{K}$ on a line $l$ passing through $O$ contains $n$ integer points ( $p_{0}, q_{0}$ ), $\left(2 p_{0}, 2 q_{0}\right),\left(3 p_{0}, 3 q_{0}\right), \ldots,\left(n p_{0}, n q_{0}\right)$ (where $M_{0}\left(p_{0}, q_{0}\right)$ is the closest to $O$ of these points), then (since $n p_{0} \leqslant 100, n q_{0} \leqslant 100$ ) we have $p_{0} \leqslant \frac{100}{n}$ $\left(<\frac{100}{n-1}<\frac{100}{n-2}<\ldots<\frac{100}{1}\right)$ and $q_{0} \leqslant \frac{100}{n}\left(<\frac{100}{n-1}<\frac{100}{n-2}<\ldots<\frac{100}{1}\right)$ and, thus, the irreducible fraction $\frac{p_{0}}{q_{0}}$ is counted in the terms $d\left(\frac{100}{1}\right)$,

![](https://cdn.mathpix.com/cropped/2024_05_21_b937612abb2773f7abffg-230.jpg?height=476&width=505&top_left_y=572&top_left_x=324)

Fig. 24.

$d\left(\frac{100}{2}\right), \ldots, d\left(\frac{100}{n}\right)$ of the sum $S$, i.e., it is counted $n$ times in this sum (while the reducible fractions $\frac{2 p_{0}}{2 q_{0}}, \frac{3 p_{0}}{3 q_{0}}, \ldots, \frac{n p_{0}}{n q_{0}}$ are, of course, not counted in the sum $S$ at all). Thus, the contribution of the fraction $\frac{p_{0}}{q_{0}}$ to the sum $S$ is $n$, i.e., it is equal to the number of integer points on the segment $O P$.

From what has been proven, it follows that the total number of fractions counted in the sum $S$ - i.e., the numerical value of the sum $S$ - is equal to the total number of integer points in the square $\mathscr{K}$, i.e., $S=100 \cdot 100=10000$.