Find and Test Primes using the Chinese Remainder Theorem and Binary Search

[John Creighto]

The Chinese remainder theorem tells us that the system of equations:

$$\begin{align} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align}$$

Uniquely determines all numbers in the range:

$$X<N=n_1n_2\ldots n_k$$

and that all solutions are congruent modulo N.

The first four primes are congruent modulo 2. Moreover if something isn't congruent modulo 2 then it is not a prime (In other words if it is not odd it is not prime unless the number is 2).

In the range N<6=2*3
All primes must be congruent to either 1 or 5 modulo 6=2*3 because these are the only two numbers in that range which aren't divisible by either 2 or 3.

Moreover, if a number isn't congruent to either 1 or 5 modulo 6 it is not a prime.

Now let's check the range of N<30=2*3*5

In this range all prime numbers will be one of the following and the only ones of these which isn't prime is dividable by 5.

1+6n 7,13,19,25
5+6n 11,17,23,29

We can check to see if a number n in this range (n<30) is prime by dividing by 6 and seeing if the remainder is either 1 or 5 and making sure the number isn't divisible by 5. Their are 11 primes less then 30 but we can check if a number is prime with two divisions and then a binary search on an array with two elements. Thus numbers less then 30 can be checked to see if they are prime with at most four operations.

Now let's check the range N<210=2*3*5*7

Choosing numbers which are less then 30, aren't dividable by 2,3, or 5 and congruent modulo 30:

1  + 30n = 31, 61, 91,  121, 151, 181
7  + 30n = 37, 67, 97,  127, 157, 187
11 + 30n = 41, 71, 101, 131, 161, 191
13 + 30n = 43, 73, 103, 133, 163, 193
17 + 30n = 47, 77, 107, 137, 167, 197
19 + 30n = 49, 79, 109, 139, 169, 199
23 + 30n = 53, 83, 113, 143, 173, 203
29 + 30n = 59, 89, 119, 149, 179, 209

The following product can be used to find numbers in this table which aren't prime:

$$x=7^{n1}11^{n2}13^{n3}19^{n4}23^{n5}29^{n6}$$

We do not need to consider divisibility by 2, 3 or 5 because all numbers in the table are relatively prime to 2, 3 and 5.

 

[abcd1019]

This is useless for larger numbers.

 

[CRGreathouse]

You're rediscovered trial division. It's a good method for factoring (fully, if the number is less than ~1 million, or partially otherwise) and testing small numbers for primality. It can also be used to test if moderately-large numbers (~10^10) are semiprime, provided you have a fast test for primality.