Calculer l'inverse de 7 modulo 26, et résoudre 7x ≡ 5 [26] (c'est le…

Stratégie : inverser d'abord, résoudre ensuite. Modulo $n$, on ne divise jamais : on multiplie par l'inverse, lorsqu'il existe.

a) L'inverse existe. $7\wedge 26=1$ (car $26=2\times 13$ et $7$ ne divise ni $2$ ni $13$), donc $7$ est inversible modulo $26$ : c'est le théorème de Bézout.

b) Euclide étendu. $26=3\times 7+5$, puis $7=1\times 5+2$, puis $5=2\times 2+1$. On remonte : $$1=5-2\times 2=5-2(7-5)=3\times 5-2\times 7=3(26-3\times 7)-2\times 7=3\times 26-11\times 7$$ Donc $-11\times 7\equiv 1[26]$, et comme $-11\equiv 15[26]$ : $$7^{-1}\equiv 15[26]$$

c) L'équation. En multipliant $7x\equiv 5[26]$ par $15$ : $$x\equiv 15\times 5=75\equiv 75-52=23[26]$$ Réciproquement $7\times 23=161=6\times 26+5$ : la solution est bien $x\equiv 23[26]$, et elle est unique modulo $26$.

⚠️ Le point délicat : sans l'inversibilité, l'unicité tombe. Si l'on avait travaillé modulo $26$ avec un coefficient non inversible, par exemple $2x\equiv 4[26]$, la multiplication par un « inverse » serait interdite : cette équation-là a deux classes de solutions ($x\equiv 2$ et $x\equiv 15$). C'est $7\wedge 26=1$ qui garantit une solution et une seule.

Contrôle numérique. $7\times 15=105=4\times 26+1$ ✓ ; $7\times 23=161=6\times 26+5$ ✓. Un balayage des $26$ classes ne donne que $x=23$.

Ce que l'exercice installe. C'est le déchiffrement d'un chiffre affine $y\equiv 7x+c[26]$ sur les $26$ lettres de l'alphabet : la clé de déchiffrement est $7^{-1}$, et la condition « la clé est inversible modulo $26$ » est exactement ce qui rend le chiffrement réversible. La même idée, à $2048$ bits, s'appelle RSA.