Racine de l'unité modulo n

• 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 ${\displaystyle x}$ est une racine k-ième de l'unité et ${\displaystyle x-1}$ n'est pas un diviseur de zéro, alors ${\displaystyle \sum _{j=0}^{k-1}x^{j}\equiv 0{\bmod {n}}}$. En effet,

  ${\displaystyle (x-1)\sum _{j=0}^{k-1}x^{j}\equiv x^{k}-1\equiv 0{\bmod {n}}}$.

Nous désignons le nombre de racines k-ièmes de l'unité modulo ${\displaystyle n}$ par ${\displaystyle f(n,k)}$. Il satisfait un certain nombre de propriétés :

• ${\displaystyle f(n,1)=1}$ pour ${\displaystyle n\geq 2}$ ;
• ${\displaystyle f(n,\lambda (n))=\varphi (n)}$ où λ désigne l'indicatrice de Carmichael et ${\displaystyle \varphi }$ l'indicatrice d'Euler ;
• ${\displaystyle n\mapsto f(n,k)}$ est une fonction multiplicative^[2] ;
• ${\displaystyle k\mid l\implies f(n,k)\mid f(n,l)}$ ;
• ${\displaystyle f(n,\mathrm {ppcm} (a,b))=\mathrm {ppcm} (f(n,a),f(n,b))}$ où ${\displaystyle \mathrm {ppcm} }$ désigne le plus petit multiple commun ;
• pour ${\displaystyle p}$ premier, ${\displaystyle \forall i\in \mathbb {N} \ \exists j\in \mathbb {N} \ f(n,p^{i})=p^{j}}$. L'application ${\displaystyle 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 ${\displaystyle f}$ rapidement.

• 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 ${\displaystyle x}$ une racine λ(n)-ième de l'unité (qui doit exister par définition de λ), alors ${\displaystyle 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 ℓ.

Nous désignons le nombre de racines k-ièmes primitives de l'unité modulo n par ${\displaystyle g(n,k)}$. Cette fonction satisfait les propriétés suivantes :

• ${\displaystyle g(n,k)>0\Leftrightarrow k\mid \lambda (n)}$ ;
• ${\displaystyle g(n,1)=1}$ ;
• ${\displaystyle g(2^{n},2)=3}$ pour ${\displaystyle n\geq 3}$^[2] ;
• ${\displaystyle g(2^{n},2^{k})=2^{k}}$ pour ${\displaystyle k\in [\![2,n-1]\!]}$ ;
• ${\displaystyle g(n,2)=1}$ pour ${\displaystyle n\geq 3}$ et ${\displaystyle n\in }$ suite A033948 de l'OEIS ;
• ${\displaystyle \sum _{k\in \mathbb {N} }g(n,k)=f(n,\lambda (n))=\varphi (n)}$ ;
• Le lien entre ${\displaystyle f}$ et ${\displaystyle g}$ peut être écrit de manière élégante en utilisant une convolution de Dirichlet :

  ${\displaystyle f=\mathbf {1} *g}$, c'est-à-dire ${\displaystyle f(n,k)=\sum _{d\mid k}g(n,d)}$.

• Arithmétique et théorie des nombres