This is also HMMT 2020 Team P9.

Quite straight idea. Take $p>7,$ when $4\mid p-1,$ consider odd prime factor of $p-1$ (if no take factor of $p-4,$) then use Law of quadratic reciprocity. When $4\mid p+1$ take prime factors of $p+1,$ we get only $p=2,3,5$ are solution.

The answer is $p=2,3,5$. For $p\ge 7$, we divide into cases. Case 1. $p\equiv 1\pmod 4$. Then pick a prime divisor $q$ of $p-4$, which exists since $p>5$. By the law of quadratic reciprocity $$\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)=\left(\frac{4}{q}\right)=1.$$Case 2. $p=7$. Then $2\equiv 9=3^2\pmod 7$ so we can choose $q=2$. Case 3. $p\equiv 3\pmod 4$ and $p>7$. Then one of $p+1,p+9$ is not a power of $2$, so it has an odd prime divisor $q$. Observe that $$q\le\frac{p+9}{4}<p.$$Moreover, by the law of quadratic reciprocity $$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}=(-1)^{\frac{q-1}{2}}=\left(\frac{-1}{q}\right)$$$$\implies\left(\frac{q}{p}\right)=\left(\frac{-p}{q}\right)=1.$$