Answer: 21
===============================================
Explanation:
Let's see if we can find a pattern where we divide powers of 3 over 30
In other words, let's see if we can find a pattern for (3^n)/30 where n is a natural number {1,2,3,4,...}
We only care about the remainders so ignore the quotients.
This is the pattern of remainders:
- 3^1 = 3. When divided over 30, we get remainder 3.
- 3^2 = 9. When divided over 30, we get remainder 9.
- 3^3 = 27. When divided over 30, we get remainder 27.
- 3^4 = 81. When divided over 30, we get remainder 21.
- 3^5 = 243. When divided over 30, we get remainder 3.
- 3^6 = 729. When divided over 30, we get remainder 9.
We see the pattern repeating again after we get to remainder 3 a second time. The pattern of remainders is {3, 9, 27, 21} which repeats forever.
The length of this cycle is 4. So what we do is divide the exponent by 4 to see what the remainder is. For instance, both 1 and 5 lead the same remainder when we divide by 4. This tells us 3^1 and 3^5 lead to the same remainder as shown in the pattern above.
Similarly, 3^2 and 3^6 lead to the same remainder. These items are spaced exactly four units apart, which is the length of the cycle.
For the exponent 2020, we get 2020/4 = 505 remainder 0
Having a remainder 0 is the same as having remainder 4, when dividing by 4.
So we'll be looking in the fourth slot of the cycle {3,9,27,21} to see the answer is 21.
Dividing 3^2020 over 30 leads to a remainder of 21.
