How would I determine whether $a^2-3b^2=0 \pmod 7$? By trying all values of $a$ and $b$ it is clear that this is only true for $a=b=0$, but I need a way to show this algebraically so that I can generalize to different values for 3 and 7.
Multiplication and Subtraction in Modular Arithmetic
0
$\begingroup$
modular-arithmetic
-
1For definiteness use $a^2-3b^2$, but instead of $7$ pick a prime p>3. There are always the trivial solutions $a, b$ each a multiple of $p$. There are non-trivial solutions precisely if $3$ is a *quadratic residue* modulo $p$. The $p$ for which this is the case can be characterized by using the law of *Quadratic Reciprocity*, it is a not hard *Legendre Symbol* calculation. I have mentioned a number of key words to help you search. A large subject! – 2011-11-06
1 Answers
2
If $b \ne 0 \pmod 7$, then it has an inverse (because 7 is prime). So you get $(a/b)^2 = 3$ But $3$ is not a square mod $7$, so this equation has no solutions.
Conversely, suppose $3$ were a square mod $7$, so there would exist $c$ such that $c^2 = 3$. Then you could just take $a=c$ and $b=1$.
So the solvability of $a^2 - kb^2 = 0 \pmod p$ depends only on whether $k$ is a square mod $p$ (in the jargon: $k$ is a quadratic residue mod $p$).
This Wikipedia article on the Legendre symbol shows you how to find out whether $k$ is a quadratic residue mod $p$ without having to try all the possibilities.