Racine primitive modulo n

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.