Congruence
Le terme de congruence est tout droit sorti de l'arithmétique modulaire.
Définition
En arithmétique modulaire, les nombres sont des entiers modulo n, où n est un nombre entier quelconque. Une congruence est une égalité particulière, c'est une égalité adapté à l'aspect modulaire de ces nombres. C'est une égalité modulo n.
Deux nombres sont considérés comme congrus modulo n si (a-b) est un multiple de n:
a = b*(mod *n) ou a ≡ b (mod n)
Si Z/mZ est l'ensemble des entiers {0,…,m-1}, alors il n'y qu'un seul entier de Z/mZ correspondant à un nombre modulo m. Mathématiquement, selon Euclide, cet entier correspond au reste de la division Euclidienne par m.
Opérations arithmétiques
Les opérations classique de soustraction, multiplication, division et addition sont possibles. Il suffit pour cela de les effectuer sur les nombres de manière classique, puis d'appliquer le modulo au résultat.
Propriétés
Par PGCD(x, y), on définie la fonction permettant d'obtenir le Plus Grand Diviseur Commun à x et y.
- Si a ≡ b (mod n) et c ≡ d (mod n), alors: a + c ≡ b + d (mod n),
- Si a ≡ b (mod n) et c ≡ d (mod n), alors: a·c ≡ b·d (mod n),
- Si a·c ≡ b·d (mod n) et PGCD(c, n) = 1, alors: a ≡ b (mod n).
Exemple
Si m = 12, alors:
13 ≡ 1 (mod 12)
25 ≡ 1 (mod 12)
13 ≡ 25 (mod 12)