CEMC Banner

Problem of the Week
Problem E and Solution
A Very Large Prime


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:

  1. If \(n\) is a positive integer and divisible by \(3\), then \(2^n-1\) is divisible by \(7\).

  2. 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\).

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