Question

What is the remainder obtained when the smallest prime number, when raised to the ninety second multiple of sixteen, is divided by two hundred and fifty seven?

• A. 1
• B. 2
• C. 3
• D. 5

Hint:

257 = 2^8 + 1, so 2^8 leaves remainder -1 (that is, 256) when divided by 257, and 2^16 leaves remainder 1. Reduce the exponent 1472 modulo 16 to find the remainder quickly.

Answer 1

The Correct Option is A

We need the remainder when \(2^{1472}\) is divided by 257, where 1472 comes from 92 times 16, the ninety second multiple of sixteen. This time, instead of spotting the 16 step cycle directly, let's get there through Fermat's little theorem.

257 is a prime number, so Fermat's little theorem says that for any number not divisible by 257, raising it to the power 256, one less than 257, leaves a remainder of 1. So $2^{256} \equiv 1 \pmod{257}$.

Using this, we first bring the exponent 1472 down modulo 256:

1. 1472 divided by 256 is 5, with 256 x 5 = 1280, leaving a remainder of 1472 - 1280 = 192.
2. So $2^{1472} \equiv 2^{192} \pmod{257}$.

Now we still need $2^{192} \pmod{257}$. Since 257 = $2^8 + 1$, we know $2^8 \equiv -1 \pmod{257}$. And 192 happens to be a multiple of 8, since 192 = 8 x 24. So:

\[ 2^{192} = (2^8)^{24} \equiv (-1)^{24} \pmod{257} \]

Since 24 is an even number, $(-1)^{24} = 1$. So $2^{192} \equiv 1 \pmod{257}$, and therefore $2^{1472} \equiv 1 \pmod{257}$ as well.

Let's summarize:

• Fermat's little theorem gives $2^{256} \equiv 1 \pmod{257}$ since 257 is prime.
• Reducing 1472 modulo 256 leaves an exponent of 192.
• Since $2^8 \equiv -1 \pmod{257}$ and 192 is a multiple of 8 with an even quotient, $2^{192} \equiv 1 \pmod{257}$.

So the remainder when $2^{1472}$ is divided by 257 is 1.