A prime number is an integer greater than \(1\) that has only two positive divisors: \(1\) and itself.
For some six-digit positive integer \(216\,09d\) with ones (units) digit \(d\), \(2^{21609d}-1\) is a very large prime number. In fact, the number contains \(65\,050\) digits. The number begins with \(746\,093\,103\,064\,661\,343\) and ends with the digit \(7\).
Determine the value of \(d\).
Here are some facts which may be helpful when solving this problem:
If \(n\) is a positive integer and divisible by \(3\), then \(2^n-1\) is divisible by \(7\).
If \(n\) is a positive integer and divisible by \(5\), then \(2^n-1\) is divisible by \(31\).
Did you know?
One use for very large prime numbers is in the area of cryptography, the study of coding and decoding information so that it can be securely transmitted. This area of study is very important because of its application to areas like online banking, email, and general internet security, to list just a few.
To start, we will look for a pattern in the ones digit of powers of \(2\).
\(2^1=2\), \(2^2=4\), \(2^3=8\), \(2^4=16\), \(2^5=32\), \(2^6=64\), \(2^7=128\), \(2^8=256\)
It appears that the ones digit of powers of \(2\) repeat in the cycle \(2\), \(4\), \(8\), \(6\). The next four powers of \(2\), \(2^9\), \(2^{10}\), \(2^{11}\), and \(2^{12}\), end with ones digits \(2\), \(4\), \(8\), and \(6\), respectively, as expected. It turns out that this pattern continues, can you convince yourself of this?
Since \(2^{21609d}-1\) has ones digit \(7\), we will be interested in finding powers of \(2\) with ones digit \(8\).
From the pattern, we know that \(2^{216088}\) has ones digit \(6\) since \(216\,088\) is divisible by \(4\). It then follows that \(2^{216089}\) has ones digit \(2\), \(2^{216090}\) has ones digit \(4\), and \(2^{216091}\) has ones digit \(8\). Since \(2^{216091}\) has ones digit \(8\), it follows that \(2^{216095}\) and \(2^{216099}\) also each have ones digits \(8\).
Then \(2^{216091}-1\), \(2^{216095}-1\) and \(2^{216099}-1\) each have ones digit \(7\), and the only possible values of \(d\) are \(1\), \(5\), and \(9\).
If \(d=5\), then our six-digit number \(216\,095\) is divisible by \(5\). From the facts given in the problem, it follows that \(2^{216095}-1\) is divisible by \(31\) and is therefore not a prime number. Thus, \(d \ne 5\).
If \(d=9\), then the sum of the digits of our six-digit positive integer \(216\,099\) is \(27\). If the sum of the digits of an integer is divisible by \(3\), then the integer itself is divisible by \(3\). Since \(27\) is divisible by \(3\), it follows that \(216\,099\) is divisible by \(3\). From the facts given in the problem, it follows that \(2^{216099}-1\) is divisible by \(7\) and is therefore not a prime number. Thus \(d \ne 9\).
It follows that we must have \(d=1\), and thus \(2^{216091}-1\) is a prime number ending in \(7\). In fact, this prime number is from a group of prime numbers called Mersenne primes. This number is the \(31^{st}\) Mersenne prime and it was discovered in September of \(1985\). For more on Mersenne Primes, check out the Great Internet Mersenne Prime Search (GIMPS) at www.mersenne.org. According to GIMPS, as of March \(2022\), \(51\) Mersenne Primes are known. Perhaps you will be part of a team that will discover the next Mersenne Prime. There are prizes awarded when new discoveries are found and verified.
Extension: Can you prove the two facts given in the problem? To do so, you may need to look up the proof technique called "Proof by Mathematical Induction".