, 2020

Solution:

Note that the condition $p \mid n^{2} - q$ just means that $q$ is a quadratic residue modulo $p$, or that the Legendre symbol $\left(\frac{q}{p}\right)$ is $1$. We use these standard facts about the Legendre symbol:
- If $p \equiv \pm 1 \pmod{8}$, then $\left(\frac{2}{p}\right) = 1$.
- For an odd prime $p$,
$$\left(\frac{-1}{p}\right) = \begin{cases} -1 & \text{ if } p \equiv 3 \pmod{4} \\ +1 & \text{ if } p \equiv 1 \pmod{4} \end{cases}$$
- Quadratic reciprocity: for distinct odd primes $p$ and $q$,
$$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = \begin{cases} -1 & \text{ if } p \equiv q \equiv 3 \pmod{4} \\ +1 & \text{ otherwise } \end{cases}$$

If $p$ is a Fermat prime or Mersenne prime, then $p$ is congruent to $1$ or $7$ modulo $8$ respectively, since $p > 5$. In that case $q = 2$ works. Otherwise assume $p$ is not a Fermat prime or Mersenne prime, so that $p-1$ and $p+1$ are not powers of $2$.

If $p \equiv 1 \pmod{4}$, then let $q$ be an odd prime divisor of $p-1$, so that $p \equiv 1 \pmod{q}$. Then by quadratic reciprocity $\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right) = 1$.

If $p \equiv 3 \pmod{4}$, then let $q$ be an odd prime divisor of $p+1$, so that $p \equiv -1 \pmod{q}$. Either $q \equiv 1 \pmod{4}$ so that $\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right) = 1$ or $q \equiv 3 \pmod{4}$ so that $\left(\frac{q}{p}\right) = -\left(\frac{p}{q}\right) = -\left(\frac{-1}{q}\right) = 1$.

Solution:

(Ankan Bhattacharya) We assume the same standard facts about quadratic residues as the previous solution.

If $p \equiv 1 \pmod{4}$, then since $p > 5$, there exists an odd prime divisor $q$ of $p-4$, which gives
$$\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right) = \left(\frac{4}{q}\right) = 1$$

If $p \equiv 7 \pmod{8}$, then we can take $q = 2$.

If $p \equiv 3 \pmod{8}$, then by Legendre's three square theorem there exist odd $a, b, c$ satisfying $p = a^{2} + b^{2} + c^{2}$. Since $p > 3$, these are not all equal and we may assume without loss of generality that $b \neq c$. Then $p - a^{2} = b^{2} + c^{2}$ has a prime divisor $q \equiv 1 \pmod{4}$, which gives
$$\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right) = \left(\frac{a^{2}}{q}\right) = 1$$