TEST d'arithmétique TS spé. math. 31 janvier 2017
EXERCICE 1
Un jeu classique consiste à coder des messages.
Pour cela, on utilise la correspondance entre les lettres de l'alphabet et
un nombre entier compris entre 0 et 25.
Le tableau ci-dessous donne cette corespondance:
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Le codage ( affine ) consiste à choisir une clé ( a ; b ) formée de deux nombres
entiers a et b compris entre 0 et 25 et à remplacer une lettre par une
autre selon le principe suivant:
- On lit sur le tableau le nombre x correspondant à la lettre.
- On calcule le reste r de la division de a x + b par 26.
( c-à-d r ≡ a x + b [ 26 ] avec 0 ≤ r < 26 )
- On lit sur le tableau la lettre correspondant au nombre r .
qui est donc la lettre codée.
Par exemple: avec la clé ( a ; b ) = ( 7 ; 12 ), pour coder la lettre T,
on calcule 7 × 19 + 12 = 145 , puis le reste de la division
euclidienne de 145 par 26, soit 15. La lettre codée est ainsi P.
1. Coder les lettres A,K,W avec la clé ( 5 ; 17 ).
REPONSE:
On trouve:
| Lettre à coder | A | K | W |
| x = | 0 | 10 | 22 |
| 5 x + 17 = | 17 | 67 | 127 |
| 5 x + 17 = | 0 × 26 + 17 | 2 × 26 + 15 | 4 × 26 + 23 |
| r = | 17 | 15 | 23 |
| Lettre codée | R | P | X |
Conclusion: A est codée R
K est codée P
W est codée X
2. Que se passe-t-il si l'on prend a = 0 et b = 17 ?
REPONSE:
On a :
a x + b = b = 17 avec 0 ≤ 17 < 26
Alors r = 17 pour tout entier x entre 0 et 25.
Toutes les lettres sont codées par la lettre R.
Ce qui rend le codage sans intérêt.
3. On considère un entier x compris entre 0 et 25.
a. Donner, sans justification, les restes obtenus dans la division euclidienne
de 13 x + 6 par 26 pour x compris entre 0 et 25.
REPONSE:
Avec la calcuatrice TI 84 plus:
Y=
\ Y1 = 13*X+6 X est mis avec la touche X,T,θ,n
\ Y2 = Y1 − 26*int( Y1 / 26 )
Pour avoir Y1 faire VARS puis ► puis ENTER ENTER
On obtient avec 2ND GRAPH
| X | Y1 | Y2 |
| 0 | 6 | 6 |
| 1 | 19 | 19 |
| 2 | 32 | 6 |
| 3 | 45 | 19 |
| .... | ..... | .... |
Conclusion:
Les restes sont alternativement 6 et 19, le premier étant 6.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 |
b. Coder le mot PREMIER avec la clé ( 13 ; 6 ).
Commenter le résultat obtenu.
REPONSE:
r = 6 correspond à G et r = 19 correspond à T
Le mot PREMIER sera codé uniquement avec les lettres G et T.
Utilisons le tableau :
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 | 6 | 19 |
| G | T | G | T | G | T | G | T | G | T | G | T | G | T | G | T | G | T | G | T | G | T | G | T | G | T |
Conclusion: PREMIER est codé
TTGGGGT
La clé choisie ( 13 ; 6 ) pour ce codage ( affine ) n'est pas intéressante puisque
pour deux lettres distinctes on peut retrouver la même lettre dans le codage.
4. Un codage est dit acceptable lorsque deux lettres distinctes quelconques
sont toujours codées différemment .
On admet que les clés ( a , b ) donnant un codage acceptable sont celles
pour lesquelles a est un entier premier avec 26, quelque soit
l'entier b compris entre 0 et 25.
a.Donner la liste des nombres entiers compris entre 0 et 25 et premiers avec 26.
26 = 2 × 13
Un entier premier avec 26 ne doit donc pas être pair ni divisible par 13.
Nous devons considérer les entiers entre 0 et 25 qui sont impairs et autre que 13.
Conclusion: La liste comporte les douze entiers suivants:
1 3 5 7 9 11 15 17 19 21 23 25
b. Déterminer le nombre de clés donnant un codage acceptable.
Pour a il y a 12 possibilités d'après les conditions "d'acceptabilité".
Pour chaque a, il y a 26 possibilités pour b.
D'après le principe multiplicatif le nombre de clés acceptabiles est :
12 × 26 = 312
Conclusion: Il y a 312 clés ( a ,; b ) acceptables
5. Le mot ABSURDE a été codé à l'aide d'une clé ( a , b ) selon le principe décrit ci-dessus et
décrit ci-dessus et l'on a obtenu VOZLGAT.
Déterminer cette clé.
REPONSE:
Notons ( a ; b ) la clé recherchée.
Utilisons le fait que A est codée V et que B est codée O.
| Lettre | A | B |
| x | 0 | 1 |
| Lettre codée | V | O |
| r | 21 | 14 |
| a x + b | b | a + b |
• On a: b ≡ 21 [ 26 ] avec 0 ≤ b < 26
Donc on a déjà: b = 21
• On a: a + b ≡ 14 [ 26 ] avec et a dans la liste déjà indiquée.
c-à-d a + 21 ≡ 14 [ 26 ]
c-à-d a ≡ 14 − 21 [ 26 ]
c-à-d a ≡ − 7 [ 26 ]
c-à-d a ≡ 26 − 7 [ 26 ]
c-à-d a ≡ 19 [ 26 ] 19 est " acceptable" car il est dans la liste rencontrée.
Conclusion : La clé est ( 19 ; 21 )
------------------------------------------------------------