Universalis

DIVISIBILITÉ

Théorèmes classiques

Théorème d'Euler-Fermat

Euler établit, en 1760, le théorème d'Euler-Fermat, suivant lequel, si m est entier naturel, et (a, m) = 1, on a :

En effet, un système réduit de résidus modulo m, soit r1, r2, ..., rϕ(m) est transformé, on l'a vu, en un système réduit par multiplication par a ; donc ar1, ar2, ..., arϕ(m) sont, modulo m, égaux à une permutation de r1, r2, ..., rϕ(m) d'où le produit :

que l'on peut simplifier par r1 r2 ... rϕ(m) premiers à m. D'où la formule d'Euler-Fermat. Fermat avait établi en 1736 ce théorème dans le cas particulier de m = p premier. Il s'agit du «  petit théorème de Fermat », suivant lequel :
si a n'est pas multiple de p. On l'écrit, sans condition sur a, sous la forme ap ≡ a(mod p). On remarquera que la réciproque de ce théorème n'a pas lieu (par exemple m = 561 = 3 × 11 × 17 vérifie, pour tout a premier à m, a560 ≡ 1). On a d'autre part établi (Beeger en 1951) qu'il existe une infinité d'entiers n pairs tels que 2n − 2 est divisible par n (le plus petit de ces nombres étant 161 038).

Théorème de Wilson

Le théorème de Wilson énonce que :

pour tout p premier (théorème publié en 1770 par Waring et démontré par Lagrange en 1771). Supposant p impair et développant :
Lagrange obtient, après avoir multiplié par x puis changé x en (x − 1), une identité permettant d'établir que p |A1, p |A2, ..., p |Ap-2 et (p − 1) Ap-1 ≡ 1 (mod p). On a donc Ap-1 ≡ − 1 (mod p), ce qui établit le théorème, car Ap-1 = (p − 1) !. On a de plus :
ce qui, pour x premier à p, donne le petit théorème de Fermat. On verra une autre démonstration du théorème de Wilson, dans le paragraphe des résidus quadratiques.

Racines primitives

La notion de racine primitive modulo m, est liée à la formule d'Euler :

Soit en effet k le plus petit exposant pour lequel ap ≡ 1 (mod m). On dit que a appartient à l'exposant k (mod m), ou que k est l'ordre de a, modulo m. Il s'ensuit que k divise tout x tel que ax ≡ 1 (mod m) ; en particulier, k |ϕ (m), et on dit que a est une racine primitive modulo m si l'ordre de a est ϕ(m), c'est-à-dire si ϕ(m) est effectivement le plus petit exposant pour lequel ap ≡ 1 (mod m). Cette définition montre que tout entier congru, modulo m, à une racine primitive, en est également une. Ces racines primitives ont l'importante propriété que, pour chacune d'elle, a par exemple, les nombres a, a2, a3, ..., aϕ(m) forment un système réduit de résidus. On démontre que tout p premier possède des racines primitives ; il y en a exactement ϕ(p − 1) distinctes entre elles, modulo p. Cela découle d'un théorème assez surprenant suivant lequel, si p est premier, et d |(p − 1), il y a exactement ϕ (d) nombres non congrus 2 à 2 et dont l'ordre est d (modulo p) ; le nombre des nombres d'ordre d (modulo p) ne dépend donc pas de p, dès que d divise (p − 1). Pour l'existence des racines primitives modulo m, avec m non premier, l'étude, plus délicate, fut faite par Gauss, qui établit que ces racines primitives n'existent que si m = 2, 4 ou pk ou 2pk (p premier impair quelconque).

La suite de cet article est accessible aux abonnés

  • Des contenus variés, complets et fiables
  • Accessible sur tous les écrans
  • Pas de publicité

Découvrez nos offres

Déjà abonné ? Se connecter

Écrit par

  • Marcel DAVID : professeur à la faculté des sciences de Reims

Carte mentale
Élargissez votre recherche dans Universalis

Classification

Pour citer cet article

Marcel DAVID, « DIVISIBILITÉ », Encyclopædia Universalis [en ligne], consulté le . URL :

Autres références

  • ALGÉBRIQUES STRUCTURES

    • Écrit par Jean-Marie PRUVOST-BEAURAIN
    • 29 463 mots
    ...un anneau unifère commutatif, e⊤ l'élément neutre de la loi l⊤, e⊥ l'élément neutre de la loi l⊥, et a et b deux éléments de E. On dit que bdivisea, ou que b est un diviseur de a, ou que a est un multiple de b, s'il existe dans A au moins un élément q tel que a = b...

  • ANNEAUX COMMUTATIFS

    • Écrit par Jean-Luc VERLEY
    • 6 217 mots
    • 1 média
    La présence dans un anneau de diviseurs de zéro, c'est-à-dire d'éléments a et b, tous deux non nuls, dont le produit est nul, rend illusoire toute théorie satisfaisante de la divisibilité. Les anneaux commutatifs sans diviseurs de zéro sont appelés des anneaux intègres ou anneaux...

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

    • Écrit par Christian HOUZEL
    • 12 998 mots
    ...d'après ce qui précède q ≡ h(1)λ-1 ≡ 1 (modλ) (théorème de Fermat ; cf. divisibilité). On voit comme ci-dessus que les entiers rationnels divisibles par h(α) sont les multiples de q ; pour continuer le raisonnement et montrer que h(α) est premier, on va prouver qu'il existe un entier rationnel...

  • ORDONNÉS ENSEMBLES

    • Écrit par André WARUSFEL
    • 1 725 mots
    • 2 médias
    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. Sur la figure, on a représenté le diagramme sagittal de l'ordre...

Voir aussi

Abonnez-vous à Universalis pour 1 euro

Rejoignez-nous

Inscrivez-vous à notre newsletter