check if n is a probable prime

Question

I tried to calculate n one by one by using Pari but it seems out of range. So I think I might need to simplify the modulo equation by using the order of 2,3,5,7 mod n but I do not know how to simplify it.

Answer 1

I don't know your code, but you should not directly compute $a^{p-1}.$ Use e.g.

p=10^11+25; Mod(7,p)^(p-1) = Mod(64827127026, 100000000025)

which is not out of range.

$ p=100000000001$ is not probable prime because Mod(7,p)^(p-1)= Mod(495415670782,1000000000001), but for $p=100000000003$ all results are 1 and $p$ is indeed prime. But the test is not 'perfect':

The next Carmichael number is $p=100023777217 =7\times 13\times 17\times 23\times 73\times 97\times 397$ and all results (except for $a=7$, which is a divsor of $p$) are $1,$ e.g. p=1000151515441; Mod(5,p)^(p-1) = Mod(1, 1000151515441).

The following Carmichael number is $100165237201=37\times 73\times 631\times 58771,$ the test gives $1$ as the result for all $a=2,3,5,7.$

So $100165237201$ is a "probable" prime, although it is not prime.

Answer 2

Using gamma-testers command , just input

? select(m->Mod(2,m)^(m-1)==1,[10^11..10^11+25])
%7 = [100000000003, 100000000019]
? select(m->Mod(3,m)^(m-1)==1,[10^11..10^11+25])
%8 = [100000000003, 100000000019]
? select(m->Mod(5,m)^(m-1)==1,[10^11..10^11+25])
%9 = [100000000003, 100000000019]
? select(m->Mod(7,m)^(m-1)==1,[10^11..10^11+25])
%10 = [100000000003, 100000000019]
? select(m->isprime(m,2)==1,[10^11..10^11+25])
%11 = [100000000003, 100000000019]
?

You get the two probable primes $10^{11}+3$ and $10^{11}+19$, which are actually prime (which is shown in "%$11$"