Arithmétique : congruences et applications

Deux entiers a et b sont congrus modulo n (noté a ≡ b [n]) si n divise a − b, autrement dit s'ils ont le même reste dans la division par n. Les congruences sont compatibles avec l'addition et la multiplication : si a ≡ b [n] et c ≡ d [n], alors a + c ≡ b + d [n] et ac ≡ bd [n]. Le petit théorème de Fermat affirme que si p est premier et a non divisible par p, alors aᵖ⁻¹ ≡ 1 [p]. Par exemple, 2⁶ = 64 ≡ 1 [7]. Ces outils sont essentiels en cryptographie : le chiffrement RSA repose sur la difficulté de factoriser le produit de deux grands nombres premiers, et utilise l'arithmétique modulaire pour chiffrer et déchiffrer. Les critères de divisibilité classiques (par 3, 9, 11) se démontrent élégamment avec les congruences.