Critère de primalité pour les nombres de la forme $N=4 \cdot 3^n-1$

Pedja

Inspiré par le test de Lucas-Lehmer pour les nombres de Mersenne, j’ai formulé l’affirmation suivante :

Soit $D_n(x)$ soit le polynôme de Dickson avec $ \alpha=1$. Soit $N=4 \cdot 3^n-1$ où $n>2$. Soit $S_i=D_3(S_{i-1})$ avec $S_0=D_9(6)$. Alors $N$ est premier si et seulement si $S_{n-2}  \equiv 0 \pmod{N}$ .
Vous pouvez faire ce test ici.

Preuve de la suffisance.

J’ai essayé d’imiter la preuve de Bruce du test de Lucas-Lehmer. Laissez $w=3+ \sqrt{8}$ et $v=3- \sqrt{8}$ . Il est alors possible de montrer (par induction) que $S_n=w^{9 \cdot 3^n}+v^{9 \cdot 3^n}$ . Donc $N$ divise $S_{n-2}$ signifie qu’il y a un entier $R$ tel que $$w^{9\cdot 3^{n-2}}+v^{9 \cdot 3^{n-2}}=RN$$ Multiplié par $w^{9 \cdot 3^{n-2}}$ donne $$w^{2 \cdot 3^{n}}=RNw^{9 \cdot 3^{n-2}}-1 \tag{1}$$ La quadrature des deux côtés de cette égalité donne $$w^{4 \cdot 3^{n}} = \left(RNw^{9 \cdot 3^{n-2}}-1 \right)^2 \tag{2}$$ Pour preuve par contradiction, supposons que $N$ est composé et choisissez un de ses diviseurs premiers $q$ qui n’est pas supérieur à sa racine carrée. Considérons le groupe $G=Z_q[\sqrt{8}]^{\ast}$ de tous les nombres $a+b \sqrt{8}$ modulo $q$ qui sont inversables. Le groupe $G$ a au plus des éléments $q^2-1$.  En affichant $w$ modulo $q$, les égalités (1) et (2) ci-dessus deviennent $w^{2 \cdot 3^{n}}  \equiv -1 \pmod{q}$ et $w^{4 \cdot 3^{n}}  \equiv 1 \pmod{q}$ .

Nous avons donc montré que l’ordre de $w$ divise $4 \cdot 3^{n}$ . Afin de compléter la preuve, nous devons montrer que $ \operatorname{ord}(w)$ est exactement $4 \cdot 3^{n}$ mais je ne vois pas pourquoi cela devrait être le cas. Est-il possible de montrer que $ \operatorname{ord}(w) =4 \cdot 3^{n}$ ? Est-il possible de prouver la suffisance de la revendication par une autre méthode?

gerard0

Bonjour.

édit : erreur, mauvaise lecture.

Cordialement.
NB : Drôle d'idée de laisser un 9 qui multiplie une puissance de 3, alors que 9 est justement une puissance de 3.

JRManda

Bonjour,

Pour $n>0$ un nombre pair, c'est-à-dire $n=2\cdot p$, $p\in \mathbb{N}^{\ast}$, le nombre $4\cdot 3^{n}-1=4\cdot 3^{2\cdot p}-1=\left(2\cdot 3^{p}-1\right)\cdot \left(2\cdot 3^{p}+1\right)$ est toujours composé. 
L'étude reste donc intéressante pour $n$ impair.

En espérant que cela peut faire avancer la réflexion sur le sujet.

Pedja

La formulation correcte est:
Soit $N= 4 \cdot 3^{n}-1 $ avec $n\ge 0$ . Soit $S_i=S_{i-1}^3-3  S_{i-1}$ avec $S_0=6$ . Alors $N$ est premier si et seulement si  $S_{n} \equiv 0 \pmod{N}$
J’ai une preuve mais elle est trop longue.