7,8,9 |
|  | Product Rule |  |

Let $K(x)$ be the number of irreducible fractions $a / b$ such that $a<x$ and $b<x$ (where $a$ and $b$ are natural numbers).

For example, $K(5 / 2)=3$ (fractions $1, 2, 1 / 2$).

Calculate the sum $K(100)+K\left(100 / 2\right)+K\left(100 / 3\right)+\ldots+K\left(100 / 99\right)+K\left(100 / 100\right)$.
The irreducible fraction $a / b$ is counted several times in our sum. Indeed, it is counted once in all $K\left({ }^{100} /\right)$ where $l a<100$ and $l b<100$. Thus, we obtain that the desired sum is equal to the number of all fractions $a / b$ (including reducible ones) or, equivalently, pairs $(a, b)$ that satisfy the condition $0<a<100,0<b<100$. There are a total of 992 such pairs. Therefore, $K(100)+K\left({ }^{100} / 2\right)+K\left({ }^{100} / 3\right)+\ldots+K\left({ }^{100} / 99\right)+K\left({ }^{100} / 100\right)=99^{2}=9801$.

## Answer

9801.

[ Connectivity and Decomposition into Connected Components ]

Problem