2. Fonctions arithmétiques
• Congruences
On se placera ici dans l'anneau Z des entiers relatifs. On dit que a est congru à b (modulo m), ce qui s'écrit a ≡ b (mod m), lorsque m | (a − b). Cette congruence modulo m, pour m fixé, est une relation d'équivalence (réflexive, transitive, symétrique) et permet donc de faire une partition de Z en classes (ensemble quotient par cette équivalence). Chacune de ces classes est appelée classe résiduelle modulo m, et comprend un élément et un seul a compris entre 0 et (m − 1), soit 0 ≤ a ≤ m − 1, tel que tout autre élément de la classe est égal à a + km. Si l'on désigne par [b]m la classe d'un entier b, il y a ainsi m classes, à savoir : [0]m, [1]m, [2]m, ..., [m − 1]m. On dit que m nombres b1, b2, ..., bm forment un système complet de résidus, modulo m, si ces nombres sont, deux à deux, non congrus modulo m ; ils correspondent donc aux m classes. La congruence modulo m étant stable dans l'addition et dans la multiplication, on peut munir l'ensemble des classes résiduelles des opérations de somme et de produit (avec [a]m + [b]m = [a + b]m et [a]m × [b]m = [ab]m). On obtient ainsi un anneau commutatif, dans lequel [ax]m = [ay]m entraîne [x]m = [y]m si a est premier à m ; dans le cas général, on n'aurait que [x]m/d = [y]m/d avec d = (a, m). Un cas particulièrement intéressant est celui où m = p est […]
… pour nos abonnés, l'article se prolonge sur 5 pages…
