Large prime gap between $10^{4999}-20777$ to $10^{4999}+22669$?

Question

According to my calculation, the numbers $10^{4999}-20777$ and $10^{4999}+22669$ are consecutive (very probable) primes.

1) Are the numbers really prime ?

2) Are the primes really consecutive ?

I did not check all the numbers in one session, so I might have forgotten to check some numbers.

Answer 1

You should mention what testing methods you used.

You likely have a pair of Probable primes. From the PRP Records, you'd need to run the following tests:

• N does not have any prime factor up to 2^32.
• N cannot be trivially written into a product.
• Take 3 square-free consecutive bases such that $(b_1/N)=(b_2/N)=(b_3/N)= -1$. $N$ should be such that $b_1^{(N-1)/2}=b_2^{(N-1)/2}=b_3^{(N-1)/2}= -1 (\mod N)$.
• Take a prime base such that $(b/N)= -1$ and $b<>b_1<>b_2<>b_3$. $N$ should pass the strong test in base b.

Mathematica's PrimeQ uses probable prime methods. As of yet, there are no known examples of a composite number passing all of the current probable prime tests -- but 15 years ago, there was another suite of tests and two counterexamples were found, which led to the new suite of tests.