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: Problem Definition:
Calculate \(3^{128} \mod 7\). Modular exponentiation, potentially using Fermat's Little Theorem, is an efficient method.Step 2: Applicable Theorem:
Fermat's Little Theorem states: For a prime 'p' and an integer 'a' not divisible by 'p', \( a^{p-1} \equiv 1 \pmod{p} \).
In this case, p = 7 (prime) and a = 3 (not divisible by 7).Applying the theorem yields:\[ 3^{7-1} \equiv 1 \pmod{7} \]\[ 3^6 \equiv 1 \pmod{7} \]Step 3: Calculation:
To find \(3^{128} \mod 7\), utilize \(3^6 \equiv 1 \pmod{7}\).
Express 128 in relation to 6: divide 128 by 6.\[ 128 \div 6 = 21 \text{ remainder } 2 \]Therefore, \(128 = 6 \times 21 + 2\).
Rewrite the expression:\[ 3^{128} = 3^{(6 \times 21 + 2)} = (3^6)^{21} \times 3^2 \]Apply the modulus 7:\[ 3^{128} \pmod{7} \equiv ((3^6)^{21} \times 3^2) \pmod{7} \]Substitute \(3^6 \equiv 1 \pmod{7}\):\[ \equiv (1^{21} \times 3^2) \pmod{7} \]\[ \equiv (1 \times 9) \pmod{7} \]\[ \equiv 9 \pmod{7} \]Find the remainder of 9 divided by 7.\[ 9 = 7 \times 1 + 2 \]The remainder is 2.
Step 4: Result:
The least non-negative remainder of \(3^{128}\) divided by 7 is 2.