Last digits of powers: Mersenne primes and perfect numbers

Recently, a new Mersenne prime has been discovered.  In the highly technological world of today, prime numbers play a, well, prime role.

The search for bigger and bigger primes has been a subject of interest in recent years, mainly due to the increasing computational power that we have achieved, and, oh yes, for the money. One of these big efforts to discover bigger and bigger primes is GIMPS, an online collaborative search for prime numbers.

The newest prime found has the form

$$p_{49}=2^{74207281}-1$$

In particular Mersenne primes are well suited to be found by computers, as computing powers of 2 results in an easy task (just left shift). 

The first question one would ask is, how big is this number anyway? This is an easy question to solve. In order to find out how many digits does $p_{49}$ have, we only have to find its logarithm base 10. This will give the exponent $e$ such that

$$10^e=p_{49},$$

which gives the number of digits $p_{49}$ has by calculating $\lceil e \rceil$.  This gives

$$\lceil e \rceil=\lceil \log 2^{74207281}-1\rceil =\lceil \log 2^{74207281}\rceil=\lceil 74207281 \log 2\rceil=22338618\,,$$

where the second equality is true since $2^{74207281}$ is not a number of the form $999\dots 9$.

The second question that could pop into our minds is, what is the last digit of this number? or even more, what are the last m digits of this number?

In order to solve this, we can use two important results in modular arithmetic: the Chinese Remainder Theorem and Euler's Theorem.

The idea is that we do not need to calculate the whole number to find some of its digits. The relevance of Euler's theorem is that estates that powers leave cyclic remainders when divided by a number. It gives a way to calculate this period. For example, to find the last $m$ digits of, say, $2^k$, really what we are asking is for the remainder that $2^k$ leaves when divided by $10^m$, that is

$$2^k\equiv d \text{ mod } 10^m\,,$$

where $d$ gives the last $m$ digits when taken to be in the least residue system. It is easier to analyze this congruence if we write $10^m=2^m\cdot 5^m$.  Thus the problem translates to

$$2^k\equiv d_1 \text{ mod } 2^m\,,$$

$$2^k\equiv d_2 \text{ mod } 5^m\,.$$

We transformed a single congruence in a system of congruences, which at first sight may seem more complicated, but in fact, it is easier to handle. The first congruence is rather straightforward. If $k>m$ we have that $d_1\equiv 0$. For the second one, we can use the magic of Euler's theorem,  since $gcd(2,5^m)=1$ we have that 

$$2^{\phi(5^m)}\equiv 1 \text{ mod }5^m\,,$$

that is, the period for the powers of $2$ modulo $5^m$ is given by Euler's totient

$$\phi(5^m)=(5-1)5^{m-1}\,.$$

This means that to find out $d_2$, we can reduce the exponent $k$ and only consider its residue modulo $\phi(5^m)$. If 

$$k\equiv e\text{ mod }\phi(5^m)\,,$$

then we have that 

$$2^k\equiv 2^e\text{ mod } 5^m\,.$$

The advantage of this is that instead of calculating the powers with $k$ as the exponent (a huge number), we only need to calculate a power $e$ that is smaller than $4\cdot 5^{m-1}$, which might be much smaller than $k$.

Then, using the Chinese Remainder we get that

$$d\equiv 2^e2^m 2^{4\cdot 5^m-m}\equiv 2^e2^{4\cdot 5^m}\text {mod }10^m\,.$$

This helps us to calculate the last, for example, 3 digits of $p_{49}$ as 352-1=351. 

Another interesting calculation that can be made has to do with perfect numbers.  It is not known a general formula for perfect numbers, but we know that every Mersenne prime creates a perfect number.

$$P=2^{k-1}(2^k-1)$$ 

gives a perfect number if $2^k-1$ is prime. Hence there is an associated perfect number with $p_{49}$ given by

$$2^{74207280}(2^{74207281}-1)\,.$$

Similarly, we can calculate that it is 44,677,235 digits long and its last 3 digits are 776. And the best part, we don't have to know the other 44, 677,232 digits!