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 :

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

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Root of unity modulo n » (voir la liste des auteurs).