In my previous post, we looked at the largest known prime, *P* = 2^{57885161} – 1, and how many digits it has in various bases. This post looks at how to find the last digit of *P* in base *b*. We assume *b* < *P*. (If *b* = *P* then the last digit is 0, and if *b* > *P* the last digit is *P*.)

If *b* is a power of 2, we showed in the previous post that the last digit of *P* is *b*-1.

If *b* is odd, we can find the last digit using Euler’s totient theorem. Let φ(*b*) be the number of positive integers less than *b* and relatively prime to *b*. Then Euler’s theorem tells us that 2^{φ(b)} ≡ 1 mod *b *since *b* is odd. So if *r* is the remainder when 57885161 is divided by φ(*b*), then the last digit of *Q* = *P*+1 in base *b* is the same as the last digit of 2^{r} in base *b*.

For example, suppose we wanted to know the last digit of *P* in base 15. Since φ(15) = 8, and the remainder when 57885161 is divided by 8 is 1, the last digit of *Q* base 15 is 2. So the last digit of *P* is 1.

So we know how to compute the last digit in base *b* if *b* is a power or 2 or odd. Factor out all the powers of 2 from *b* so that *b* = 2^{k} *d* and *d* is odd. We can find the last digit base 2^{k}, and we can find the last digit base *d*, so can we combine these to find the last digit base *b*? Yes, that’s exactly what the Chinese Remainder Theorem is for.

To illustrate, suppose we want to find the last digit of *P* in base 12. *P* ≡ 3 mod 4 and *P* ≡ 1 mod 3, so *P* ≡ 7 mod 12. (The numbers are small enough here to guess. For a systematic approach, see the post mentioned above.) So the last digit of *P* is 7 in base 12.

If you’d like to write a program to play around with this, you need to be able to compute φ(*n*). You may have an implementation of this function in your favorite environment. For example, it’s `sympy.ntheory.totient`

in Python. If not, it’s easy to compute φ(*n*) if you can factor *n*. You just need to know two things about φ. First, it’s a multiplicative function, meaning that if *a* and *b* are relatively prime, then φ(*ab*) = φ(*a*) φ(*b*). Second, if *p* is a prime, then φ(*p*^{k}) = *p*^{k} – *p*^{k-1}.

**Update**: There’s a new record prime as of January 2016, and it’s also a Mersenne prime. Update of this post here.

**Related**: Applied number theory

This seems unnecessarily sophisticated. We can compute 2^57885161 (mod b) in time “proportional to log(57885161)” by the usual square/multiply technique, and then subtract 1. No need to compute φ(b) or factorize b or anything like that. Am I missing something?

Just fun to do it this way. 🙂