Question

The remainder when $2^{2016}$ is divided by $63$ is:

• A. \( 1 \)
• B. \( 8 \)
• C. \( 17 \)
• D. \( 32 \)
• E. \( 61 \)

Hint:

Whenever the divisor is of the form \( 2^n - 1 \), the remainder of \( 2^{kn} \) will always be 1. Here, \( 63 = 2^6 - 1 \), and 2016 is a multiple of 6, so the result is immediately 1.

Answer 1

The Correct Option is A

Concept: To find the remainder of a large power, we look for a power of the base that is close to the divisor. This is based on modular arithmetic properties, specifically: if \( a \equiv 1 \pmod{m} \), then \( a^k \equiv 1^k \pmod{m} \).

Step 1: Find a power of 2 near 63.
We know that \( 2^6 = 64 \). In terms of modulo 63: \[ 2^6 \equiv 64 \equiv 1 \pmod{63} \]

Step 2: Express the total power \( 2^{2016} \) in terms of \( 2^6 \).
We check if 2016 is divisible by 6: \[ 2016 \div 6 = 336 \] So, we can write: \[ 2^{2016} = (2^6)^{336} \]

Step 3: Calculate the remainder.
Substituting the modular equivalence: \[ (2^6)^{336} \equiv (1)^{336} \pmod{63} \] \[ 2^{2016} \equiv 1 \pmod{63} \] The remainder is 1.