Exercice

Les parties A et B peuvent être traitées de façon indépendante.

Partie A

Pour deux entiers naturels non nuls a et b, on note r (a, b) le reste dans la division euclidienne de a par b.

On considère l’algorithme suivant :

1 Faire fonctionner cet algorithme avec a = 26 et b = 9 en indiquant les valeurs de a, b et c à chaque étape. 0,5 pt

2 Cet algorithme donne en sortie le PGCD des entiers naturels non nuls a et b.

Le modifier pour qu’il indique si deux entiers naturels non nuls a et b sont premiers entre eux ou non. 0,5 pt

Partie B

À chaque lettre de l’alphabet, on associe grâce au tableau ci-dessous un nombre entier compris entre 0 et 25.

On définit un procédé de codage de la façon suivante :

Étape 1 : on choisit deux entiers naturels p et q compris entre 0 et 25.

Étape 2 : à la lettre que l’on veut coder, on associe l’entier x correspondant dans le tableau ci-dessus.

Étape 3 : on calcule l’entier x′ défini par les relations :

x′ ≡ px + q [26] et 0 ≤ x′ ≤ 25.

Étape 4 : à l’entier x′, on associe la lettre correspondante dans le tableau.

1 Dans cette question, on choisit p = 9 et q = 2.

a. Démontrer que la lettre V est codée par la lettre J. 0,5 pt

b. Citer le théorème qui permet d’affirmer l’existence de deux entiers relatifs u et v tels que 9u + 26v = 1. Donner sans justifier un couple (u, v) qui convient. 0,75 pt

c. Démontrer que x′ ≡ 9x + 2 [26] équivaut à x ≡ 3x′ + 20 [26]. 0,75 pt

d. Décoder la lettre R. 0,5 pt

2 Dans cette question, on choisit q = 2 et p est inconnu. On sait que J est codé par D. Déterminer la valeur de p (on admettra que p est unique). 0,75 pt

3 Dans cette question, on choisit p = 13 et q = 2. Coder les lettres B et D. Que peut-on dire de ce codage ? 0,75 pt