1
$\begingroup$

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.

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you,But can you share your all answers, $\endgroup$ – math110 May 19 '13 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$ – Zev Chonoles May 19 '13 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 '13 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.