Prove that there exists an integer $a$ such that $\frac{a^2-x}{p}\in \mathbb{Z}$ Let $x$ be an odd number, $y$ a positive integer, and $p$ an odd prime number such that $x^2+y^2=p$. Show that there exists an integer $a$ such that  $\dfrac{a^2-x}{p}\in \mathbb{Z}.$
This problem is one that my friend asked me, and I've considered it for some time, but I can't prove it. Thank you everyone.
 A: Hint: Because $p$ is odd and $p=x^2+y^2$ for some integers $x$ and $y$, we know that $p\equiv 1\bmod 4$. Let the prime factorization of $x$ be
$$x=q_1^{e_1}\cdots q_r^{e_r}$$
(which includes no $2$'s, since $x$ is odd). Use the fact that $x^2\equiv 0\bmod q_i$ for all $i$, together with quadratic reciprocity, to prove that $\big(\!\frac{x}{p}\!\big)=1$, so that there is an integer $a$ with $a^2\equiv x\bmod p$.
Full argument in spoiler:

 $$\begin{align*} \left(\frac{x}{p}\right)&=\left(\frac{q_1}{p}\right)^{e_1}\cdots\left(\frac{q_r}{p}\right)^{e_r}\\\\\\ &=\left(\frac{p}{q_1}\right)^{e_1}\cdots\left(\frac{p}{q_r}\right)^{e_r}\\\\\\ &=\left(\frac{x^2+y^2}{q_1}\right)^{e_1}\cdots\left(\frac{x^2+y^2}{q_r}\right)^{e_r}\\\\\\ &=\left(\frac{y^2}{q_1}\right)^{e_1}\cdots\left(\frac{y^2}{q_r}\right)^{e_r}\\\\\\ &=1^{e_1}\cdots 1^{e_r}\\\\\\ &=1 \end{align*}$$

A: Using Jocobi symbol form of quadratic reciprocity,
$$
\left(\frac{x}{p}\right) 
= \left(\frac{p}{x}\right)(-1)^{\tfrac{x-1}{2}\tfrac{p-1}{2}}=1.
$$
