# 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.

• i.e., $x$ needs to be Quadratic Residue $\pmod p$ – lab bhattacharjee May 19 '13 at 7:46
• Unsourced, unmotivated, no sign of any effort by OP beyond cut'n'paste. Voting to close. – Gerry Myerson May 19 '13 at 7:47
• @GerryMyerson: We should let the OP respond. – Inceptio May 19 '13 at 7:48

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.$$
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$.
\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*}
• I just can't see it...and it is important that $\,x^2+y^2=p\,$ and not merely $\,x^2+y^2=0\pmod p\,$ , since for example $\,7^2+6^2=0\pmod {17}\,$ , yet $\,7\,$ is not a quadratic residue modulo $\,17\,$ . – DonAntonio May 19 '13 at 8:15