Un entier g tel que les résidus g^k réduits modulo N produisent toutes les classes de résidus premières à N ; en d'autres termes, g engendre le groupe multiplicatif (Z/NZ)^×.

Principe

Si (Z/NZ)^× est cyclique alors un élément g unique a pour ordre multiplicatif φ(N) et ses puissances énumèrent toutes les unités modulo N.

Démonstration

Pour N = 7, l'entier 3 est une racine primitive car les puissances 3^1,...,3^6 modulo 7 donnent 3,2,6,4,5,1, couvrant les six unités ; 3 a donc pour ordre φ(7)=6.

Mauvaise application

Prétendre qu'un élément g est une racine primitive alors que g n'est pas premier à N ou que (Z/NZ)^× n'est pas cyclique (par exemple N = 8) conduit à des conclusions fausses sur la génération de toutes les unités.

Conséquence

Lorsque la racine primitive existe, les logarithmes discrets relatifs à cette racine définissent une bijection entre (Z/NZ)^× et Z/φ(N)Z, permettant des raisonnements fondés sur la structure cyclique et l'arithmétique des indices.

Inversion

La situation inverse est un élément dont les puissances engendrent seulement un sous-groupe propre de (Z/NZ)^× (par exemple un élément d'ordre divisant un diviseur propre de φ(N)), qui n'énumère pas tous les résidus premiers à N.

Limite

Les racines primitives existent pour N = 1, 2, 4, p^k et 2p^k avec p premier impair ; elles n'existent pas pour un N composite général. Le concept s'applique uniquement aux entiers premiers à N et au groupe multiplicatif des unités modulo N.

Tension sémantique

Il faut distinguer racine primitive et générateur d'un groupe additif ou d'un quelconque élément d'ordre maximal dans un sous-groupe ; 'primitive' signifie ici générateur du groupe multiplicatif complet lorsque celui-ci est cyclique.

Synthèse

Une racine primitive modulo N est un entier générateur qui, lorsqu'il existe, fait du groupe multiplicatif des unités modulo N un groupe cyclique dont les puissances parcourent toutes les classes inversibles.