mala_mu je napisao:Pošto je u zadatku dato da je [inlmath]n^2+2^n[/inlmath] prost za neki prirodan broj [inlmath]n>1[/inlmath], možemo prvo potražiti koje je to [inlmath]n[/inlmath].
Da ne bude zabune, to neće biti jedno takvo [inlmath]n[/inlmath], već će biti više vrednosti [inlmath]n[/inlmath] ali takvih da zadovoljavaju uslov, kao što je i rečeno u zadatku, da su deljivi sa [inlmath]3[/inlmath], ali ne i sa [inlmath]6[/inlmath].
mala_mu je napisao:Prvo ću pretpostaviti da je [inlmath]n[/inlmath] neparan broj.
Nije potrebno da pretpostavljamo. Lako se vidi da [inlmath]n[/inlmath] mora biti neparan broj. Kada bi [inlmath]n[/inlmath] bio paran broj, tada bi zadati izraz [inlmath]n^2+2^n[/inlmath] bio paran broj veći od dvojke, pa ne bi bio prost broj.
mala_mu je napisao:Tada [inlmath]n^2+2^n[/inlmath] mogu zapisati kao [inlmath]n^2-1+2^n+1=(n-1)(n+1)+(2+1)\left(1-2+2^2+\cdots+2^{n-1}\right)=(n-1)(n+1)+3m[/inlmath].
Neka je [inlmath]n>3[/inlmath], to znači da je [inlmath]n\neq3[/inlmath], a jedan od brojeva [inlmath]n-1[/inlmath], [inlmath]n[/inlmath], [inlmath]n+1[/inlmath] djeljiv je sa [inlmath]3[/inlmath] što će reći da je [inlmath]n^2+2^n[/inlmath] djeljiv sa [inlmath]3[/inlmath].
Ja bih to rekao ovako: Pošto smo dobili da je zadati izraz [inlmath]n^2+2^n[/inlmath] jednak izrazu [inlmath](n-1)(n+1)+3m[/inlmath], sledi da nijedan od faktora [inlmath](n-1)[/inlmath] ili [inlmath](n+1)[/inlmath] ne sme biti deljiv sa [inlmath]3[/inlmath], jer bi tada [inlmath](n-1)(n+1)+3m[/inlmath] bio deljiv sa [inlmath]3[/inlmath], pa bi i zadati izraz [inlmath]n^2+2^n[/inlmath] bio deljiv sa [inlmath]3[/inlmath] i bio bi veći od [inlmath]3[/inlmath], što znači da ne bi bio prost broj.
E sad, pošto nijedan od faktora [inlmath](n-1)[/inlmath] ili [inlmath](n+1)[/inlmath] nije deljiv sa [inlmath]3[/inlmath], a znamo da tačno jedan od brojeva [inlmath](n-1)[/inlmath], [inlmath]n[/inlmath] ili [inlmath](n+1)[/inlmath] mora biti deljiv sa [inlmath]3[/inlmath] (jer su to tri uzastopna prirodna broja), sledi da će [inlmath]n[/inlmath] biti taj koji je deljiv sa [inlmath]3[/inlmath].
Pošto smo već konstatovali da [inlmath]n[/inlmath] ne sme biti parno, sledi da [inlmath]n[/inlmath] ne sme biti deljivo sa [inlmath]6[/inlmath].
Time je dokazano ono što je traženo – da je [inlmath]n[/inlmath] deljivo sa [inlmath]3[/inlmath], a da nije deljivo sa [inlmath]6[/inlmath].
Neke od vrednosti [inlmath]n[/inlmath] koje zadovoljavaju uslov da je [inlmath]n^2+2^n[/inlmath] prost broj:
[inlmath]n=3:\quad n^2+2^n=17\\
n=9:\quad n^2+2^n=593\\
n=15:\quad n^2+2^n=32\:993\\
n=21:\quad n^2+2^n=2\:097\:593[/inlmath]
Međutim, za [inlmath]n=27[/inlmath], iako [inlmath]27[/inlmath] zadovoljava uslov da je deljiv sa [inlmath]3[/inlmath] i nije deljiv sa [inlmath]6[/inlmath], dobilo bi se [inlmath]n^2+2^n=134\:218\:457[/inlmath], što nije prost broj (deljiv je sa [inlmath]73[/inlmath], sa [inlmath]521[/inlmath] i sa [inlmath]3\:529[/inlmath]). To je primer koji pokazuje da implikacija (koju je trebalo dokazati) ne važi i u obrnutom smeru.