lavorare modulo 2/4 non serve a molto, mi sembra che quello che stai dicendo alla fin fine sia:
"i quadrati modulo 9 sono $0,1,4,7$; il polinomio $p^5+4p+1$, modulo 9, assume i valori 1, 6, 5, 4, 6, 5, 7, 6, 5 a seconda che $p \equiv 0,1,2,3,4,5,6,7,8 \pmod 9$. In particolare, $p^5+4p+1$ è un quadrato modulo 9 se e solo se $p \equiv 0, 3, 6 \pmod 9$, ma l'unico tale primo è $p=3$".
Oppure, per dirla in un modo più simile a come la racconti tu: modulo 3 vediamo che $p \equiv 0, 1 \pmod 3$. Se $p \equiv 0 \pmod 3$ abbiamo finito. Altrimenti scriviamo $p=3k+1$ e guardiamo modulo 9: otteniamo $n^2 \equiv 1+4p+p^5 \equiv 1+(12k+4) + (1+15k) \equiv 6 \pmod 9$, ma $6$ non è un quadrato modulo 9.