4. Zadatak

Prvo rješenje.

Ako je $p\ne3$, tada imamo dva slučaja:

1. $p=3k+1$, $k\in\mathbb Z$. Tada je $$p^2+8=9k^2+6k+9,$$ što je djeljivo sa 3.
2. $p=3k+2$, $k\in\mathbb Z$. Tada je $$p^2+8=9k^2+12k+12,$$ što je također djeljivo sa 3.

U oba slučaja $p^2+8$ ne može biti prost broj.

Prema tome, jedina mogućnost da su $p$ i $p^2+8$ prosti brojevi je $p=3$ (tj. $p^2+8=17$) i u tom slučaju $p^3+4=31$ je također prost.

Drugo rješenje.

Ako broj nije djeljiv sa 3, tada njegov kvadrat daje ostatak 1 pri dijeljenju sa 3.

Zato je, za $p$ koji nije djeljiv sa 3, broj $p^2+8$ djeljiv sa 3, pa $p^2+8$ nije prost.

Zaključujemo da je jedina mogućnost $p=3$ i tada je $p^3+4=31$ zaista prost broj.