Les congruences : calculer avec des restes
Objectif : Trouver un reste, et calculer une puissance modulo un nombre premier sans jamais dépasser deux chiffres.
L’essentiel
Travailler modulo n, c'est ne garder d'un entier que son RESTE dans la division par n. Tout ce qui dépasse est jeté. « 137 modulo 6 » vaut 5 parce que 137 = 6×22 + 5.
À retenir
- a modulo n : le reste de la division euclidienne, rien d'autre
- Un reste nul est une réponse valable, et souvent la bonne
- Pour une puissance : réduire APRÈS chaque multiplication, jamais à la fin
- Petit théorème de Fermat : a^(p−1) ≡ 1 mod p, si p premier et a non multiple de p
- Modules courants ici : 5, 7, 11, 13 — tous premiers, donc le théorème s'applique
⚠ Attention, piège
- Le théorème exige que la base ne soit PAS multiple du module. 10 puissance 4 modulo 5 ne vaut pas 1 mais 0, parce que 10 est multiple de 5.
Exemples
- Reste de 198 par 9 : 9 × 22 = 198, il ne reste rien. Réponse 0.
- 4 puissance 5 modulo 13. 4² = 16 ≡ 3.
- 2 puissance 4 modulo 5 : le théorème donne la réponse sans calcul, 1. Vérification : 16 = 5×3 + 1.
Mots-clés
a^(p−1) ≡ 1 (mod p)
Le plan de la leçon
- Le reste, et rien que le reste
- Les puissances : réduire à chaque étape
- Le petit théorème de Fermat, quand le module est premier
Je me teste
Que vaut le reste de 154 divisé par 6 ?
- 3
- 2
- 4
- 0
Que vaut 2 puissance 4 modulo 5 ?
- 4
- 1
- 0
- 2
Pour calculer une grande puissance modulo n, que faut-il faire ?
- Changer de module
- Additionner les restes
- Calculer la puissance puis diviser à la fin
- Réduire après chaque produit
Le mot d’Oscar — Et il vous en faut un seul.
Réponses : 1. C · 2. B · 3. D