Congruence ax ≡ b, inverse modulo n et chiffrement

Échauffement

Trois questions rapides sur des leçons déjà vues.

Découvrir

On veut résoudre $3x \equiv 1\ [7]$ . Quelle valeur de $x$ convient ?

$5$
$\dfrac{1}{3}$

L'idée clé

On ne divise pas : on multiplie par un inverse.

Si $a$ et $n$ sont premiers entre eux, il existe un inverse $a'$ de $a$ modulo $n$ : $aa' \equiv 1\ [n]$ . Alors $ax \equiv b\ [n] \iff x \equiv a'b\ [n]$ .

Chiffrement affine : on code $x$ par $y \equiv ax + b\ [26]$ ; pour déchiffrer, on utilise l'inverse de $a$ modulo 26.

Exemple corrigé

Résous $3x \equiv 4\ [7]$ .

5 \times 3 \equiv 1\ [7]

L'inverse de 3 est 5.

x \equiv 20\ [7]

On multiplie par 5.

x \equiv 6\ [7]

On réduit.

À toi, guidé

À toi : quel est l'inverse de 2 modulo 5 ?

3

2 × 3 = 6 ≡ 1.

Entraînement ★

Résous $3x \equiv 12\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous $3x \equiv 9\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous $3x \equiv 6\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)

Attention !

Entraînement ★★

Avec le chiffrement $y \equiv 3x + 1\ [26]$ , quel nombre $y$ code $x = 3$ ?
Avec le chiffrement $y \equiv 3x + 1\ [26]$ , quel nombre $y$ code $x = 5$ ?

Quel est l'inverse de 2 modulo 5 ?

Résous $2x \equiv 10\ [11]$ : donne $x$ entre 0 et 10.

Bilan

Trois questions pour vérifier que c'est acquis.

Résous $3x \equiv 12\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous $3x \equiv 9\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)
Résous $3x \equiv 6\ [7]$ : donne la solution $x$ entre 0 et 6. (L'inverse de 3 modulo 7 est 5.)

Fiche résumé

Inverse modulo $n$

Il existe si $\mathrm{PGCD}(a ; n) = 1$ .
$ax \equiv b \iff x \equiv a'b\ [n]$ .

Attention : on multiplie, on ne divise pas.

À propos de cette leçon