I was working my way through some basic number theory problems and was all thumbs while solving this problem :

List all the pairs of integer solutions $(x, y)$ of the Diophantine equation : $x^2$ $+$ $y^2$ $=$ $2^{10}$$-$$1$ and show that the list is exhaustive

How can I go about it ? A hint would be a good way to start

  • 1
    $\begingroup$ Brute force? $x$ and $y$ must both be less than 32, so just draw up a table of $n^2$ and $1023-n^2$ for $8\le n<31$ and look for common values. (The lower bound 8 is $\left\lceil \sqrt{1023-31^2} \right\rceil$). $\endgroup$ – hmakholm left over Monica Feb 22 '15 at 17:42
  • $\begingroup$ Hi , @HenningMakholm , as it is a Number theory question - may be there is a more sublime way to solve it ? $\endgroup$ – pranav Feb 22 '15 at 17:42
  • 1
    $\begingroup$ @panav: Doing the brute force calculation on a computer takes about 2 minutes (all of it typing time) and concluded there are no solutions. That's valuable information even if your goal is to find a slicker argument -- now you know what you're looking for a slicker argument for. $\endgroup$ – hmakholm left over Monica Feb 22 '15 at 17:47
  • $\begingroup$ Hi , @HenningMakholm , I was hoping to solve this using pen and paper : the computer is always there ;) $\endgroup$ – pranav Feb 22 '15 at 17:50

It has no solutions, since $x^2+y^2\equiv -1\equiv 3\pmod{4}$, but $x^2$ can only be $0$ or $1$ modulo $4$.

$2^{10}-1\equiv -1\pmod{4}$, since $4\mid 2^{10}-1-(-1)=2^{10}=4\cdot 2^{8}$.

  • $\begingroup$ Hi , @user314 , how did you arrive at the fact that it is congruent to 3(mod 4) ; can you please explain it , in a bit more detail in the answer , would be grateful ... $\endgroup$ – pranav Feb 22 '15 at 17:48
  • 1
    $\begingroup$ @pranav: they mean that $2^{10}-1\equiv3\pmod4$ $\endgroup$ – robjohn Feb 22 '15 at 17:49
  • 1
    $\begingroup$ The answer is a bit hard to understand. What you probably mean is that $2^{10}-1\equiv3\pmod4$, but that is not clear in your answer. $\endgroup$ – robjohn Feb 22 '15 at 17:51
  • 2
    $\begingroup$ @pranav: no... it is simpler than that. For $k\ge2$, $2^k\equiv0\pmod4$, so $2^{10}-1\equiv0-1\equiv3\pmod4$ $\endgroup$ – robjohn Feb 22 '15 at 17:52
  • 1
    $\begingroup$ @pranav It is a very well-known fact that $x^2+y^2\equiv -1\equiv 3\pmod{4}$ is impossible. Modulo $3,4$ are the first things I mostly always look at when I solve Diophantine equations. $\endgroup$ – user26486 Feb 22 '15 at 17:57

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.