Let $p$ be an odd prime. Suppose there exist integers $m$ and $n$ such that $p$ divides both $m^2+1$ and $n^2+2$. Prove that there exists an integer $k$ such that $p$ divides $k^4+1$.
$\newcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}$ I have so far that the Legendre symbol $\legendre{-1}{p} = 1$, and $\legendre{2}{p}=1$, which means that $p \equiv 1 \pmod 8$. How does this help me find $k$? Or should I try a completely different approach? I would appreciate hints, and preferably not a full answer (or an answer that is revealed on hover). Thanks!
Once you have $p\equiv 1 \bmod 8$ you are done.
because the multiplicative group of $\mathbb Z_p$ is cyclic you have that it is of the form $1=x^0,x,x^2,\dots,x^{p-1}$. In this case $-1=x^{(p-1)/2}$. You should be able to work out the rest.