INFO TEST du mardi 29 mars 2016 TS spé maths
EXERCICE de bac 2016 en Nouvelle Calédonie
Candidats ayant suivi l’enseignement de spécialité 5 points
Les parties A et B peuvent être traitées de manière indépendante
Partie A
Afin de crypter un message, on utilise un chiffrement affine.
Chaque lettre de l’alphabet est associée à un nombre entier comme indiqué dans le tableau ci-dessous :
comme indiqué dans le tableau ci-dessous :
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
Soit x le nombre associé à la lettre à coder.
On détermine le reste y de la division euclidienne de 7x + 5 par 26,
puis on en déduit la lettre associée à y (c’est elle qui code la lettre d’origine).
1.Codons la lettre L.
La lettre L correspond à : x = 11
On a : 7 × 11 + 5 = 82 = 26 × 3 + 4 avec 0 ≤ 4 ≤ 26
Donc 82 a pour reste 4 dans la division par 26.
y = 4
Le nombre 4 correspond à E.
Conclusion: la lettre L est codée E.
2. a. Montrons que k ≡ 7x [26] ⇒ 15k ≡ x [26] pour tout entier relatif k
Soit k un entier relatif.
On a k ≡ 7x [26] ⇒ 15 k ≡ 15 × 7 x [26] en multipliant par 15
Or 15 × 7 = 105 = 4 × 26 + 1
Ainsi k ≡ 7 x [26] ⇒ 15 k ≡ 4 × 26 x + x [26]
c-à-d k ≡ 7x [26] ⇒ 15 k ≡ x [26]
Conclusion : k ≡ 7x [26] ⇒ 15k ≡ x [26] pour tout entier relatif k
b. Montrons la réciproque : pour tout k entier relatif
15 k ≡ x [26] ⇒ k ≡ 7 x [26]
Soit un k entier relatif quelconque
On a : 15 k ≡ x [26] ⇒ 7 × 15 k ≡ 7 x [26] en multipliant par 7
Mais on a vu que 7 × 15 = 4 × 26 + 1
Ainsi : 15k ≡ x [26] ⇒ 4 × 26 k + 1k ≡ 7 x [26]
c-à-d 15k ≡ x [26] ⇒ k ≡ 7 x [26]
Ainsi on a l'implication réciproque.
Conclusion: 15 k ≡ x [26] ⇔ k ≡ 7x [26] pour tout k entier relatif
c. Montrons que : y ≡ 7x + 5 [26] ⇔ x ≡ 15 y + 3 [26]
c-à-d montrons y − 5 ≡ 7 x [26] ⇔ x ≡ 15 ( y − 5 ) + 15 × 5 + 3 [26]
Ce qui revient à établir y − 5 ≡ 7 x [26] ⇔ x ≡ 15 ( y − 5 ) [26] notée ( 1 )
sachant 15 × 5 + 3 = 78 = 26 × 3
Or on a montré déjà que : k ≡ 7x [26] ⇔ 15 k ≡ x [26] pour tout entier relatif k
Donc aussi en particulier pour k = y − 5 on obtient l'équivalence souhaitée ( 1 )
Conclusion : L'équivalence est prouvée.
3. Décodons F.
Pour décoder une lettre:
On cherche à quel entier y entre 0 et 25 elle correspond
puis on détermine l'entier x entre 0 et 25 tel que : y ≡ 7x + 5 [26]
c-à-d tel que x ≡ 15 y + 3 [26].
La lettre F correspond à y = 5 .
On a : 15 y + 3 =15 × 5 + 3 = 78
78 = 26 × 3 + 0 et 0 ≤ 0 < 26
78 a pour reste 0 dans la division par 26.
Donc x = 0
L'entier 0 correspond à la lettre A .
Le décodage de la lettre F donne la lettre A.
Conclusion : Le décodage de la lettre F donne la lettre A.
Partie B
On considère les suites (an) et (bn) telles que a0 et b0 sont des entiers compris entre 0 et 25 inclus
et pour tout entier naturel n,
an+1 = 7an + 5 et bn+1 = 15 bn + 3
Montrons que pour tout entier naturel n : an = ( a0 + 5 / 6 ) × 7n − 5 / 6
On admet pour la suite du problème que pour tout entier naturel n
b n = ( b 0 + 3 / 14 ) × 15n − 3 / 14
Récurrence sur IN
• Pour n = 0
( a0 + 5 / 6 ) × 70 − 5 / 6 = a0 + 5 / 6 − 5 / 6 = a0
L'égalité est vérifiée pour n = 0
• Soit n dans IN quelconque.
Montrons que si l'égalité est vraie pour n alors elle est vraie pour n + 1.
Considérons : a n+ 1 = 7 an + 5
On a : a n = ( a 0 + 5 / 6 ) × 7n − 5 / 6
Donc a n+ 1 = 7 ( ( a 0 + 5 / 6 ) × 7n − 5 / 6 ) + 5
c-à-d a n+ 1 = ( a 0 + 5 / 6 ) × 7n + 1 − 7 × 5 / 6 + 5
mais − 7 × 5 / 6 + 5 = − 35 / 6 + 30 / 6 = − 5 / 6
Ainsi : a n + 1 = ( a 0 + 5 / 6 ) × 7n + 1 − 5 / 6
C'est l'égalité à l'ordre n + 1.
Conclusion : L'égalité est prouvée sur IN
Partie C
Déchiffrer un message codé avec un chiffrement affine ne pose pas de difficulté (on peut tester les 312
couples de coefficients possibles). Afin d’augmenter cette difficulté de décryptage, on propose d’utiliser
une clé qui indiquera pour chaque lettre le nombre de fois où on lui applique le chiffrement affine de la
partie A. Par exemple pour coder le mot MATH avec la clé 2-2-5-6, on applique « 2 » fois le chiffrement
affine à la lettre M (cela donne E), « 2 » fois le chiffrement à la lettre A, « 5 » fois le chiffrement à la lettre T
et enfin « 6 » fois le chiffrement à la lettre H. Dans cette partie, on utilisera la clé 2-2-5-6.
On veut décoder la lettre Q dans le mot IYYQ.
• Première méthode: On décode six fois de suite en remontant à la lettre de départ.
En effet lettre cherchée a été codée 6 fois de suite pour donner la lettre Q.
On repart chaque fois du x trouvé qui devient un y pour obtenir le nouvel x.
Lettre Entier y 15 y + 3 Reste x dans la division par 26 Lettre pour x
Q 16 243 = 26 × 9 + 9 0 ≤ 9 < 26 J
J 9 138 = 26 × 5 + 8 0 ≤ 8 < 26 I
I 8 123 = 26 × 4 + 19 0 ≤ 19 < 26 T
T 19 288 = 26 × 11 + 2 0 ≤ 2 < 26 C
C 2 33 = 26 × 1 + 7 0 ≤ 7 < 26 H
H 7 108 = 26 × 4 + 4 0 ≤ 4 < 26 E
x = 4 Conclusion: la lettre Q se décode en E.
• Deuxième méthode: On utilise la partie B.
Pour y on considère x ≡ 15 y + 3 [26] avec 0 ≤ x < 26
Donc on applique à y la fonction y → 15 y + 3
Puis à 15 y + 3 on applique cette même fonction six fois de suite
comme 15( 15 ( 15 ( 15 ( 15 ( 15 y + 3 ) + 3) + 3) + 3 ) + 3) + 3 avec y =16
Ensuite on doit prendre le reste dans la division par 26.
Or la suite ( b n ) déjà rencontrée est telle que:
b n+ 1 = 15 b n + 3 avec b0 entre 0 et 25
On décide de prendre : b 0 = 16
Alors b1 = 15 b 0 + 3
b2 = 15 b 1 + 3
..................
b6 = 15 b5 + 3
On considère alors le reste de la division de b6 par 26
pour avoir un entier entre 0 et 25. cet entier indiquera la lettre qui décode Q
Pour trouver b6 on utilise ce que l'on a admis:
b n = ( b 0 + 3 / 14 ) × 15n − 3 / 14 pour tout n dans IN
Ici on a pris b0 = 16
Pour n = 6 on a b6 = ( 16 + 3 / 14 ) × 156 − 3 / 14
c-à-d b6 = 184690848 = 26× 7103494 + 4 avec 0 ≤ 4 < 26
Le reste de la division de 184 690 848 par 26 est 4
4 correspond à E.
Conclusion : Q se décode en E.
--------------------------------------------------------------------------------------------