5. Zadatak

Prvo rješenje.

Koristeći binomni poučak dobivamo

$$\begin{aligned} 21^{2021} &=(1+20)^{2021}\\ &=1+2021\cdot20+\binom{2021}{2}\cdot20^2+\binom{2021}{3}\cdot20^3+\cdots\\ &=1+40420+2021\cdot1010\cdot400+\binom{2021}{3}\cdot8000+\cdots\\ &=40421+1000N, \end{aligned}$$

za neki prirodan broj $N$ (neispisani pribrojnici sadrže faktor $20^k$, gdje je $k\geq4$, pa su sigurno djeljivi s $1000$).

Posljednje tri znamenke broja $21^{2021}$ su stoga $421$.

Drugo rješenje.

Neka je $x=21$. Tada računamo

$$\begin{aligned} x^{50}-1 &=(x^{25}+1)(x^{25}-1)\\ &=(x^{25}+1)(x^{20}+x^{15}+x^{10}+x^5+1)(x^5-1)\\ &=(x^{25}+1)(x^{20}+x^{15}+x^{10}+x^5+1)\\ &\qquad\cdot(x^4+x^3+x^2+x+1)(x-1). \end{aligned}$$

Budući da je $x=21$, prva je zagrada parna, a zadnja je djeljiva s $20$. Kako je $x\equiv1\pmod5$, a isto vrijedi i za bilo koju potenciju od $x$, dvije zagrade u sredini su djeljive s $5$. Tako smo dobili da je izraz na desnoj strani djeljiv s $1000$, odnosno da vrijedi

$$21^{50}\equiv1\pmod{1000}.$$

Zato je dovoljno naći zadnje tri znamenke broja $21^{21}$ jer je $2021=40\cdot50+21$. Očito je

$$21^1\equiv21\pmod{1000}.$$

Redom kvadrirajući dobivamo

$$21^2\equiv441\pmod{1000},$$ $$21^4\equiv481\pmod{1000}.$$

Sada vidimo da je

$$21^5=21^4\cdot21\equiv101\pmod{1000}.$$

Ponovno kvadrirajući, dobivamo

$$21^{10}\equiv201\pmod{1000},$$ $$21^{20}\equiv401\pmod{1000},$$

te

$$21^{21}=21^{20}\cdot21\equiv421\pmod{1000}.$$

Stoga broj $21^{2021}$ završava s $421$.

Napomena:

Početak drugog rješenja može se izvesti i koristeći Eulerov poučak: budući da je $\varphi(1000)=400$, dobivamo da je $21^{2021}\equiv21^{21}\pmod{1000}$.

Rješenje je moguće izvesti i potencirajući ostatak pri dijeljenju s $1000$ broja $21$ na $2021.$ potenciju, recimo koristeći identitet $21^{2021}=(21^{43})^{47}$ ili $21^{2021}=(21^{47})^{43}$.