"

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 } .