Nombre premier long

La longueur de la période du développement en base ${\displaystyle b}$ non divisible par ${\displaystyle p}$ du rationnel ${\displaystyle 1/p}$ (laquelle commence directement après la virgule) étant égale à l'ordre de ${\displaystyle {\overline {b}}}$ dans le groupe ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$^[3], le nombre ${\displaystyle p}$ est un nombre premier long en base ${\displaystyle b}$ si et seulement si le groupe ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$ admet ${\displaystyle {\overline {b}}}$ comme générateur^[3], ou ce qui est équivalent, si ${\displaystyle b}$ est une racine primitive modulo ${\displaystyle p}$.

Ceci équivaut au fait que le nombre ${\displaystyle p}$ ne divise aucun des nombres ${\displaystyle b^{d}-1=(b-1)\times {\underset {d{\text{ chiffres 1}}}{\underbrace {11...1_{b}} }}}$ où ${\displaystyle d}$ est un diviseur strict de ${\displaystyle p-1}$.

En particulier, en base 10, un nombre premier ${\displaystyle p}$ différent de deux, trois et cinq est long si et seulement s'il ne divise aucun rep-unit ${\displaystyle R_{d}}$ avec ${\displaystyle d}$ diviseur strict de ${\displaystyle p-1}$.

Une caractérisation équivalente est que l'entier ${\displaystyle {\frac {b^{p-1}-1}{p}}}$ soit cyclique^[3].

• Les dix premiers nombres premiers longs en base 10 sont 7, 17, 19, 23, 29, 47, 59, 61, 97 ,109 : suite A001913 de l'OEIS.
• Les dix premiers nombres premiers long en base 2 sont : 3, 5, 11, 13, 19, 29, 37, 53, 59, 61 : suite A001122 de l'OEIS
• 2 est long en toute base impaire.
• 3 est long en base ${\displaystyle 3m+2}$ car ${\displaystyle {\overline {3m+2}}={\overline {2}}}$ engendre ${\displaystyle (\mathbb {Z} /3\mathbb {Z} )^{*}}$ ; on a ${\displaystyle 1/3=0,{\overline {m(2m+1)}}_{3m+2}}$.
• 5 est long en bases ${\displaystyle 5m+2}$ et ${\displaystyle 5m+3}$ car ${\displaystyle {\overline {2}}}$ et ${\displaystyle {\overline {3}}}$ engendrent ${\displaystyle (\mathbb {Z} /5\mathbb {Z} )^{*}}$; on a ${\displaystyle 1/5=0,{\overline {m(2m)(4m+1)(3m+1)}}_{5m+2}}$ et ${\displaystyle 1/5=0,{\overline {m(3m+1)(4m+2)(2m+1)}}_{5m+3}}$