Primality test for numbers of the form $(10^p-1)/9$ (and maybe $((10 \cdot 2^n)^p-1)/(10 \cdot 2^n-1)$)

Solution 1:

It generally works with most primes, I've thrown this sort of test (in a more refined form) at literally millions of numbers.

You could look at http://www.os2fan2.com/gloss/maths.pdf where I give a working function to deal with this sort of problem.

The Messerine test amounts to that if $p = 7\pmod{24}$, then isoquad(4,(p+1)/4, 2, 4)=0 makes p prime. A run over the first million cases produced only a handful of fails. If p+1 = 2^x.(odd), and 2^x > odd, then this is sufficient proof that p is prime.

The messerine test in the form above depends on that the prime is upper-long, ie the period divides p+1 an odd number of times. A result of 0 equates to a quarter-period.

The particular test that you are running will of course demonstrate that if p is prime, it will divide either S(p+1)-2 or S(p-1)-2, and that the value at p is adjacent to both sides of the value it divides (ie upper vs lower).

The thing is somewhat more robust than the small fermat theorom, which states that if p is prime, then p | (b^(p-1)-1. This is because this class of bases equates to that p | (b^p-1)-2 or p | b^(p+1)-2, and it is harder to create a composite number that divides both these values (p-1, p+1).

For example, 1729 is a pseudoprime to every base. It has three divisors, 7, 13, and 19, with individual periods of 6, 12, 18. This means that 1/1729 in any base has a period that divides 36, and 36 divides 1728. So b^1728-1 is a multiple of 1729.

A number like 341 is a pseudoprime to 2, in that 341 | 2^340 - 1, but 341 = 11 *31. In base 2, 341 has a 10-digit period, and 10 A 341.