Primality test for numbers of the form $(11^p-1)/10$

Solution 1:

This is a partial answer.

This answer proves that if $N$ is prime, then $S_{p-1} \equiv S_{0}\pmod{N}$.

Proof :

Let us first prove by induction that $$S_i=a^{11^{i+1}}+a^{-11^{i+1}}\tag1$$ where $a:=2+\sqrt 3$.

For $i=0$, $(1)$ holds since $a^{11}+a^{-11}=1956244=S_0$.

Suppose that $(1)$ holds for $i$.

Letting $b_m:=a^{11^{i+1}\ m}+a^{-11^{i+1}\ m}$, one gets $$\begin{align}S_{i+1}&=S_{i}^{11}-11 S_{i}^9+44 S_{i}^7-77 S_{i}^5+55 S_{i}^3-11 S_{i} \\\\&=(b_{11} + 11b_9 + 55b_7 + 165b_5 + 330 b_3 + 462b_1) \\&\qquad -11(b_9 + 9 b_7 + 36 b_5 + 84 b_3 + 126 b_1) \\&\qquad +44(b_7 + 7 b_5 + 21 b_3 + 35 b_1) \\&\qquad -77(b_5 + 5 b_3 + 10 b_1) \\&\qquad +55(b_3 + 3 b_1) \\&\qquad -11b_1 \\\\&=b_{11} \\\\&=a^{11^{i+2}}+a^{-11^{i+2}}.\quad\square\end{align}$$

Using $(1)$, one has $$\begin{align}S_{p-1}&=(2+\sqrt 3)^{10N+1}+(2-\sqrt 3)^{10N+1} \\\\&=(2+\sqrt 3)(2+\sqrt 3)^{10N}+(2-\sqrt 3)(2-\sqrt 3)^{10N} \\\\&=(2+\sqrt 3)(262087 + 151316 \sqrt 3)^{N}+(2-\sqrt 3)(262087 - 151316 \sqrt 3)^{N} \\\\&=2\bigg((262087 + 151316 \sqrt 3)^{N}+(262087 - 151316 \sqrt 3)^{N}\bigg) \\&\qquad +\sqrt 3\bigg((262087 + 151316 \sqrt 3)^{N}-(262087 - 151316 \sqrt 3)^{N}\bigg) \\\\&=2\sum_{k=0}^{N}\binom Nk262087^{N-k}\bigg((151316\sqrt 3)^{k}+(-151316\sqrt 3)^{k}\bigg) \\&\qquad +\sqrt 3\sum_{k=0}^{N}\binom Nk262087^{N-k}\bigg((151316\sqrt 3)^{k}-(-151316\sqrt 3)^{k}\bigg) \\\\&=2\sum_{j=0}^{(N-1)/2}\binom N{2j}262087^{N-2j}\bigg(2(151316\sqrt 3)^{2j}\bigg) \\&\qquad +\sqrt 3\sum_{j=1}^{(N+1)/2}\binom N{2j-1}262087^{N-(2j-1)}\bigg(2(151316\sqrt 3)^{2j-1}\bigg) \\\\&=4\sum_{j=0}^{(N-1)/2}\binom N{2j}262087^{N-2j}\cdot 151316^{2j}\cdot 3^j \\&\qquad +2\sum_{j=1}^{(N+1)/2}\binom N{2j-1}262087^{N-(2j-1)}\cdot 151316^{2j-1}\cdot 3^j\end{align}$$

Since $N$ is prime, one has, for $1\leqslant i\leqslant N-1$, $\displaystyle\binom Ni\equiv 0\pmod N$, so one gets $$\begin{align}S_{p-1}&\equiv 4\binom N{0}262087^{N}\cdot 151316^{0}\cdot 3^0 \\&\qquad+2\binom N{N}262087^{0}\cdot 151316^{N}\cdot 3^{(N+1)/2}\pmod N \\\\&\equiv 4\cdot 262087^{N}+6\cdot 151316^N\cdot 3^{(N-1)/2}\pmod N \\\\&\equiv 4\cdot 262087^{N}+6\cdot 151316^N\cdot \dfrac{(-1)^{(N-1)/2}}{\bigg(\dfrac N3\bigg)}\pmod N\end{align}$$where $\bigg(\dfrac{q}{p}\bigg)$ denotes the Legendre symbol.

