Question

The least non-negative remainder when \(3^{128}\) is divided by 7 is:

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

Hint:

When dealing with large exponents in modular arithmetic, always look for a pattern or apply theorems like Fermat's Little Theorem or Euler's Totient Theorem. This avoids calculating the large power directly. The goal is to find a smaller power that gives a remainder of 1 or -1, as this simplifies the calculation significantly.

Answer 1

The Correct Option is A

Step 1: Understanding the Concept:
This problem requires finding the value of \(3^{128} \mod 7\). This can be solved efficiently using modular exponentiation, often with the help of Fermat's Little Theorem.
Step 2: Key Formula or Approach:
Fermat's Little Theorem states that if 'p' is a prime number, then for any integer 'a' not divisible by 'p', we have: \[ a^{p-1} \equiv 1 \pmod{p} \] Here, p = 7 (a prime number) and a = 3 (not divisible by 7).
So, we can apply the theorem: \[ 3^{7-1} \equiv 1 \pmod{7} \] \[ 3^6 \equiv 1 \pmod{7} \] Step 3: Detailed Explanation:
Our goal is to find the remainder of \(3^{128}\) when divided by 7. We can use the result from Fermat's Little Theorem, \(3^6 \equiv 1 \pmod{7}\).
We need to express the exponent 128 in terms of 6. We do this by dividing 128 by 6.
\[ 128 \div 6 = 21 \text{ with a remainder of } 2 \] So, we can write the exponent 128 as: \[ 128 = 6 \times 21 + 2 \] Now, we can rewrite the original expression: \[ 3^{128} = 3^{(6 \times 21 + 2)} = 3^{(6 \times 21)} \times 3^2 = (3^6)^{21} \times 3^2 \] Now we apply the modulus 7 to this expression: \[ 3^{128} \pmod{7} \equiv ((3^6)^{21} \times 3^2) \pmod{7} \] Since we know \(3^6 \equiv 1 \pmod{7}\), we can substitute this in: \[ \equiv (1^{21} \times 3^2) \pmod{7} \] \[ \equiv (1 \times 9) \pmod{7} \] \[ \equiv 9 \pmod{7} \] Now, we find the remainder when 9 is divided by 7. \[ 9 = 7 \times 1 + 2 \] The remainder is 2.
Step 4: Final Answer:
The least non-negative remainder when \(3^{128}\) is divided by 7 is 2.