A number theory problem by Vinayak Srivastava

$9^{42}=81^{21}=(80+1)^{21}$ , which gives remainder $1$ when divided by $80$ .

Hardest problem in the world. It should come as the last question on the International Maths Olympiad. If 9 has an even power on top, its remainder with 80 should be 1.

Using the language of modular arithmetic:

$9^2 = 81 \equiv 1 \mod 80$ , so

$(9^2)^{21} \equiv 1^{21} \mod 80 \equiv 1 \mod 80$

$\begin{aligned} 9^{42} &= 81^{21} \\ &= (80 + 1)^{21} \\ &= \green{\binom{21}{0} 80^{21} + \binom{21}{1} 80^{20} \cdot 1^1 + \ldots + \binom{21}{20} 80^{1} \cdot 1^{20}} + 1^1 \\ &= 80 \bigg( \green{\binom{21}{0} 80^{20} + \binom{21}{1} 80^{19} \cdot 1^1 + \ldots + \binom{21}{20} 80^{0} \cdot 1^{20}} \bigg) + 1 \\ &= 80\green{(k)} + 1 \\ &\equiv \boxed{1} \mod{(80)} \end{aligned}$

I tried a smaller number and found the remainder would be the same for a smaller power and for a larger power of some number divided by some number, I don't know how much it holds true to different kinds of numbers. $\frac{81}{80}$ gives a remainder of $1$ , so $9^{42}=81^{21}$ would also give a remainder of $\boxed{1}$

$9^{(any-even-number)}$ has the ending $1$ .

Now, every multiple of $80$ has the ending $0$ .

Thus, $9^{42}$ divided by $80$ has the remainder $1-0=\boxed{1}$