Amérique du Nord, mai 2013, exercice de spécialité

Énoncé

5 points
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
Affecter à c la valeur c+1
Affecter à a la valeur a - b
Fin de tant que
Sortie :
Afficher c
Afficher a
1. Faites fonctionner cet algorithme avec a = 13 et b = 4 en indiquant les valeurs des variables à chaque étape.
Il vous suffit de suivre pas à pas l'algorithme et d'inscrire les résultats au fur et à mesure dans un tableau.
2. Que permet de calculer cet algorithme ?
En faisant fonctionner l'algorithme pas à pas, vous ferez apparaître la division euclidienne.
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.
1. Codez la lettre U.
En utilisant le tableau de l'énoncé, voyez quel est le nombre associé à U puis déduisez un nombre p puis la lettre correspondante.
2. Modifiez 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

1. Trouvez un nombre entier x tel que 9x \equiv 1\ [26].
Si vous ne voyez pas rapidement une solution x, révisez votre table de 3.
2. Démontrez alors l'équivalence :
9m + 5 = p\ [26] \Longleftrightarrow m = 3p - 15\ [26].
Pensez à multiplier par 3 pour faire apparaître le 15 et le 3 puis utiliser le x précédent
3. Décodez alors la lettre B.
Faites le même raisonnement que dans la partie B 1. mais à l'envers et en utilisant la question précédente.

Corrigé

Partie A
1. 
Variables :
a
b
c
a \geq b ?
Initialisation :
13
4
0
oui
Premier passage :
9
4
1
oui
Deuxième passage :
5
4
2
oui
Troisième passage :
1
4
3
Non : a < b
Fin du « Tant que » et affichage :
a = 1

c = 3


2. Cet algorithme calcule le reste et le quotient de la division euclidienne de a par b.
Partie B
1. La lettre U est associée au nombre m = 20.
Or, 9 \times 20 + 5 = 185 et 185\equiv 3\quad [26], soit p = 3 qui correspond à D. La lettre U est donc codée par D.
2 
Variables :
a est un entier naturel

c est un entier naturel
Initialisation :
Affecter à c la valeur 0

Demander la valeur de a

Affecter à a la valeur 9 \times a+5
Traitement :
Tant que a > 26

Affecter à c la valeur c +1

Affecter à a la valeur a-26

Fin de tant que
Sortie :
Afficher a

Partie C
1. 9\times 3=27 \equiv 1\ [26]. Donc x = 3 convient.
2. Puisque 9\times 3\equiv 1\ [26] :
9m + 5 \equiv p\ [26] \iff 27m+15\equiv 3p \ \iff m \equiv 3p - 15\ [26].
3. La lettre B est associée à 1.
On prend donc p = 1, d'après la question précédente m\equiv 3 \times 1 - 15 \quad[26], soit m \equiv 14\quad [26].
14 correspond à la lettre O. La lettre B correspond au codage de la lettre O.