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 findthe 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 Eulers totient theorem. Let ( b ) be the number of positive integers less than b and relatively prime to b . Then Eulers theorem tells us that 2 ( b ) 1 mod b since b is odd. So if r is the remainder when 57885161is 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, thats 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 1mod 3, so P 7mod 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 7in base 12.
If youd 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, its
sympy.ntheory.totient in Python. If not, its easy to compute ( n ) if you can factor n . You just need to know two things about . First, its 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 .