There are plenty of primes for k ≡ 4,8 (mod 10). The test doesn't produce false positives or negatives (so far!). So why exclude them? It makes an impression of a random statement then. (like "Here is my theorem for all cats that are black or white, but not orange, and only those that were born on Tuesday or Friday".)

For k ≡ 1,6 (mod 10), there are no primes, indeed, because 5 | k*6^n-1. But the test doesn't produce false positives for these either.

P.S. Pari also is supposed to have a polchebyshev() function, but my pari binary is old. So I made up my own P(k,x). Time to rebuild a newer binary...

[QUOTE=Batalov;380411]What is the reason for restriction k ≡ 3,9 (mod 10)?
It is easy to see that k ≡ 0,2,5,7 (mod 10) are not working (many counterexamples), but what about k ≡ 1,4,6,8 (mod 10)? None of them have counterexamples so far.
[CODE]# Pari/GP
allocatemem(1800000000);
KK=7000;
v=vector(KK); v[1]=x; v[2]=x^2-2; for(i=3,KK,v[i]=x*v[i-1]-v[i-2])
P(k,x)=eval(v[k])

t6(k,n)=s=Mod(P(k,5778),k*6^n-1);for(k=1,n-2,s=s*(s^2-3);s=s^2-2);s==0

#for example 1 (mod 10)
forstep(k=1,KK,10,for(n=3,500,if(t6(k,n) && !ispseudoprime(k*6^n-1),print(k" "n))))[/CODE][/QUOTE]

The entire idea is pointless. We know the full factorization of N+1!
Thus, the older methods of Lehmer, Selfridge, Brillhart, et.al. apply
and give a rigorous proof in probabilistic cubic polynomial time.
Just find a primitive root.....

[QUOTE=Batalov;380414]P.S. Pari also is supposed to have a polchebyshev() function, but my pari binary is old. So I made up my own P(k,x). Time to rebuild a newer binary...[/QUOTE]

Yes, absolutely! Lots of fixes, speedups, and new functions added since then.

[QUOTE=R.D. Silverman;380416]The entire idea is pointless. We know the full factorization of N+1!
Thus, the older methods of Lehmer, Selfridge, Brillhart, et.al. apply
and give a rigorous proof in probabilistic cubic polynomial time.
Just find a primitive root.....[/QUOTE]
Well, to play devil's advocate, sometimes a slow but [I]original [/I]method [I]could [/I]be of interest - even if it had no practical value.

In this particular case, though, one must agree. Because Chebyshev's are chainable, this method simply computes P[SUB](N+1)/4[/SUB](3), and why for this subclass of k's "/4" (and not "/2") works can probably be explained (?). With a small modification, it will work for all k, but it will be a PRP test even more obviously once one sees what it does.

[QUOTE=Batalov;380419]Well, to play devil's advocate, sometimes a slow but [I]original [/I]method [I]could [/I]be of interest - even if it had no practical value.[/QUOTE]

Sure. AKS is a great example.

[QUOTE=Batalov;380378]P[SUB]6[/SUB](x) = x^6 - 6x^4 + 9x^2 -[B] 2[/B]
(not -1)[/QUOTE]
I went the same way like you with the calculus up to here, and also didn't find any counterexample as long as my pari didn't step on my patience. This test seems to be some kind of PRP test for a "special base", I see no strong reason why this would be true, but also have no counterexample to give.

p.s. The new pari, after 2.5.0 and including, has the polchebyshev() function (which also evaluates the polynomial in some point, quite fast). You should upgrade to the newer pari, it is much better and faster than the previous versions and it has things for parallel processing (i.e. using all cores of your CPU).

edit: you can use (istead of the forstep with the step 10) something like:
[code]for(n=3,20,forstep(k=3,1000,[B][6,4][/B],N=k*6^n-1; s=...; for(i=1,n-2,s=...)[/code] to go through all k which are 3 or 9 (mod 10).

edit2: very good observation about other k mod 10.