title: Racine de l'unité modulo n
text: # Racine de l'unité modulo n
  
  En arithmétique modulaire, une racine k-ième de l'unité modulo n, pour des entiers k, n ≥ 2, est une racine de l'unité dans l'anneau ℤ/nℤ, c'est-à-dire une solution $x$ de l'équation $x^{k}\equiv 1{\bmod {n}}$. Si k est l'ordre de $x$ modulo n, alors $x$ est appelé racine k-ième primitive de l'unité modulo n.
  
  Les racines primitives modulo n sont les racines $\varphi (n)$-ièmes primitives de l'unité modulo n, où $\varphi$ est l'indicatrice d'Euler.
  
  ## Racines de l'unité
  
  ### Propriétés
  
  * Modulo n, si x est une racine k-ième de l'unité, alors x est inversible (d'inverse $x^{k–1}).$ Autrement dit, x et n sont premiers entre eux.
  * Modulo n, si x est inversible, alors c'est une racine k-ième primitive de l'unité modulo n, où k est l'ordre multiplicatif de x modulo n.
  * Si $x$ est une racine k-ième de l'unité et $x-1$ n'est pas un diviseur de zéro, alors $\sum _{j=0}^{k-1}x^{j}\equiv 0{\bmod {n}}$. En effet,
  
      $(x-1)\sum _{j=0}^{k-1}x^{j}\equiv x^{k}-1\equiv 0{\bmod {n}}$.
  
  ### Nombre de racines k-ièmes
  
  Nous désignons le nombre de racines k-ièmes de l'unité modulo $n$ par $f(n,k)$. Il satisfait un certain nombre de propriétés :
  
  * $f(n,1)=1$ pour $n\geq 2$ ;
  * $f(n,\lambda (n))=\varphi (n)$ où λ désigne l'indicatrice de Carmichael et $\varphi$ l'indicatrice d'Euler ;
  * $n\mapsto f(n,k)$ est une fonction multiplicative ;
  * $k\mid l\implies f(n,k)\mid f(n,l)$ ;
  * $f(n,\mathrm {ppcm} (a,b))=\mathrm {ppcm} (f(n,a),f(n,b))$ où $\mathrm {ppcm}$ désigne le plus petit multiple commun ;
  * pour $p$ premier, $\forall i\in \mathbb {N} \ \exists j\in \mathbb {N} \ f(n,p^{i})=p^{j}$. L'application $i\mapsto j$ n'est pas précisément connue. Si elle l'était, alors avec le point précédent, elle fournirait un moyen d'évaluer $f$ rapidement.
  
  ## Racines primitives de l'unité
  
  ### Propriétés
  
  * L'exposant maximum pour une racine primitive modulo n est λ(n), où λ désigne l'indicatrice de Carmichael.
  * Chaque diviseur k de λ(n) donne une racine k-ième primitive de l'unité. En effet, si k divise λ(n) et $x$ une racine λ(n)-ième de l'unité (qui doit exister par définition de λ), alors $x^{\lambda (n)/k}$ convient.
  * S'il existe une racine k-ième primitive de l'unité qui est également une racine ℓ-ième de l'unité (non nécessairement primitive), alors k divise ℓ.
  
  ### Nombre de racines k-ièmes primitives
  
  Nous désignons le nombre de racines k-ièmes primitives de l'unité modulo n par $g(n,k)$. Cette fonction satisfait les propriétés suivantes :
  
  * $g(n,k)>0\Leftrightarrow k\mid \lambda (n)$ ;
  * $g(n,1)=1$ ;
  * $g(2^{n},2)=3$ pour $n\geq 3$ ;
  * $g(2^{n},2^{k})=2^{k}$ pour $k\in [\![2,n-1]\!]$ ;
  * $g(n,2)=1$ pour $n\geq 3$ et $n\in$ suite A033948 de l'OEIS ;
  * $\sum _{k\in \mathbb {N} }g(n,k)=f(n,\lambda (n))=\varphi (n)$ ;
  * Le lien entre $f$ et $g$ peut être écrit de manière élégante en utilisant une convolution de Dirichlet :
  
      Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://localhost:6011/fr.wikipedia.org/v1/ » :): {\displaystyle f = \mathbf{1} * g} , c'est-à-dire $f(n,k)=\sum _{d\mid k}g(n,d)$.
  