• By Fermat's little theorem, one has $262087^{N}\equiv 262087\pmod N$ and $151316^N\equiv 151316\pmod N$.

• $N\equiv 1\pmod 4$ since if $p=6n+5$, then $2N\equiv 10N\equiv 11^{6n+5}-1\equiv 3^{6n+5}-1\equiv 3^5\cdot 729^n-1\equiv 3\cdot 1^n-1\equiv 2\pmod 8$, and if $p=6n+1$, then $2N\equiv 10N\equiv 11^{6n+1}-1\equiv 3^{6n+1}-1\equiv 3\cdot 729^n-1\equiv 3\cdot 1^n-1\equiv 2\pmod 8$.

• $\bigg(\dfrac N3\bigg)=1$ since $N\equiv 10N\equiv 11^p-1\equiv (-1)^p-1\equiv 1\pmod 3$.

Therefore, one finally has $$\begin{align}S_{p-1}&\equiv 4\cdot 262087+6\cdot 151316\cdot \frac 11\pmod N \\\\&\equiv 1956244\pmod N \\\\&\equiv S_0\pmod N.\quad\blacksquare\end{align}$$

Solution 2:

I don't know if this helps, but we can show that if $q\neq 5$ is prime and $p$ doesn't divide $(q-1)$, then $q$ doesn't divide $N$. When $p$ divides $(q-1)$, it's not difficult to find examples such as $(11^5-1)/10 = 5\cdot 3221$ and $(11^7-1)/10$ which is divisible by $43$.

Let $a=11$, $N=(a^p-1)/(a-1)$ and $q<N$ be a prime number such that $p$ does not divide $q-1$. Our purpose is to show that $N\neq 0$ (mod q).

If $q=2$ or $q=5$, then $$N=\frac{a^p-1}{a-1} = 1 + a + a^2+\dots + a^{p-1} = 1+1+\dots+1 = p \hspace{5mm} (\textrm{mod}\ q)$$ Thus, $N=1$ (mod 2), and $N\neq 0$ (mod 5) unless $p=5$. But, the case $p=q=5$ is ruled out by the hypothesis (first example above).

If $q=a=11$, then $N=(a^p-1)/(a-1) = 1$ (mod 11).

For the remainig cases, assume for a contradiction that $N=0$ (mod q). Since $q$ does not divide $10 = a-1$, then $a-1$ has an inverse in the field $\mathbb{Z}_q$, so $(a-1)^{-1}(a^p-1) = 0$ in $\mathbb{Z}_q$. Since the field $\mathbb{Z}_q$ has no zero divisors, then either $(a-1)^{-1}=0$ (which is impossible) or $a^p = 1$ in $\mathbb{Z}_q$. Second, since $q$ doesn't divide $a$, $a^{q-1}=1$ in $\mathbb{Z}_q$ by Fermat's little theorem. Thus, $p$ divides $q-1$. Contradiction.

Solution 3:

I don't think your test is sufficient. See mathlove's answer for context and necessity.

Notice that $a^{11^{p-1}}=(2+\sqrt{3})^{11^{p}}\equiv (2+\sqrt{3})^{11}\mod N$ is a stronger condition than what you have, and $a^{11^{p-1}}=(2+\sqrt{3})^{11^{p}}\equiv (2+\sqrt{3})^{11}\mod N\Rightarrow ((2+\sqrt{3})^{11})^{11^{p-1}-1}\equiv 1\mod N$. Thus $ord_a(N)|11^{p-1}-1$.

Conversely, if $ord_a(N)|11^{p-1}-1$, then $a^{11^{p-1}}=(2+\sqrt{3})^{11^{p}}\equiv (2+\sqrt{3})^{11}\mod N$, so this is a stronger condition.

This condition does not seem sufficient: notice that $N-1=\frac{11^p-1}{10}-1=\frac{11^p-11}{10}=\frac{11(11^{p-1}-1)}{10}$. Also note that $a=(2+\sqrt{3})^{11}$ and so $ord_a(N)|11^{p-1}-1$ is not any stronger than "$N$ is a Fermat probable prime base a."

So why does the test work so well for the numbers tested? One of the reasons may be that $\frac{11^p-1}{10}$ is already a Fermat probable prime (a priori before the test) to base $11$. Further, it is a strong probable prime base $11$, and primover base $11$. What the test is is essentially a Fermat probable prime test in another base, on a number that by construction is already a probable prime.