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
• E. 6

Hint:

257 = \(2^8+1\), so \(2^8 \equiv -1\) and \(2^{16} \equiv 1 \pmod{257}\). Since 1472 is a multiple of 16, the remainder is 1.

Answer 1

The Correct Option is A

Use Fermat's Little Theorem instead of the $2^8 \equiv -1$ trick.

Since 257 is prime, Fermat's Little Theorem tells us $2^{256} \equiv 1 \pmod{257}$ (the order of 2 modulo 257 divides $256$).

We need $2^{1472} \bmod 257$, so first reduce the exponent $1472$ modulo $256$:
$1472 = 5 \times 256 + 192$ (since $5 \times 256 = 1280$ and $1472 - 1280 = 192$)

So $2^{1472} = (2^{256})^5 \times 2^{192} \equiv 1^5 \times 2^{192} = 2^{192} \pmod{257}$.

Now use $2^8 \equiv -1 \pmod{257}$ (since $257 = 2^8+1$). Since $192 = 8 \times 24$:
$2^{192} = (2^8)^{24} \equiv (-1)^{24} = 1 \pmod{257}$

Both routes agree.

\[\boxed{Remainder = 1}\]