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.

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

2 Answers 2


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

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*}$$

  • $\begingroup$ Thank you,But can you share your all answers, $\endgroup$
    – math110
    May 19, 2013 at 8:12
  • $\begingroup$ It's only been 4 minutes since I posted this hint. Keep trying to figure it out. "What you have been obliged to discover by yourself leaves a path in your mind which you can use again when the need arises." - G. C. Lichtenberg $\endgroup$ May 19, 2013 at 8:13
  • $\begingroup$ 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\,$ . $\endgroup$
    – DonAntonio
    May 19, 2013 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.