2
$\begingroup$

Show that the equation has non integer solution $x^2 - 3y = 5$

According to the solutions of the exercise, for that equation to have integer solutions then $$x^2\equiv5\pmod 3$$ must be true, otherwise it has non integer solutions.

Why is this true? Where does the (mod 3) come from? Why not (mod of something else)?

$\endgroup$
  • 2
    $\begingroup$ The mod 3 deals with the $3y$ part, leaving you only with the $x$, which is very convenient. $\endgroup$ – Daniel Mar 17 '17 at 0:32
  • $\begingroup$ @Daniel so if the equation was x² - 4y = 5 i would get $$x^2\equiv5\pmod 4$$ $\endgroup$ – Cat_astrophic Mar 17 '17 at 0:36
  • $\begingroup$ Right, and then you'd need to see if this yields a contradiction or not $\endgroup$ – Daniel Mar 17 '17 at 0:37
  • 2
    $\begingroup$ @Daniel Which does not because $x^2-4y=5$ has integer solutions, e.g. $x=y=5$. Thus no $(\mbox{mod }N)$ trick works here. So I woudln't call it a technique. More like observation, in some situations it works, in others it does not. $\endgroup$ – freakish Mar 17 '17 at 0:39
  • $\begingroup$ @freakish That's right. Moreover, it may be the case in which there are no solutions at all but taking modulo doesn't yield any contradiction. For instance $x^2 + 2 y^2 = -1$, if you take modulo 2 then it would be $x^2 = -1 \mod 2$, which is not a contradiction of course $\endgroup$ – Daniel Mar 17 '17 at 0:41
3
$\begingroup$

$y=(x^2-5)/3$

For $y$ to be an integer, the numerator should be divisible by 3. Now, Every perfect square leaves a reminder of 0 or 1 when divided by 3. So, $x^2-5$ will leave reminder 1 or 2 but never zero. Thus no integer solutions are possible.

$\endgroup$
1
$\begingroup$

We rearrange the equation to get $x^2 = 3y + 5$, which says that we're looking for an $x$ that, when squared, is three times some integer $y$ plus 5. And "is equal to three times some integer plus 5" is the same as "is congruent to 5, mod 3". Hence, $x$ is a solution to the equation if and only if $x^2 \equiv 5\ (\mbox{mod } 3)$.

$\endgroup$
1
$\begingroup$

Given $x^2-3y =5$, we need $x^2-5 = 3y$. Then constraining $x$ and $y$ to integers gives us that $x^2-5$ is divisible by $3$, and thus $x^2\equiv 5\equiv 2 \bmod 3$, which doesn't have integer solutions since $x\nmid 3 \implies x=3k\pm 1\implies x^2 = 9k^2 \pm 6k +1 \equiv 1 \bmod 3$

$\endgroup$
0
$\begingroup$

More accuracy, the issue equation has the consequence $$x^2\equiv 2\pmod3.\quad(1)$$ On the other hand, unknown $x$ must belong to one of residue classes $\{0,1,2\}$ modulo $3$. So $$x^2\bmod3\in\{0,1\},$$ and that contradicts with $(1).$

$\endgroup$

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.