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

In summary, the Chinese remainder theorem states that a system of equations involving congruences modulo different numbers uniquely determines all numbers in a certain range and that all solutions are congruent modulo the product of those numbers. This theorem can be applied to finding prime numbers, as demonstrated in the conversation. Specifically, for a range N, all prime numbers in that range will be congruent to either 1 or 5 modulo N=2*3*5, and only numbers congruent to those values modulo N can potentially be prime. This method, known as trial division, can also be used for factoring and testing for primality.
  • #1
John Creighto
495
2
The Chinese remainder theorem tells us that the system of equations:

[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 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:
Code:
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:

[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.
 
Last edited:
Physics news on Phys.org
  • #2
This is useless for larger numbers.
 
  • #3
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.
 

1. What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical theorem that states that if we have a system of congruences with relatively prime moduli, then there exists a unique solution for the system of congruences. This theorem is useful in various areas of mathematics, including number theory and cryptography.

2. How does the Chinese Remainder Theorem help in finding primes?

The Chinese Remainder Theorem can be used in conjunction with binary search to efficiently find and test primes. By breaking down a large number into smaller congruences, we can use the Chinese Remainder Theorem to quickly check if these smaller congruences are satisfied by a potential prime number. This greatly reduces the number of potential candidates to be tested, making the process more efficient.

3. What is a binary search and how does it relate to finding primes?

A binary search is a search algorithm that works by dividing a sorted list in half and repeatedly comparing the middle element to the desired value. By discarding the half of the list that does not contain the desired value, the search can be completed in logarithmic time. In the context of finding primes, the binary search is used to efficiently narrow down the potential candidates for prime numbers.

4. What are the advantages of using the Chinese Remainder Theorem and binary search to find primes?

Using the Chinese Remainder Theorem and binary search allows for a much faster and more efficient way to find and test primes compared to traditional methods. This is because it greatly reduces the number of potential candidates that need to be tested, saving time and resources. Additionally, this method can be easily automated, making it ideal for large-scale prime searches.

5. Are there any limitations to using the Chinese Remainder Theorem and binary search in finding primes?

While the Chinese Remainder Theorem and binary search can greatly enhance the process of finding primes, it is not a foolproof method. There is still a small chance of potential primes slipping through the sieve, and additional tests may still be necessary to confirm the primality of a number. Additionally, this method may not be suitable for finding extremely large primes, as the calculations become increasingly complex and time-consuming.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
799
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
14
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
11
Views
367
  • Precalculus Mathematics Homework Help
Replies
1
Views
906
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
813
Back
Top