The best way to find big prime numbers is to use a thing called “modular arithmetic” and another thing called “fermat’s theorem” – not the famous “Fermat’s Last Theorem” – Fermat’s theorem is much less famous and much more useful than Fermat’s Last Theorem.<\/p>\n
\nModular arithmetic is when we do addition, subtraction and multiplication with the remainders of numbers instead of the number itself. So, if we choose a ‘base’ of 10, we’d say 3 times 4 is 2. That’s because if you choose any numbers which end in 3 and 4 (that is, their remainders are 3 and 4 when you divide them by 10), and multiply them, you get a number whose last digit is 2.<\/p>\n
Try it: what’s the last digit of 33 x 184? of 103 x 1294? Of 239830903 x 29083498954? It’s always 2.<\/p>\n
If we use a base of 7 instead, we’d say 3 x 4 is 5. If I multiply two numbers which give remainders of 3 and 4 when I divide them by 7, the result will give a remainder of 5 when I divide it by 7.<\/p>\n
That’s modular arithmetic. Fermat’s theroem says that if your base is prime, say P, then whenever if I raise A to the power of P, I get A.<\/p>\n
Examples:<\/p>\n
if P is 3,<\/p>\n
if P is 7,<\/p>\n
On the other hand, if P is 10,<\/p>\n
So if you have a big number N and you want to check if it’s prime, you can do this:<\/p>\n
All big prime numbers now rely on tricks like this one – Fermat’s theorem, or the similar Lucas-Lehmer test.<\/p>\n