What is the remainder when $2^{31}$ is divided by $5$?

### Concept & Logic This problem requires understanding the **Cyclicity of Remainders** (or power cycles). When powers of a number are divided by a divisor, the remainders repeat in a fixed cycle. Finding the length of this cycle allows us to reduce huge exponents to manageable numbers. ### Step-by-Step Solution * **Calculation:** * Let's find the pattern of remainders when powers of $2$ are divided by $5$: * $2^1 = 2 \implies 2 \pmod 5 = 2$ * $2^2 = 4 \implies 4 \pmod 5 = 4$ * $2^3 = 8 \implies 8 \pmod 5 = 3$ * $2^4 = 16 \implies 16 \pmod 5 = 1$ * Once we hit a remainder of $1$, the cycle repeats. The cyclicity of $2$ when divided by $5$ is **$4$**. * Now, divide the given exponent ($31$) by the cyclicity ($4$) to find the remaining cycle steps. $$ 31 \div 4 = 7 \text{ with a remainder of } 3 $$ * This means the pattern repeats exactly $7$ times, and we need the $3^{\text{rd}}$ value in the cycle. * The $3^{\text{rd}}$ value corresponds to $2^3$. $$ 2^{31} \pmod 5 \equiv 2^3 \pmod 5 = 8 \pmod 5 = 3 $$ ### Exam Strategy & Shortcut An alternative faster method is using **Fermat's Little Theorem**, which states that if $p$ is a prime number, then $a^{p-1} \pmod p = 1$. Here, $p = 5$, so $2^4 \pmod 5 = 1$. Break the exponent $31$ into multiples of $4$: $$ 2^{31} = 2^{28} \cdot 2^3 = (2^4)^7 \cdot 2^3 $$ Since $2^4 \pmod 5 = 1$, the expression becomes $1^7 \cdot 8 = 8$. Dividing $8$ by $5$ leaves $3$. ### Common Pitfall A common error is confusing the unit digit cycle with the remainder cycle. While they often align (because finding the unit digit is essentially finding the remainder when divided by $10$), you must explicitly check the cycle for the specific divisor given in the question (in this case, $5$). ### Final Answer **Therefore, the correct answer is 3.**