Exercice 8 — Des rationnels en couleur

Sujet

On rappelle qu'un nombre rationnel positif est le quotient d'un entier naturel par un entier naturel non nul. Pour tout rationnel \(x\), il existe un entier naturel \(a\) et un entier naturel \(b\) non nul tels que \(x=\frac{a}{b}\). Par exemple, \(x=\frac{12}{431}\) est un rationnel positif.
On admet qu'on peut attribuer sans ambiguïté une couleur, rouge ou vert, à chaque rationnel positif en suivant les règles suivantes :

• le rationnel 1 est vert ;
• pour tout rationnel \(x, x\) et \(x+1\) ne sont pas de la même couleur ;
• pour tout rationnel non nul \(x, x\) et \(\frac{1}{x}\) sont de la même couleur.

Par la suite, on notera \(x \sim y\) lorsque \(x\) et \(y\) sont de la même couleur et \(x \nsim y\) lorsque \(x\) et \(y\) ne sont pas de la même couleur. Par exemple, \(14 \nsim 15\) et \(14 \sim \frac{1}{14}\).

Comment annoncer la couleur

1. Déterminer la couleur de chacun des nombres suivants : \(2,0,17,2017, \frac{1}{2}, \frac{1}{18}, \frac{1}{2017}, \frac{5}{2}, \frac{13}{4}\).
2. Soit \(n\) un entier naturel non nul. Quelle est la couleur de \(n\) (et de \(\frac{1}{n}\) ) ?
3. Pour déterminer la couleur d'un rationnel \(\frac{a}{b}\), on utilise le premier algorithme ci-contre (les mentions Étape 1 et Étape \(\mathbf{2}\) sont des commentaires).
   a. a. Après une Étape \(\mathbf{1}\), est-on sûr que \(\frac{a}{b} \sim \frac{r}{b}\) ? \(\frac{a}{b} \nsim \frac{r}{b}\) ?
   b. Justifier que ce premier algorithme termine. c. En fin de boucle, la couleur de \(a\) est-elle la couleur de la fraction \(\frac{a}{b}\) du départ? Comment la reconstituer alors?

Premier algorithme

• \(r \leftarrow a\)
• Tant que \(b \neq 0\)
• Étape 1: calculer \(q\) et \(r\) entiers tels que \(a= b q+r\) et \(0 \leq r
• Étape 2 : Faire \(a \leftarrow b, b \leftarrow r\)

Algorithme modifié

• \(r \leftarrow a\); résultat \(\leftarrow 0\)
• Tant que \(b \neq 0\)
• Calculer \(q\) et \(r\) entiers tels que
  \(a=b q+r\) et \(0 \leq r
• résultat \(\leftarrow\) résultat \(+q\);
• Faire \(a \leftarrow b ; b \leftarrow r\);
• Étape finale...

1. a. En s'aidant du premier algorithme, donner la couleur du rationnel \(\frac{431}{12}\).
   b. Quelle est la couleur de \(\frac{403}{2017}\) ?
   c. Rédiger l'Étape finale de l'algorithme modifié de sorte qu'il renvoie la couleur de \(\frac{a}{b}\).