When $2^{256}$ is divided by $17$, the remainder would be

### Concept & Strategy To find the remainder of a large exponent, restructure the base to a power that is exactly $1$ more or $1$ less than the divisor (or a multiple of the divisor). This leverages the negative remainder concept: $(-1)^{\text{even}} = 1$. ### Step-by-Step Solution * **Given:** Find the remainder of $2^{256} \div 17$. * **Find a strategic base:** We need a power of $2$ that is adjacent to $17$ or a multiple of $17$. Let's list the first few powers of $2$: $2^1 = 2$ $2^2 = 4$ $2^3 = 8$ $2^4 = 16$ * **Rewrite the expression:** Notice that $16$ is exactly $1$ less than the divisor $17$. We must restructure $2^{256}$ to utilize $2^4$. Divide the exponent $256$ by $4$. $$256 \div 4 = 64$$ $$2^{256} = (2^4)^{64} = 16^{64}$$ * **Apply modular arithmetic:** Now we evaluate $16^{64} \pmod{17}$. When $16$ is divided by $17$, the remainder can be expressed as $-1$. $$16 \equiv -1 \pmod{17}$$ * **Evaluate the power:** Substitute $-1$ into the exponent. $$(-1)^{64} = 1$$ Since the exponent ($64$) is even, the negative base becomes positive $1$. ### Exam Strategy & Shortcut Memorize Fermat's Little Theorem: $a^{p-1} \equiv 1 \pmod p$ when $p$ is prime. Here, $p = 17$. The theorem states $2^{16} \equiv 1 \pmod{17}$. Since $256$ is a perfect multiple of $16$ ($16 \times 16 = 256$), we can rewrite it as $(2^{16})^{16} \equiv 1^{16} \pmod{17}$, which instantly evaluates to $1$. ### Common Pitfall Students frequently rely on cyclicity (the pattern of unit digits $2, 4, 8, 6$) to solve this, but cyclicity only finds the remainder when dividing by $10$ (the units digit). It does not work for divisors like $17$. Always use modular arithmetic. ### Final Answer Therefore, the correct answer is **1**.