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.
Modular 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.
Try it: what’s the last digit of 33 x 184? of 103 x 1294? Of 239830903 x 29083498954? It’s always 2.
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.
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.
Examples:
if P is 3,
- 1 x 1 x 1 is 1,
- 2 x 2 x 2 is 8, which has a remainder of 2.
if P is 7,
- 1^7 is 1,
- 2^7 is 128, which has a remainder of 2 when I divide by 7,
- 3^7 is 2187, which has a remainder of 3 when I divide by 7,
- 4^7 is 16384, which has a remainder of 4 when I divide by 7,
- 5^7 is 78125, which has a remainder of 5 when I divide by 7,
- 6^7 is 279936, which has a remainder of 6 when I divide by 7.
On the other hand, if P is 10,
- Although 1^10 is 1, on the other hand
- 2^10 is 1024, which has a remainder of 4, not 2, when I divide by 10.
So if you have a big number N and you want to check if it’s prime, you can do this:
- make sure N doesn’t have any small factors – if it does, it’s obviously not prime!
- choose your favourite number A
- work out A^N modulo N (that is, the remainder when you divide A^N by N – there are quick ways of doing this)
- if you don’t get A, then N is not prime.
- if you do get A, then pick a different A and try again – unless you already know from theory that you’ve checked enough different A’s for your particular N.
All big prime numbers now rely on tricks like this one – Fermat’s theorem, or the similar Lucas-Lehmer test.
If you want to find a record-breaking prime number, it can take months of computer time to check a single number. Since most numbers are not prime, a solo hunter will need to spend centuries hunting. The holders of the records get the job done by recruiting thousands of volunteers to donate unused computer time, so that record-breaking prime numbers aree discovered roughtly once every year or two. Look up the GIMPS project, for example – they own all ten of the top ten biggest known prime numbers!