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

Question

This question is the successor of Primality test for numbers of the form (3^p−1)/2

Here is what I observed:

Let $N$ = $(11^p-1)/10$ when $p$ is a prime number $p > 3$.

Let the sequence $S_i=S_{i-1}^{11}-11 S_{i-1}^9+44 S_{i-1}^7-77 S_{i-1}^5+55 S_{i-1}^3-11 S_{i-1}$ with $S_0=1956244$. Then $N$ is prime if and only if $S_{p-1} \equiv S_{0}\pmod{N}$.

I choose $1956244$ because this is one of the "seeds" for the test of Lucas–Lehmer and it seems it works with this "seed" (you can find the seeds for Lucas–Lehmer test at OEIS A018844) and this seed matches with the sequence when $S_0 = 4$, $S_1 = 1956244$. $4$ is the first seed of the Lucas–Lehmer test.

For the sequence, I choose the Chebyshev's polynomial $T_{11}(x)$ and divided each part by $2^{2n}$: $$\frac{1024}{1024}x^{11}-\frac{2816}{256}x^9+\frac{2816}{64}x^7-\frac{1232}{16}x^5+\frac{220}{4}x^3-\frac{11}{1}x.$$

For the test, I use PARI/GP.

For example with $p = 17$ I found with PARI/GP:

 Mod(1956244, 50544702849929377)
 Mod(15674474965388057, 50544702849929377)
 Mod(44534929988004909, 50544702849929377)
 Mod(28140092860411758, 50544702849929377)
 Mod(15603700915052433, 50544702849929377)
 Mod(37189226565807060, 50544702849929377)
 Mod(20742285445093842, 50544702849929377)
 Mod(44492854083486120, 50544702849929377)
 Mod(17447547902277534, 50544702849929377)
 Mod(45802288862695262, 50544702849929377)
 Mod(35665546395277410, 50544702849929377)
 Mod(14106987120477193, 50544702849929377)
 Mod(8318528060373474, 50544702849929377)
 Mod(47976595814239915, 50544702849929377)
 Mod(30975975792991455, 50544702849929377)
 Mod(47014797124698019, 50544702849929377)
 Mod(1956244, 50544702849929377)

And $50544702849929377$ is indeed a prime number.

I checked until $p=5200$ and I didn't find any counterexample.

Is there a way to explain this? I don't know how to start for proving it, especially why $S_{p-1} \equiv S_{0}\pmod{N}$ implies that $N$ is prime (still by observation). If you found a counterexample please tell me.

Answer 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}$$

Answer 2

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.

Answer 3

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.

Answer 4

The prime sequence using ISOQUAD() im http://www.os2fan2.com/glossn/maths.pdf basically supercedes all of this. In essence, the prime test amounts to something along the lines that b^^p = b mod(p), which is a version of fermat's little theorm for class-2 number systems.

This code is REXX code. REXX handles bignum inline, and this code has been tested with numbers over 2000 digits. With the modulus function, that should be not greater than half the number of digits, that is, for NUMERIC DIGITS 2000 you can use numbers as high as 1000 digits.

This program is in REXX. You can get rexx for DOS, OS/2, Windows, and a number of other platforms: search for Regina REXX in your search engine.

The following additional functions have been added.

 ptest(x,y) tests if y is prime against isobase x
 pwr(x, b, p) test if b^p-1 is prime against isobase x
 ppwr(x, b, p) tests if b^p+1 is prime against isobase x

/* */
numeric digits 2000
parse arg chalk
interpret 'cheese='chalk
say cheese
exit

ptest: ; parse arg x, y; z= isoquad(x,y,2,x,y); return z
pwr: ; parse arg x, y, z ; yy = (y**z-1)/(y-1); zz = isoquad(x, yy, 2, x, yy); return zz
ppwr: ; parse arg x, y, z ; yy = (y**z+1)/(y+1); zz = isoquad(x, yy, 2, x, yy); return zz
/* pwr(8, 120, p) for p= 5; ppwr(8, 120, p) for p=3, 31, 43 */


isoquad: procedure ; parse arg g0, i0, t0, t1, p
if i0 < 1 then do; i0 = 1-i0; t2 = t1; t1 = t0; t0 = t2; end
do forever ; if i0=1 then leave
i1 = trunc(i0/2); i2=i0-i1-i1
if i2=0 then t2=t1 ;
 else do; t2 = mmp(g0,t1,t0,p); t0 = t1 ; end
t1 = mmp(g0,t2,t0,p); g0 = mmp(g0,g0,2,p); i0=i1
end /* forever */
return t1

mmp: procedure expose p; parse arg x0, x1, x2, p;
r1 = x0 * x1-x2; r2 = trunc(r1/p)
r2 = r1 - r2 * p; if r2 < 0 then r2 = r2+p
return r2

The value for testing primes is to run isoquad(b,p,2,b,p). If the return value is not equal to b, then p is not prime. If you run it for several different values of b, and get the same b, then you are most likely looking at a prime or a pseudoprime.

Running this code on my computer with the command regina testiso 5,(1e317-1)/9, 2,5, (1e317-1)/9) pauses for a few seconds and then returns 5. Replacing the 5 with 6, it returns 6. This number has a high probability of being prime.

Running the same code using p=1e(311-1)/9 produces a number of about 300 digits.

Some notes

The process in the op is largely to produce large numbers in the isoseries. This has been superceded by isoquad, which can extend any isoseries by any value modulo p, given (b, t, t0, t1, p), where t(n+1)=b.t(n)-t(n-1). The term sort for is t(t) here. Using t0=2, t1=b, is equivalent to taking the isopower, which is a form as well behaved as ordinary powers of numbers.

The messerine prime test equates to isoquad(4, (p+1)/4,2,4,p). The value given by this is 0 when prime. The test is actually for an isoperiod of p+1, which gives 0, since cos(90 deg)=0. The value of p can be any prime p mod 24 = 7, this produces very few failures. The matching condition is that to divide the period, p=1 mod 24 (lower short) or p=7 mod 24 (upper long). For a number like 247, we see that the value of the period divides 248 (long) an odd number of times, or divides 496 an even number of times for p=1 mod 24.