3. Zadatak

Prvi način:

Broj $1$ pri dijeljenju s $9$ daje ostatak $1$.

Broj $2$ pri dijeljenju s $9$ daje ostatak $2$.

Broj $2^2$ pri dijeljenju s $9$ daje ostatak $4$.

Broj $2^3$ pri dijeljenju s $9$ daje ostatak $8$.

Broj $2^4$ pri dijeljenju s $9$ daje ostatak $7$.

Broj $2^5$ pri dijeljenju s $9$ daje ostatak $5$.

Kako $2^6$ daje ostatak $1$ pri dijeljenju s $9$, ostatci broja $2^n$ pri dijeljenju s $9$ se ponavljaju periodički s periodom $6$.

Zato najprije izračunamo zbroj ostataka za prvih šest pribrojnika $1+2+4+8+7+5=27$ i zaključujemo da je zbroj $1+2+2^2+2^3+2^4+2^5$ djeljiv s $9$.

S obzirom da je $2^{6+k}=2^6\cdot2^k$, $2^{6+k}$ za svaki nenegativni cijeli broj $k$ daje isti ostatak pri dijeljenju s $9$ kao i $2^k$, tj. s obzirom da se ostatci broja $2^n$ pri dijeljenju s $9$ ponavljaju periodički s periodom $6$, zaključujemo da je zbroj

$$2^{6k}+2^{6k+1}+2^{6k+2}+2^{6k+3}+2^{6k+4}+2^{6k+5}$$

djeljiv s $9$ za svaki nenegativni cijeli broj $k$.

Zbroj $1+2+2^2+2^3+\ldots+2^{2021}$ ima $2\,022$ pribrojnika.

Kako je $2\,022$ djeljivo s $6$, pribrojnici u polaznom zbroju se mogu grupirati u skupine od $6$ pribrojnika (tih skupina ima $337$ jer je $2\,022:6=337$) čiji je zbroj djeljiv s $9$ i time zaključujemo da je polazni zbroj djeljiv s $9$, odnosno da je ostatak pri dijeljenju broja $1+2+2^2+2^3+\ldots+2^{2021}$ brojem $9$ jednak $0$.

Drugi način:

Broj $1$ pri dijeljenju s $9$ daje ostatak $1$.

Broj $2$ pri dijeljenju s $9$ daje ostatak $2$.

Broj $2^2$ pri dijeljenju s $9$ daje ostatak $4$.

Broj $2^3$ pri dijeljenju s $9$ daje ostatak $8$.

Broj $2^4$ pri dijeljenju s $9$ daje ostatak $7$.

Broj $2^5$ pri dijeljenju s $9$ daje ostatak $5$.

Kako je za prvih $6$ pribrojnika zbroj ostataka $1+2+4+8+7+5=27$, zaključujemo da je zbroj $1+2+2^2+2^3+2^4+2^5$ djeljiv s $9$.

Promotrimo li zbroj sljedećih šest pribrojnika

$$2^6+2^7+2^8+2^9+2^{10}+2^{11}=2^6\cdot(1+2+2^2+2^3+2^4+2^5),$$

zaključujemo da je i on djeljiv s $9$, jer je izraz u zagradi djeljiv s $9$, a možemo i općenito zaključiti da je

$$2^{6k}+2^{6k+1}+2^{6k+2}+2^{6k+3}+2^{6k+4}+2^{6k+5} =2^{6k}\cdot(1+2+2^2+2^3+2^4+2^5)$$

djeljivo s $9$ za svaki nenegativni cijeli broj $k$ (jer je izraz u zagradi djeljiv s $9$), tj. da je zbroj svake sljedeće skupine od šest pribrojnika opet djeljiv s $9$.

Zbroj $1+2+2^2+2^3+\ldots+2^{2021}$ ima $2\,022$ pribrojnika.

Kako je $2\,022$ djeljivo s $6$, pribrojnici u polaznom zbroju se mogu grupirati u skupine od $6$ pribrojnika (tih skupina ima $337$ jer je $2\,022:6=337$) čiji je zbroj djeljiv s $9$ i time zaključujemo da je polazni zbroj djeljiv s $9$, odnosno da je ostatak pri dijeljenju broja $1+2+2^2+2^3+\ldots+2^{2021}$ brojem $9$ jednak $0$.

Treći način:

Broj $1$ pri dijeljenju s $9$ daje ostatak $1$.

Broj $2$ pri dijeljenju s $9$ daje ostatak $2$.

Broj $2^2$ pri dijeljenju s $9$ daje ostatak $4$.

Broj $2^3$ pri dijeljenju s $9$ daje ostatak $8$.

Broj $2^4$ pri dijeljenju s $9$ daje ostatak $7$.

Broj $2^5$ pri dijeljenju s $9$ daje ostatak $5$.

Kako $2^6$ daje ostatak $1$ pri dijeljenju s $9$, ostatci broja $2^n$ pri dijeljenju s $9$ se ponavljaju periodički s periodom $6$.

Promotrimo zbroj $1+2+2^2+2^3+\ldots+2^{2021}$. Vrijedi:

• zbroj prva dva pribrojnika je $1+2=3=2^2-1$
• zbroj prva tri pribrojnika je $3+4=7=2^3-1$
• zbroj prva četiri pribrojnika je $7+8=15=2^4-1$
• itd.

Pokažimo da će se uzorak nastaviti.

Ako je zbroj prvih $k+1$ pribrojnika $1+2+\ldots+2^k=2^{k+1}-1$, onda je zbroj prvih $k+2$ pribrojnika jednak

$$2^{k+1}-1+2^{k+1}=2\cdot2^{k+1}-1=2^{k+2}-1.$$

Zato je

$$1+2+\ldots+2^{2021}=2^{2022}-1.$$

Budući da broj $2\,022$ daje ostatak $0$ pri dijeljenju sa $6$, zaključujemo da $2^{2022}$ daje ostatak $1$ pri dijeljenju s $9$, pa traženi broj daje ostatak $0$ pri dijeljenju s $9$.