Question

What is the remainder when \(43^{380}\) is divided by 20?

Hint:

To find \(a^b \pmod{n}\), first reduce \(a \pmod{n}\). Then, find the smallest integer \(k>0\) such that \(a^k \equiv 1 \pmod{n}\). This \(k\) is the cycle length. The answer is then \(a^{b \pmod{k}} \pmod{n}\). If \(b \pmod{k}\) is 0, the result is \(a^k \pmod{n}\), which is 1.

Answer 1

Step 1: Understanding the Concept:
This problem requires finding the remainder of a large exponential expression, which is a problem in modular arithmetic. The key is to first simplify the base and then find the cyclicity of the remainders of its powers.
Step 2: Detailed Explanation:
We need to find the value of \(43^{380} \pmod{20}\).
First, simplify the base, 43, with respect to the modulus, 20. \[ 43 = 2 \times 20 + 3 \] So, \(43 \equiv 3 \pmod{20}\).
Therefore, the problem is equivalent to finding the remainder of \(3^{380}\) when divided by 20. \[ 43^{380} \equiv 3^{380} \pmod{20} \] Next, find the pattern (cycle) of the remainders of powers of 3 when divided by 20. \[ 3^1 \equiv 3 \pmod{20} \] \[ 3^2 \equiv 9 \pmod{20} \] \[ 3^3 = 27 \equiv 7 \pmod{20} \] \[ 3^4 = 81 = 4 \times 20 + 1 \equiv 1 \pmod{20} \] The cycle of remainders repeats after a power of 4, as we have reached a remainder of 1. The length of the cycle is 4.
Now, we need to find where the exponent 380 falls in this cycle. We do this by finding the remainder of the exponent when divided by the cycle length. \[ 380 \div 4 \] Since 80 is divisible by 4, 380 is also divisible by 4. The remainder is 0. \[ 380 \equiv 0 \pmod{4} \] A remainder of 0 means the exponent is a multiple of the cycle length, so it corresponds to the last element in the cycle, which is \(3^4\).
Step 3: Final Answer:
\[ 3^{380} = (3^4)^{95} \equiv 1^{95} \equiv 1 \pmod{20} \] The remainder is 1.