Arithmétique – Bac S Amérique du Nord 2013 (spé)
Exercice 2 (spé) 5 points
Candidats ayant suivi l'enseignement de spécialité mathématiques
Partie A
On considère l'algorithme suivant :
| Variables : | $ a $ est un entier naturel |
| $ b $ est un entier naturel | |
| $ c $ est un entier naturel | |
| Initialisation : | Affecter à $ c $ la valeur $ 0 $ |
| Demander la valeur de $ a $ | |
| Demander la valeur de $ b $ | |
| Traitement : | Tant que $ a > b $ |
| $ \qquad $ Affecter à $ c $ la valeur $ c+1 $ | |
| $ \qquad $ Affecter à $ a $ la valeur $ a - b $ | |
| Fin de tant que | |
| Sortie : | Afficher $ c $ |
| Afficher $ a $ |
- Faire fonctionner cet algorithme avec $ a = 13 $ et $ b = 4 $ en indiquant les valeurs des variables à chaque étape.
- Que permet de calculer cet algorithme ?
Partie B
À chaque lettre de l'alphabet, on associe, grâce au tableau ci-dessous, un nombre entier compris entre $ 0 $ et $ 25 $.
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
On définit un procédé de codage de la façon suivante :
- Étape 1 : À la lettre que l'on veut coder, on associe le nombre $ m $ correspondant dans le tableau.
- Étape 2 : On calcule le reste de la division euclidienne de $ 9m+5 $ par $ 26 $ et on le note $ p $.
- Étape 3 : Au nombre $ p $, on associe la lettre correspondante dans le tableau.
- Coder la lettre U.
- Modifier l'algorithme de la partie A pour qu'à une valeur de $ m $ entrée par l'utilisateur, il affiche la valeur de $ p $, calculée à l'aide du procédé de codage précédent.
Partie C
- Trouver un nombre entier $ x $ tel que $ 9x \equiv 1 \left[26\right] $.
Démontrer alors l'équivalence :
$ 9m+5 \equiv p \left[26\right] \Leftrightarrow m\equiv 3p - 15 \left[26\right]. $- Décoder alors la lettre B
Corrigé
Partie A
Représentons les étapes de l'algorithme dans le tableau suivant :
$a$ $b$ $c$ $a > b$ 13 4 0 vrai 9 4 1 vrai 5 4 2 vrai 1 4 3 faux Fin : $a = 1$ ; $c = 3$
L'algorithme permet de calculer le quotient $c$ et le reste $a$ de la division euclidienne de la valeur de $a$ entrée initialement par $b$.
Au bout de $n$ étapes on a :
$ b c_n + a_n = a_0 $Dans l'exemple de la question 1 :
$ 4 \times 3 + 1 = 13 $
Partie B
Codage de la lettre U :
- Étape 1 : $ U \to m = 20 $
Étape 2 : $ 9m + 5 = 9 \times 20 + 5 = 185 $
La division euclidienne de 185 par 26 donne : $ 185 = 26 \times 7 + 3 $.
Le reste est $ p = 3 $.- Étape 3 : $ p = 3 \to D $
La lettre U est codée par la lettre D.
On peut modifier l'algorithme de la façon suivante :
Variables : $ a $ est un entier naturel $ b $ est un entier naturel $ c $ est un entier naturel $ m $ est un entier naturel Initialisation : Affecter à $ c $ la valeur $ 0 $ Affecter à $ b $ la valeur $ 26 $ Demander la valeur de $ m $ Affecter à $ a $ la valeur $ 9m + 5 $ Le reste de l'algorithme (traitement et sortie) reste identique à celui donné dans l'énoncé.
La valeur de $ p $ cherchée est la valeur de $ a $ affichée en fin d'algorithme.
Partie C
On a $ 3 \times 9 = 27 $ et $ 27 \equiv 1 \left[26\right] $.
On peut donc choisir $ x = 3 $.
En multipliant les deux membres de la congruence $ 9m + 5 \equiv p \left[26\right] $ par 3, on obtient :
$ 3(9m + 5) \equiv 3p \left[26\right] $$ 27m + 15 \equiv 3p \left[26\right] $Comme $ 27 \equiv 1 \left[26\right] $, on en déduit :
$ m + 15 \equiv 3p \left[26\right] $$ m \equiv 3p - 15 \left[26\right] $Décodage de la lettre B :
La lettre B correspond à $ p = 1 $.
En remplaçant $ p $ par 1 dans la congruence précédente :
$ m \equiv 3 \times 1 - 15 \left[26\right] $$ m \equiv -12 \left[26\right] $Comme $ -12 + 26 = 14 $, on a $ m \equiv 14 \left[26\right] $.
Le nombre $ m = 14 $ correspond à la lettre O.
La lettre B est décodée par la lettre O.
(Solution rédigée par Paki)