Annale corrigée Exercice Ancien programme

Codons et décodons

Polynésie française • Juin 2017

Exercice 4 • 5 points • 1 h

Codons et décodons

Les thèmes clés

Arithmétique

 

Les parties A et B sont indépendantes.

Une personne a mis au point le procédé de cryptage suivant.

À chaque lettre de l'alphabet, on associe un entier n comme indiqué ci-dessous :

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 choisit deux entiers a et b compris entre 0 et 25.

Tout nombre entier n compris entre 0 et 25 est codé par le reste de la division euclidienne de an + b par 26.

Le tableau suivant donne les fréquences f en pourcentage des lettres utilisées dans un texte écrit en français.

Lettre

A

B

C

D

E

F

G

H

I

J

K

L

M

f

9,42

1,02

2,64

3,38

15,87

0,94

1,04

0,77

8,41

0,89

0,00

5,33

3,23

Lettre

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

f

7,14

5,13

2,86

1,06

6,46

7,90

7,26

6,24

2,15

0,00

0,30

0,24

0,32

partie a

Un texte écrit en français et suffisamment long a été codé selon ce procédé. L'analyse fréquentielle du texte codé a montré qu'il contient 15,9 % de O et 9,4 % de E.

On souhaite déterminer les nombres a et b qui ont permis le codage.

1. Quelles lettres ont été codées par les lettres O et E ?

2. Montrer que les entiers a et b sont solutions du système :

{4a+b14 [26]b4 [26].

3. Déterminer tous les couples entiers (a, b) ayant pu permettre le codage de ce texte.

partie b

1. On choisit a = 22 et b = 4.

a) Coder les lettres K et X.

b) Ce codage est-il envisageable ?

2. On choisit a = 9 et b = 4.

a) Montrer que pour tous entiers naturels n et m, on a :

m9n+4 [26]n3m+14 [26].

b) Décoder le mot AQ.

Les clés du sujet

Partie A

2. Suivez le procédé de cryptage donné dans l'énoncé à partir des lettres codées respectivement en O et en E (question 1.).

3. Résolvez le système d'équations de la question 2.

Partie B

1. a) Suivez encore une fois le procédé de cryptage, mais cette fois-ci pour les lettres K et X.

2. b) Utilisez la question 2. a) en remarquant que l'entier n est l'entier associé à la lettre à coder et que l'entier m est l'entier associé à la lettre codée.

Corrigé

partie a

1. Extraire des informations d'un tableau

Dans le texte codé, on a constaté 15,9 % de lettres O. La fréquence la plus proche dans le tableau donnant les fréquences en pourcentage des lettres utilisées dans un texte écrit en français (non codé) est 15,87 %. Cette fréquence correspond à la lettre E.

Ainsi, la lettre E a été codée par la lettre O.

Similairement, dans le texte codé, on a constaté 9,4 % de lettres E. La fréquence la plus proche dans le tableau évoqué précédemment est 9,42 % correspondant à la lettre A.

Ainsi, la lettre A a été codée par la lettre E.

2. Justifier un système d'équations

En suivant le procédé de cryptage, on associe à la lettre E l'entier 4. Ensuite, on effectue la division euclidienne de a × 4 + b, soit 4a + b par 26. Par cette division euclidienne, il existe un unique couple d'entiers naturels (q  r) tel que 4a + b = 26 × q + r où 0 r 25. Or, d'après la question précédente, la lettre E est codée par la lettre O qui est associée à l'entier naturel 14 (d'après le tableau de l'énoncé), ainsi r = 14. On a alors 4a + b = 26 × q + 14 ce qui s'écrit aussi 4a + b  14 [26].

Similairement, on associe à la lettre A l'entier 0. D'après la question précédente, cette lettre est codée par la lettre E associée à l'entier 4. Il existe alors un entier naturel q tel que a × 0 + b = 26 × q + 4. Ainsi, on a b = 26 × q + 4 ce qui s'écrit aussi b  4 [26].

