4. Zadatak

Kako je najveći zajednički djelitelj brojeva $a$ i 35 jednak 1, to je najveći zajednički djelitelj brojeva $a$ i 5, kao i $a$ i 7 jednak 1.

Svaki cijeli broj $a$ relativno prost s 5 može se zapisati u jednom od oblika: $5k\pm1$ ili $5k\pm2$, a onaj relativno prost sa 7 može se zapisati u obliku: $7k\pm1$, $7k\pm2$ ili $7k\pm3$. S druge strane, dani broj se može zapisati ovako: $$\begin{aligned} &(a^4-1)\left((a^4+a^2+1)+14a^2\right)\\ &=(a^2-1)(a^2+1)(a^4+a^2+1)+14a^2(a^4-1)\\ &=(a^6-1)(a^2+1)+14a^2(a^4-1). \end{aligned}$$ Sada se lako provjeri da je svaki od ova dva sumanda djeljiv i s 5 i sa 7, tj. da je djeljiv s 35: $$\begin{aligned} a=5k\pm1&\quad\Rightarrow\quad a^2=5M+1\quad\Rightarrow\quad5\mid a^2-1\\ a=5k\pm2&\quad\Rightarrow\quad a^2=5M+4\quad\Rightarrow\quad5\mid a^2+1, \end{aligned}$$ odakle slijedi da $5\mid a^4-1$. Zato je drugi sumand djeljiv s 35.

Nadalje, prvi sumand je djeljiv s 5, pa treba još pokazati da je djeljiv i sa 7. $$\begin{aligned} a=7k\pm1&\Rightarrow a^2=7M+1\Rightarrow7\mid a^2-1\\ a=7k\pm2&\Rightarrow a^2=7M+4\Rightarrow a^4=7N+2\Rightarrow a^6=7W+1\\ a=7k\pm3&\Rightarrow a^2=7M+2\Rightarrow a^4=7N+4\Rightarrow a^6=7W+1, \end{aligned}$$ odakle slijedi $7\mid a^6-1$.

Napomena. U dokazu se može koristiti i mali Fermatov teorem.