Congruence ax ≡ b, inverse modulo n et chiffrement

Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

À propos de cette leçon

Terminale, mathématiques expertes › PGCD, Bézout et Gauss

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits

Congruence ax ≡ b, inverse modulo n et chiffrement

PGCD, Bézout et Gauss. PGCD, algorithme d'Euclide, Bézout, Gauss, équation diophantienne, chiffrement

Échauffement

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

  1. Quel est le plus petit entier positif xx tel que 21≡x [5]21 \equiv x\ [5] ?
  2. Quel est le reste de la division de 282^{ 8 } par 5 ?
  3. On sait que x≡2 [9]x \equiv 2\ [9] et y≡1 [9]y \equiv 1\ [9]. Quel est le reste de x+yx + y modulo 9 ?

Découvrir

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

  1. 55
  2. 13\dfrac{1}{3}

L'idée clé

On ne divise pas : on multiplie par un inverse.

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

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

Exemple corrigé

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

5×3≡1 [7]5 \times 3 \equiv 1\ [7]
L'inverse de 3 est 5.
x≡20 [7]x \equiv 20\ [7]
On multiplie par 5.
x≡6 [7]x \equiv 6\ [7]
On réduit.

À toi, guidé

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

33
2 × 3 = 6 ≡ 1.

Entraînement ★

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

Attention !

Entraînement ★★

  1. Avec le chiffrement y≡3x+1 [26]y \equiv 3x + 1\ [26], quel nombre yy code x=3x = 3 ?
  2. Avec le chiffrement y≡3x+1 [26]y \equiv 3x + 1\ [26], quel nombre yy code x=8x = 8 ?
  1. Quel est l'inverse de 2 modulo 5 ?
  1. Résous 2x≡10 [11]2x \equiv 10\ [11] : donne xx entre 0 et 10.

Bilan

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

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

Fiche résumé

Inverse modulo nn

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

Attention : on multiplie, on ne divise pas.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Quel est l'inverse de 3 modulo 11, entre 0 et 10 ?
Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits