The least non-negative remainder when \(3^{128}\) is divided by 7 is:
Show 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.
Step 1: Understanding the Concept: The objective is to compute \(3^{128} \mod 7\). Modular exponentiation, particularly aided by Fermat's Little Theorem, is the efficient method.
Step 2: Key Formula or Approach: Fermat's Little Theorem states that for a prime number 'p' and an integer 'a' not divisible by 'p': \[ a^{p-1} \equiv 1 \pmod{p} \] Here, p = 7 (prime) and a = 3 (not divisible by 7). Applying the theorem: \[ 3^{7-1} \equiv 1 \pmod{7} \] \[ 3^6 \equiv 1 \pmod{7} \]
Step 3: Detailed Explanation: We need the remainder of \(3^{128}\) divided by 7. Using \(3^6 \equiv 1 \pmod{7}\) from Fermat's Little Theorem. Divide the exponent 128 by 6: \[ 128 \div 6 = 21 \text{ with a remainder of } 2 \] Represent 128 as:\[ 128 = 6 \times 21 + 2 \] Rewrite the expression: \[ 3^{128} = 3^{(6 \times 21 + 2)} = 3^{(6 \times 21)} \times 3^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: Final Answer: The least non-negative remainder of \(3^{128}\) divided by 7 is 2.