0%

Problème 72

Énoncé:

Considérons la fraction $n/d$ où $n$ et $d$ sont des entiers positifs. Si $n < d$ et $PGCD(n, d) = 1$, alors c'est une fraction propre et irréductible.

Si on liste l'ensemble des fractions propres irréductibles pour $d \le 8$, en ordre de taille ascendant, on obtient:

$$1/8, 1/7, 1/6, 1/5, 1/4, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8$$

On peut voir qu'il y a $21$ éléments dans cette liste.

Combien d'éléments contiendrait l'ensemble de fractions propres irréductibles pour $d \le 1 \ 000 \ 000$ ?

Lien du problème originel