Ismeretes, hogy egy egész szám négyzete $0$ vagy $1$ maradékot ad $3$-mal osztva aszerint, hogy maga a szám osztható-e $3$-mal vagy sem.
Az utóbbi esetben $p^2+8$ osztható $3$-mal, és mivel nagyobb $3$-nál, így nem lehet prím. Így ha $p^2+8$ nem osztható $3$-mal, akkor $p$ osztható kell legyen $3$-mal. Az egyetlen $3$-mal osztható prímszám a $3$ és ebben az esetben $3^2+8=17$ valóban prímszám.
A feladatnak tehát egyetlen megoldása van, $p=3.$