I'm looking to find solutions to $x^2 – 11y^2 = 3$ using congruences.
The question specifically asks "Can this equation be solved by congruences (mod 3)? If so, what is the solution? (mod 4) ? (mod 11) ?"
I know using (mod 4) I can show that there aren't any solutions:
$x^2 – 11y^2 \equiv 3 (mod 4)$
$x^2 – 11y^2 \equiv -1 (mod 4)$
This is unsolvable because of the fact that 11 is a prime, and it's congruent to 3 mod 4, and thus would follow that there are no solutions. Thus I know that the whole equation is unsolvable.
I'm curious because the back of the book said that this result could also be seen (mod 3), but I can't get the same result:
$x^2 – 11y^2 \equiv 3 (mod 3)$
$x^2 – 11y^2 \equiv 0 (mod 3)$
Thus x and y can both be congruent to 0 mod 3 to solve it. Can someone help me understand why this equation is provably unsolvable mod 3?
Best Answer
$$-11 \equiv -11+16 \equiv 5 \equiv 1 \pmod 4$$
So,the congruence becomes:
$$x^2+y^2 \equiv 3 \pmod 4$$
$$x \equiv 0 \pmod 4 \Rightarrow x^2 \equiv 0 \pmod 4$$
$$x \equiv 1 \pmod 4 \Rightarrow x^2 \equiv 1 \pmod 4$$
$$x \equiv 2 \pmod 4 \Rightarrow x^2 \equiv 0\pmod 4$$
$$x \equiv 3 \pmod 4 \Rightarrow x^2 \equiv 1 \pmod 4$$
$$$$
$$y \equiv 0 \pmod 4 \Rightarrow y^2 \equiv 0 \pmod 4$$
$$y \equiv 1 \pmod 4 \Rightarrow y^2 \equiv 1 \pmod 4$$
$$y \equiv 2 \pmod 4 \Rightarrow y^2 \equiv 0\pmod 4$$
$$y \equiv 3 \pmod 4 \Rightarrow y^2 \equiv 1 \pmod 4$$
We can see that it cannot be $x^2+y^2 \equiv 3 \pmod 4$
EDIT:
$$-11 \equiv 1 \pmod 3$$
So,the congruence becomes:
$$x^2+y^2 \equiv 0 \pmod 3$$
$$x \equiv 0 \pmod 3 \Rightarrow x^2 \equiv 0 \pmod 3$$
$$x \equiv 1 \pmod 3 \Rightarrow x^2 \equiv 1 \pmod 3$$
$$x \equiv 2 \pmod 3 \Rightarrow x^2 \equiv 1 \pmod 3$$
$$$$
$$y \equiv 0 \pmod 3 \Rightarrow y^2 \equiv 0 \pmod 3$$
$$y \equiv 1 \pmod 3 \Rightarrow y^2 \equiv 1 \pmod 3$$
$$y \equiv 2 \pmod 3 \Rightarrow y^2 \equiv 1 \pmod 3$$
We can see that $x^2+y^2 \equiv 0 \pmod 3$,only if $x \equiv 0 \pmod 3 \text{ AND } y \equiv 0 \pmod 3$