DIVISIBILITÉ

Carte mentale

Élargissez votre recherche dans Universalis

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 | (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 à 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]× [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]≠ 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 (ab) = (a(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 :

alors F est aussi multiplicative, et réciproquement.

De plus, on a :

où :

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 non multiplicatives ; elle s'établit par simple calcul, et fournit la démonstration la plus simple du fait que f est multiplicative si F l'est. L'implication en sens contraire est beaucoup plus simple à établir ; elle résulte de ce que tout diviseur d'un produit de deux nombres premiers entre eux est le produit d'un diviseur de l'un par un diviseur de l'autre.

On établit donc que la fonction ϕ d'Euler est arithmétiquement multiplicative, soit en la mettant sous la forme :

car c'est :
où les pi sont les facteurs premiers de m ; soit aussi en considérant les nombres de la forme ax + by qui sont premiers à ab (système réduit de résidus, modulo ab).

Si l'on envisage alors :

on a une fonction multiplicative qui, par simple calcul, donne Φ(pα) = pα, donc Φ(m) = m pour tout m. Cela établit la formule classique :
qui peut aussi se démontrer en rangeant 1, 2, 3, ..., m en classes Cd, comprenant les nombres dont le P.G.C [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 6 pages

Écrit par :

Classification

Autres références

«  DIVISIBILITÉ  » est également traité dans :

ALGÉBRIQUES STRUCTURES

  • Écrit par 
  • Jean-Marie PRUVOST-BEAURAIN
  •  • 34 159 mots

Dans le chapitre « Espèces de structures plus riches que celle d'annoïde »  : […] Un corpoïde est un annoïde (E, λ ⊤ , λ ⊥ ) tel que tout élément appartenant à E qui n'est pas un élément neutre du groupoïde commutatif (E, λ ⊤ ) soit un élément symétrisable de la catégorie (E, λ ⊥ ). Un anneau est un bimagma (E,  l ⊤ ,  l ⊥ ) tel que (E,  l ⊤ ) soit un groupe abélien et (E,  l ⊥ ) un demi-groupe (c'est-à-dire un magma associatif) tel que la loi de composition interne l ⊥ soit […] Lire la suite

ANNEAUX COMMUTATIFS

  • Écrit par 
  • Jean-Luc VERLEY
  •  • 6 490 mots
  •  • 1 média

Dans le chapitre « Anneaux de Dedekind »  : […] Par définition, on appelle anneau de Dedekind tout anneau intégralement clos et noethérien (c'est-à-dire dans lequel tout idéal est engendré par un nombre fini d'éléments) dans lequel tout idéal premier non nul est maximal. Cela signifie que le quotient de A par un idéal premier non nul quelconque est non seulement un anneau d'intégrité mais même un corps. L'exemple le plus simple d'un tel anneau […] Lire la suite

NOMBRES (THÉORIE DES) - Nombres algébriques

  • Écrit par 
  • Christian HOUZEL
  •  • 14 064 mots

Dans le chapitre « Entiers cyclotomiques »  : […] Considérons, avec Kummer, un nombre premier impair λ et une racine λ-ième imaginaire α de 1 ; ainsi : L'équation de degré λ − 1 précédente est irréductible sur le corps Q des nombres rationnels, donc les nombres 1, α, α 2 , ..., α λ-2 sont linéairement indépendants sur Q  ; les entiers cyclotomiques correspondant à λ sont les nombres de la forme : où a 0 , a 1 , ..., a λ-2  ∈  Z , c'est-à-dire l […] Lire la suite

ORDONNÉS ENSEMBLES

  • Écrit par 
  • André WARUSFEL
  •  • 1 802 mots
  •  • 2 médias

Dans le chapitre « Quelques ordres sur N* »  : […] On peut munir l'ensemble N* des entiers naturels strictement positifs de diverses relations d'ordre qui montreront bien la grande variété de propriétés que l'on peut obtenir ainsi. Après la relation ≤ usuelle, la relation d'ordre la plus courante est la relation de divisibilité : si p divise q , c'est-à-dire si q est multiple de p  : cela signifie qu'il existe un entier m  ∈  N* tel que q  =  mp. […] Lire la suite

Voir aussi

Pour citer l’article

Marcel DAVID, « DIVISIBILITÉ », Encyclopædia Universalis [en ligne], consulté le 06 mai 2022. URL : https://www.universalis.fr/encyclopedie/divisibilite/