# HAPPY NEW YEAR $2020$ Remainder Problem [duplicate]

I framed a new question just now. What is the Remainder when the number $$20^{20}$$ is divided by $$2020$$

My try:

$$\frac{20^{20}}{2020}=\frac{20^{19}}{101}$$

Now Consider: $$20^{18}=(400)^9=(404-4)^9=101k-2^{18}$$

Now i was trying to find Remainder without calculator or by manual division.

• It's spelt, "remainder". Dec 31, 2019 at 18:50
• oops will correct it Dec 31, 2019 at 18:52
• Just go by iterated squaring. $20^2=400\equiv -4\pmod {101}$. then $20^4\equiv 16 \pmod {101}$ and so on.
– lulu
Dec 31, 2019 at 18:55
• $20^{20}=10^{20}2^{20}\equiv 100^{10}1024^2\equiv(-1)^{10}{14}^2\equiv196\equiv95\bmod101$ and $20^{20}\equiv0\bmod20$ so $20^{20}\equiv600\bmod2020$ by the Chinese remainder theorem Dec 31, 2019 at 21:56

$$20^{19}=100^9\cdot4^9\cdot20=100^9\cdot4^{10}\cdot5=100^9\cdot1024^2\cdot5 \equiv - 14^2\cdot5=-980 \equiv 30 \; (\mod 101)$$

• That’s quite clever! +1. Dec 31, 2019 at 19:22

What is the remainder of $$20^{19}$$ when divided by $$101$$?

We can solve this by Exponentiation by Squares, at each step, just squaring the previous result. This is easy enough to do by hand.

$$20^1\equiv20\pmod{101},$$ $$20^2\equiv97\pmod{101},$$ $$20^4\equiv16\pmod{101},$$ $$20^8\equiv54\pmod{101},$$ $$20^{16}\equiv88\pmod{101}.$$

Since $$19=16+2+1$$, our desired remainder will be

$$20^{19}=20^{16}\times20^2\times20^1\equiv30\pmod{101}.$$

Finally, using that $$a\equiv b\pmod{c}$$ iff $$ak\equiv bk\pmod{ck}$$, for any non-zero $$k$$, we can deduce

$$20^{20}\equiv\boxed{600}\pmod{2020}.$$