Have you ever noticed that whenever a large prime is found in mathematics, the following sentence always pops up somewhere: “.. and it’s last 10 digits are: xxxxxxxxxx “. How are these terminating digits found? Do they just calculate the whole number and then look at the tail? Does it take a supercomputer to actually find these digits?
Turns out: no, not really. Even you can do it.
Where do the last digits come from?
Let’s first consider where these terminating digits actually come from. Say that we want to find the last 2 digits of 7531 * 8642. Don’t pull out a calculator, instead, think about where these last 2 digits would actually come from. Would they be affected by all digits in our numbers? Of course not, if we visualize this multiplication using the area model, only the red areas affect the last 2 digits of our number:
As you can see, the last 2 digits of all other products are ’00’. Thus, the product of any two numbers whose last 2 digits are ’42’ and ’31’ will have the same last 2 digits, everytime. Specifically, 42 * 31 = 1302, so the last two digits of 7531 * 8642 are ’02’.
Mersenne Primes
Time to go a little bigger. Mersenne Primes are primes given by \(2^p – 1\) where \(p\) itself is prime as well. Pretty much all of the largest primes we know are Mersenne Primes. In fact, the largest prime we know is a Mersenne Prime: \(2^{57885161} – 1\). Want to know what its last 10 digits are?
The problem is somewhat similar to the one we faced previously, except instead of two numbers, we have to multiply 57885161 numbers together. Luckily, since all of these numbers are the same, there is a quick way to do this! Here’s a Python implementation of the algorithm:
def mypow(x, n): if(n == 0): return 1 if(n == 1): return x if(n == 2): return x * x if(n % 2 == 0): return mypow(x * x, int(n / 2)) return x * mypow(x * x, int((n - 1) / 2))
However, if we now ask it to calculate mypow(2, 57885161) % 10000000000, nothing happens. That’s because in the end, this query will only return the last 10 digits, but it calculates all of them, which is exactly what we were trying to avoid.
The key now is to split our gigantic power into the string of multiplications it really is, and after a multiplication, drop all digits that aren’t in the last 10. As you saw above, to do this we use % 10000000000 or % 10**10 (\(10^{10}\)). Here’s what the code looks like:
def mypow(x, n, digits): if(n == 0): return 1 if(n == 1): return x % (10 ** digits) if(n == 2): return x * x % (10 ** digits) if(n % 2 == 0): return mypow(x * x, int(n / 2), digits) % (10 ** digits) return x * mypow(x * x, int((n - 1) / 2), digits) % (10 ** digits)
As you can see, I went for an extra argument specifying how many digits we are looking for. First, test it a little and see if it works. For example, 2^10 = 1024, so mypow(2, 10, 2) should return 24. After that, try mypow(2, 57885161, 10) - 1 (don’t forget the -1!). It should return 1724285951, the last 10 digits of our prime!
Bigger!
If you have a decent computer, the answer should have appeared in a few seconds. We should be able to calculate even larger Mersenne Primes with this method. Prime(3443958) is the largest known prime for which \(2^p-1\) is prime, but, hypothetically, let’s just assume that prime(10000000) satisfies this condition as well! The number would be astronomically large, WolframAlpha estimates it has approximately \(3.43\cdot{10}^{54012208}\) digits. But in a few seconds, our function tells us the last ten digits of this number are 6819899391!
Does this always work?
You might be wondering whether this works for any sort of large number. Unfortunately, it doesn’t always work out as well as for Mersenne Primes. Generally, any number that can be calculated by multiplications and additions only, is fine. Take, for example, the non-Mersenne but still enormously large prime 19249 * 2^13018586 + 1. The following query gives its last 10 digits: (19249 * mypow(2, 13018586, 10) + 1) % (10 ** 10), returning 8618996737.
Anyway, that’s it for now. Happy digit-hunting.