EXERCICE 4 (5 points)

• 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.
  • 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.
• Partie B
  A 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:
• Etape 1: on choisit deux entiers naturels $p$ et $q$ compris entre 0 et 25.
• Etape 2: à la lettre que l'on veut coder, on associe l'entier $x$ correspond dans le tableau ci-dessus.
• Etape 3: on calcule l'entier $x'$ défini par les relations $$x' \equiv px + q \; \; \;[26] \;\; et \; 0\leqslant x' \leqslant 25.$$
• Etape 4: à l'entier $x'$, on associe la lettre correspondant 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.
    • 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.
    • c. Démontrer que $x' \equiv 9x + 2 \; \; \;[26]$ équivaut à $x \equiv 3x' + 20 \; \; \; [26]$.
    • d. Décoder la lettre R.
  • 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 admettre que $p$ est unique).
  • 3. Dans cette question, on choisit $p = 13$ et $q = 2$. Coder les lettres B et D. Que peut-on dire de ce codage?