Primality test for numbers of the form $\frac{a^p-1}{a-1}$?

Question

Here is what I observed :

Inspired by Lucas-Lehmer primality test, I think I made a primality test for numbers of the form $\frac{a^p-1}{a-1}$ but the test isn't perfect and there are some conditions to apply :

• $a$ must not be a perfect power otherwise you can get false positive.
• $p$ must be a prime number $\ge 3$ otherwise you can "break" the primality test and get false positive.

Interestingly the test passes some strong pseudoprimes, Poulet number, Carmichael number or Wieferich primes.

Let $N = \frac{a^p-1}{a-1}$

Let the sequence $S_i = 2 \cdot T_{a}(S_{i-1}/2)$ where $T_{n}(x)$ is the Chebyshev's polynomial of the first kind with $S_0 = 4$.

Then $N$ is prime if $S_{p} \equiv 2 \cdot T_{a}(2)$ (mod $N$) or $S_{p} \equiv 2 \cdot T_{a-2}(2)$ (mod $N$)

You can run the test here (outdated, see below for new test).

For the moment, I didn't find a counterexample with the two conditions.

I need help for proving it but I don't know how to start. If you found a counterexample please tell me.

EDIT : I made a new test, you can found it here (outdated)

I just changed $S_0$ is now equals to $L_n$ where $L_n$ is the $n$th Lucas number and I changed the final value of the sequence, and it seems it removes some false positive.

EDIT 2 : I made a new test,for $\frac{a^p-1}{a-1}$ you can found it here

This time, $S_0 = p$ and $N$ is prime if $S_{p} \equiv 2 \cdot T_{a}(p/2)$ (mod $N$) or $S_{p} \equiv 2 \cdot T_{a-2}(p/2)$ (mod $N$) and it removes again some false positives.

If you found again a counterexample, please tell me.

Answer 1

The test fails already for $p=3$ and $a=7$, claiming that $57=3\cdot 19$ is prime.

ADDED. And new test fails for $a=10$ and $p=5$.

ADDED#2. And the test in EDIT 2 fails for $a=52$ and $p=3$.

Answer 2

Following Max Alekseyev suggestions. The following Pari GP code provides false positives. You can play with limits $p$ and $a$ inside forprime and for loops respectively (last statement).

phi(a,p)= 
{ 
my(N=(a^p-1)/(a-1), S=Mod(p,N), ctr=1); 
while(ctr<=p,S=2*polchebyshev(a,1,S/2);ctr+=1); 
if((S==2*polchebyshev(a,1,p/2)||S==2*polchebyshev(a-2,1,p/2))!=isprime(N),print("a=",a," p=",p," ",N)) 
}
forprime(p=3,200,for(a=3,5000,if(ispower(a),next(),phi(a,p))))

The following are false positives for $2<p<200$ and $2<a<5001$

a=52 p=3 2757
a=82 p=3 6807
a=103 p=3 10713
a=222 p=3 49507
a=260 p=3 67861
a=296 p=3 87913
a=315 p=3 99541
a=442 p=3 195807
a=466 p=3 217623
a=664 p=3 441561
a=675 p=3 456301
a=764 p=3 584461
a=1152 p=3 1328257
a=1640 p=3 2691241
a=1683 p=3 2834173
a=1785 p=3 3188011
a=2226 p=3 4957303
a=2422 p=3 5868507
a=2944 p=3 8670081
a=3601 p=3 12970803
a=3840 p=3 14749441
a=4674 p=3 21850951

It seems that false positives are found just for $p=3$. You can improve your test by OR-ing more conditions to exclude $p=3$ falses first, then $p=5$ (if there is any) and so on.

NOTE Code was modified as it is indicated in comments. Output list too.