a
b (mod n) 39 (mod 12) 0 (mod n)
a toujours une solution b (mod n)
a toujours une solution b (mod n)
a une solution si et seulement si a et n sont premiers entre eux2x = 7 (12) n'a pas de solution
| Cas général | Exemples avec n=12 |
|---|---|
| Le calcul modulo n considère seulement les nombres de 0 à n-1 | On considère les nombres de 0 à 11 |
| L'addition s'effectue de manière habituelle et on retranche n du résultat si celui-ci dépasse n | 3+4 = 7 ; 7+8 = 3 |
| La multiplication s'effectue de manière habituelle et on retranche n autant de fois que nécessaire du résultat pour que celui-ci ne dépasse pas n | 2*3 = 6; 3*4 = 0 ; 7*7 = 1 |
| Deux nombres a et b qui se différencient par
un multiple de n sont dits "congruents" (ou congrus) modulo n; notation: a b (mod n) |
3 39 (mod 12) |
| On note aussi de façon simplifiée: a = b (n) | 8 = 32 (12) |
| L'équation x + a = 0 (ou x + a 0 (mod n)
a toujours une solution |
Solution de x + 7 = 0 (12) : x = 5 (12) |
| L'équation x + a = b (ou x + a b (mod n)
a toujours une solution |
Solution de x + 7 = 2 (12) : x = 7 (12) |
| L'équation ax = b (ou a x b (mod n)
a une solution si et seulement si a et n sont premiers entre eux |
7x = 2 (12) implique x = 2 (12) 2x = 7 (12) n'a pas de solution |
L'équation a x
b (mod p)
a toujours une solution si p est premier (et a non nul). Par exemple:
2x = 7 (13) implique x = 10 (13)
Plus généralement, l'équation a x
b (mod n)
a une solution si a et n sont premiers entre eux (et a non nul). Par exemple:
3x = 2 (10) implique x = 4 (10) puisque 3 x 7 = 1 (10)
Cette dernière propriété est liée à la théorie de la divisibilité et le théorème de Bezout.
Pratiquement par division euclidienne, on cherche les nombres x et y tels que x a + y n = 1.