Congruence
Deux nombres entiers et sont dits congrus modulo si divise la différence . Cela est souvent noté :
où est un entier positif appelé le modulus. En termes simples, et laissent le même reste lorsqu'ils sont divisés par .
Exemples :
car la différence est divisible par 6.
car et donnent tous deux un reste de lorsqu'ils sont divisés par .
Les systèmes de chiffrement comme RSA utilisent des congruences pour coder et décoder des messages.
Le calcul des fonctions de hachage pour la vérification de l'intégrité des données ou pour des structures de données comme les tables de hachage utilise également des congruences.
Propriétés de base :
Addition et Soustraction:
Si et , alors et .
Multiplication:
Si et , alors .
Puissance:
Si , alors pour tout entier positif , .
(la réciproque est fausse).