Les entiers a et b sont donc solutions du système {4a+b14[26]b4[26].

3. Déterminer toutes les solutions d'un système d'équations

Résolvons le système suivant : {4a+b14[26]b4[26].

b  4 [26] signifie qu'il existe un entier k tel que b = 4 + 26k. Or, l'entier b doit être compris entre 0 et 25 et 0b2504+26k25426k21213k2126.

Il existe un unique entier k qui vérifie 213k2126 : k = 0. On en conclut que : b = 4 + 26 × 0 = 4.

D'après le point précédent, on a 4a + b  14 [26] 4a + 4  14 [26] 4a  10 [26].

Le reste de la division euclidienne de 4a par 26 doit ainsi être égal à 10. Calculons ce reste pour tout entier naturel a compris entre 0 et 25 (contrainte donnée dans l'énoncé) :

a

0

1

2

3

4

5

6

7

8

9

10

11

12

4a

0

4

8

12

16

20

24

28

32

36

40

44

48

Reste

0

4

8

12

16

20

24

2

6

10

14

18

22

a

13

14

15

16

17

18

19

20

21

22

23

24

25

4a

52

56

60

64

68

72

76

80

84

88

92

96

100

Reste

0

4

8

12

16

20

24

2

6

10

14

18

22

L'entier a pourrait donc prendre les valeurs 9 et 22.

rassurez-vous !

Ces résultats ne sont pas surprenants : lisez les énoncés des questions 1 et 2 de la partie B.

Les couples d'entiers (a, b) ayant pu permettre le codage de ce texte sont (9, 4) et (22, 4).

partie b

1. a) Suivre une procédure

En suivant le procédé de cryptage, on associe à la lettre K l'entier 10. Ensuite, on effectue la division euclidienne de 22 × 10 + 4 = 224 par 26. Par cette division euclidienne, on a : 224 = 26 × 8 + 16. Le reste de cette division étant 16, la lettre K est codée par la lettre Q.

De même, en suivant le procédé de cryptage, on associe à la lettre X l'entier 23. Ensuite, on effectue la division euclidienne de 22 × 23 + 4 = 510 par 26. Par cette division euclidienne, on a : 510 = 26 × 19 + 16. Le reste de cette division étant 16, la lettre X est codée par la lettre Q.

b) Argumenter

D'après la question précédente, la lettre Q code à la fois les lettres K et X. Ces lettres une fois codées devenant indiscernables, un tel codage n'est pas envisageable.

2. a) Justifier une équivalence

On a pour tous entiers naturels n et m :

retenez bien !

Soient a, b et k des entiers relatifs. Si ab[26] alors kakb[26].

notez bien !

271[26] et 1214[26].

m9n+4[26]3×m3×9n+3×4[26]3m27n+12[26]3mn+12[26]3m12n[26]3m+14n[26]n3m+14[26]

Réciproquement, pour tous entiers naturels n et m :

n3m+14[26]9×n9×3m+9×14[26]9n27m+126[26]9nm+126[26]9n126m[26]9n+4m[26]m9n+4[26]

Ainsi, pour tous entiers naturels n et m, m9n+4[26]n3m+14[26].

b) Prendre une initiative et argumenter

La lettre A est associée à l'entier 0 (m=0). D'après la question 2. a) de la partie B, on a :

09n+4[26]n3×0+14[26]n14[26].

L'entier n étant compris entre 0 et 25, on en déduit que n = 14 qui est associé d'après le tableau à la lettre O.

La lettre Q est associée à l'entier 16 (m=16). D'après la question 2. a) de la partie B, on a :

169n+4[26]n3×16+14[26]n62[26].

notez bien !

62 = 2 × 26 + 10 donc 6210[26].

L'entier n étant compris entre 0 et 25, on en déduit que n = 10 qui est associé d'après le tableau à la lettre K.

Le mot AQ est décodé en le mot OK.

Accéder à tous les contenus
dès 6,79€/mois

  • Les dernières annales corrigées et expliquées
  • Des fiches de cours et cours vidéo/audio
  • Des conseils et méthodes pour réussir ses examens
  • Pas de publicités
S'abonner