4. Zadatak

Prvo rješenje.

Rastavimo dani broj na faktore:

$$\begin{aligned} 3^{12}-1&=(3^6-1)(3^6+1)\\ &=(3^3-1)(3^3+1)(3^6+1)\\ &=(3-1)(3^2+3+1)(3+1)(3^2-3+1)(3^2+1)(3^4-3^2+1)\\ &=2\cdot13\cdot4\cdot7\cdot10\cdot73. \end{aligned}$$

Traženi djelitelj je broj 73.

Napomena: Od učenika se ne traži da pokažu da nema drugih djelitelja između 70 i 80. Međutim, kada je poznat rastav na proste faktore $3^{12}-1=2^4\cdot5\cdot7\cdot13\cdot73$ to se lagano provjeri.

Drugo rješenje.

Rastavimo promatrani broj

$$3^{12}-1=27^4-1=729^2-1=531440$$

na proste faktore:

$$531440=10\cdot8\cdot6643 =2^4\cdot5\cdot7\cdot949 =2^4\cdot5\cdot7\cdot13\cdot73.$$

Traženi djelitelj je broj 73.

Treće rješenje.

Direktno ćemo provjeriti da je $3^{12}-1$ djeljivo sa 73. Rješenje zapisujemo pomoću kongruencija:

$$\begin{aligned} 3^{12}-1&=81^3-1=(73+8)^3-1\\ &\equiv8^3-1\pmod{73}\\ &=64\cdot8-1=(73-9)\cdot8-1\\ &\equiv-9\cdot8-1\equiv-73\equiv0\pmod{73}. \end{aligned}$$

Napomena: Od učenika se ne traži da pokažu da nema drugih djelitelja između 70 i 80 pa da ovakvo rješenje treba priznati kao potpuno.

Prirodan pristup zadatku bio bi promatranje koji bi od brojeva $71, 72,\ldots, 79$ mogli biti djelitelji od $3^{12}-1$. Brojeve djeljive s 3 lako je eliminirati. S ostalim brojevima može se postupiti slično kao što je ovdje napisano za broj 73 ili na neki drugi način.