EXERCICE 4 (5 points)
Partie A
On considère l'équation $(E) : 25x - 108y = 1$ où $x$ et $y$ sont des entiers relatifs.
- Vérifier que le couple $(13,3)$ est solution de cette équation.
- Déterminer l'ensemble des couples d'entiers relatifs solutions de l'équation $(E)$.
Partie B
Dans cette partie, $a$ désigne un entier naturel et les nombres $c$ et $g$ sont des entiers naturels vérifiant la relation
$$25g-108c =1.$$
- Soit $x$ un entier naturel.
Démontrer que si $x\equiv a\;[7]$ et $x\equiv a\;[19]$, alors $x\equiv a\;[133]$.
-
- Vérifier que pour tout entier $x$ tel que $1\leqslant x\leqslant 6$, on a $x^6\equiv 1\;[7]$.
- On suppose que $a$ n'est pas un multiple de $7$.
Démontrer que $a^{108}\equiv 1\;[7]$.
En déduire que $\left(a^{25}\right)^g\equiv a\;[7]$.
- On suppose que $a$ est un multiple de $7$.
Démontrer que $\left(a^{25}\right)^g\equiv a\;[7]$.
- On admet que pour tout entier naturel $a$, $\left(a^{25}\right)^g\equiv a\;[19]$.
Démontrer que $\left(a^{25}\right)^g\equiv a\;[133]$.
Partie C
On note $A$ l'ensemble des entiers naturels $a$ tels que : $1\leqslant a\leqslant 26$.
Un message, constitué d'entiers appartenant à $A$, est codé puis décodé.
La phase de codage consiste à associer, à chaque entier $a$ de $A$, l'entier $r$ tel que $a^{25}\equiv r\;[133]$ avec $0\leqslant r < 133$.
La phase de décodage consiste à associer à $r$, l'entier $r_1$ tel que $r^{13}\equiv r_1\;[133]$ avec $0\leqslant r_1< 133$.
- Justifier que $r_1\equiv a\;[133]$.
- Un message codé conduit à la suite des deux entiers suivants : $128$\quad$59$.
Décoder ce message.