The Chinese remainder theorem tells us that the system of equations:(adsbygoogle = window.adsbygoogle || []).push({});

[tex]\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}

[/tex]

Uniquely determines all numbers in the range:

[tex] X<N=n_1n_2\ldots n_k[/tex]

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 lets 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 lets 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:

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

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

[tex]x=7^{n1}11^{n2}13^{n3}19^{n4}23^{n5}29^{n6}[/tex]

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.

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Loading...

Similar Threads - Find Test Primes | Date |
---|---|

I How to find admissible functions for a domain? | Jan 31, 2018 |

I How to find the matrix of the derivative endomorphism? | Oct 22, 2017 |

I Finding the Kernel of a Matrix Map | Sep 15, 2017 |

A How can I find the collision time of 2 ellipsoids that rotate | May 22, 2017 |

Finding small primes (fast determanistic tests) | Aug 2, 2006 |

**Physics Forums - The Fusion of Science and Community**