Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Racine primitive modulo n
Résumé
Les racines primitives modulo n sont un concept issu de l'arithmétique modulaire, dans la théorie des nombres. Ce sont (lorsqu'il en existe) les générateurs du groupe des inversibles de l'anneau Z/nZ.
Si n est un entier strictement positif, les nombres premiers avec n, pris modulo n, forment un groupe pour la multiplication, noté (Z/nZ) ou Z. Ce groupe est cyclique si et seulement si n est égal à 4 ou p ou 2p pour un nombre premier p ≥ 3 et k ≥ 0. Un générateur de ce groupe cyclique est appelé une racine primitive modulo n, ou un élément primitif de Z. Une racine primitive modulo n est donc un entier g tel que tout inversible dans Z/nZ est une puissance de g modulo n.
Prenons par exemple n = 14. Les éléments de (Z/14Z) sont les classes de congruence 1, 3, 5, 9, 11 et 13. Donc 3 est une racine primitive modulo 14, et l'on a 3 ≡ 9, 3 ≡ 13, 3 ≡ 11, 3 ≡ 5 et 3 ≡ 1 (modulo 14). La seule autre racine primitive modulo 14 est 5.
Voici une table contenant les plus petites racines primitives pour quelques valeurs de n () :
Voici une table donnant les plus petites racines primitives r modulo les nombres premiers p inférieurs à () :
On ne connait aucune formule générale simple pour calculer les racines primitives modulo n. Il existe cependant une méthode pour tester si un entier m est racine primitive mod n — c'est-à-dire si son ordre multiplicatif modulo n est égal à φ(n) (l'ordre de Z) — qui est plus rapide qu'un simple calcul mod n de toutes ses puissances successives jusqu'à l'exposant φ(n) :
Les racines primitives mod n sont les racines dans Z/nZ du φ(n)-ième polynôme cyclotomique Φ.
Pour tout nombre premier p, le n-ième polynôme cyclotomique Φ est irréductible sur le corps fini Z si et seulement si p est une racine primitive modulo n. Par conséquent, les entiers n modulo lesquels il n'existe pas de racine primitive () sont ceux tels que Φ est réductible sur tous les Z. Ce sont également les entiers modulo lesquels 1 a d'autres racines carrées que 1 et –1.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.