3. Zadatak

Prvo rješenje.

Odredimo koji prirodni brojevi $n$ zadovoljavaju navedeno svojstvo, da im je kvadrat oblika $8k+4$.

Ako je broj neparan, onda je i njegov kvadrat neparan. Dakle, $n$ mora biti paran.

Ako je broj djeljiv sa $4$, njegov kvadrat je djeljiv sa $16$, pa onda i sa $8$.

To znači da $n$ mora biti oblika $4l+2$.

Provjerimo da svi takvi brojevi zadovoljavaju navedeno svojstvo: ako je $n=4l+2$, onda je

$$n^2=16l^2+16l+4,$$

a to je oblika $8k+4$.

Primijetimo da je kvadrat prirodnog broja manji od $1\,000\,000$ ako i samo ako je taj prirodni broj manji od $1\,000$. Dakle, treba odrediti koliko ima prirodnih brojeva manjih od $1\,000$ koji su oblika $4k+2$.

Konačno, takvi su svi brojevi $2,6,10,\ldots,998$, tj. oblika $4k+2$ za $k=0,1,2,\ldots,249$. Takvih je brojeva $250$.

Drugo rješenje.

Budući da je

$$(8k+r)^2=64k^2+16kr+r^2,$$

slijedi da $(8k+r)^2$ i $r^2$ daju isti ostatak pri dijeljenju s $8$.

Ostaci kvadrata brojeva $0,1,2,\ldots,7$ pri dijeljenju sa $8$ su redom $0,1,4,1,0,1,4,1$.

Zaključujemo da $(8k+r)^2$ daje ostatak $4$ pri dijeljenju sa $8$ ako i samo ako je $r=2$ ili $r=6$.

Primijetimo da je kvadrat prirodnog broja manji od $1\,000\,000$ ako i samo ako je taj prirodni broj manji od $1\,000$. Dakle, treba odrediti koliko ima prirodnih brojeva manjih od $1\,000$ koji su oblika $8k+2$ ili $8k+6$.

Brojevi oblika $8k+2$ manji od $1\,000$ su $2,10,\ldots,994$, tj. svi za $k=0,1,2,\ldots,124$. Takvih brojeva je $125$.

Brojevi oblika $8k+6$ manji od $1\,000$ su $6,14,\ldots,998$, tj. svi za $k=0,1,2,\ldots,124$. Takvih brojeva je također $125$, pa je konačno rješenje $250$.