DIVISIBILITÉ

Congruences

On se placera ici dans l'anneau Z des entiers relatifs. On dit que aest 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 b₁, b₂, ..., b_m 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 premier ; dans ce cas, en effet, l'anneau des classes résiduelles devient un corps, qu'on écrit en général Z/pZ ou Z/p. En effet, si[a]_p≠ 0, donc a non multiple de p, c'est-à-dire a premier avec p, on peut écrire ab + pc = 1, d'où[a]_p[b]_p = [1]_p, ce qui montre l'existence de 1 / [a]_p = [b]_p. Cela rejoint d'ailleurs une propriété classique : tout anneau fini sans diviseur de 0 est un corps. D'autre part, il est facile de voir que[a]_m = [b]_m équivaut à (a, m) = (b, m) ; on peut donc envisager les classes résiduelles premières à m qui forment, pour m donné, ce qu'on appelle un système réduit (par exemple, pour m = 18, les classes [1], [5], [7], [11], [13] et [17]). On dit alors qu'un ensemble d'entiers est un système réduit de résidus modulo m , si un et un seul de ces entiers appartient à chacune des classes d'un système réduit. Pour m = p premier, toutes les classes sauf [0] forment un système réduit, comprenant (p − 1) éléments. Dans le cas général de m quelconque, le nombre d'éléments d'un système réduit est égal à celui des nombres compris entre 1 et m et premiers à m. Ce nombre s'appelle l'indicateur d'Euler de m, désigné par ϕ(m), et l'on peut établir les conditions nécessaires et suffisantes suivantes pour qu'un ensemble de nombres soit un système réduit de résidus modulo m : ce système comprend ϕ(m) éléments ; ces éléments sont deux à deux non congrus modulo m ; chaque élément est premier à m. Il est alors évident que, si l'on multiplie chacun de ses éléments par un même facteur premier à m, on transforme un système réduit de résidus en un système réduit.

Fonctions arithmétiques classiques

La fonction ϕ d'Euler est une fonction arithmétique multiplicative ; on appelle ainsi toute fonction f définie sur les entiers naturels, et telle que f (ab) = f (a) f (b) lorsque (a, b) = 1. On établit sur les fonctions arithmétiques multiplicatives l'important théorème suivant : si f est arithmétique multiplicative et si l'on pose :

De plus, on a :

Cette fonction μ s'appelle fonction de Möbius ; elle est aussi multiplicative. La relation de réciprocité liant f à F, grâce à cette fonction de Möbius, reste d'ailleurs valable dans le cas de fonctions[...]