Problem E

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:

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.