0

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.

Michael Hardy
  • 1
Aaron Dufour
  • 157
  • 1
    Maybe this line of thinking can help...Your equation is equivalent to $a^2=3b^2$ mod $7$. Thus we would need $3b^2$ to be a perfect square mod $7$. The perfect squares mod $7$ are $0,1,2,4$. However, $3$ times a perfect square is $0,3,6,5$. So only $0$'s match. – Bill Cook Nov 06 '11 at 19:57
  • @BillCook I tried that line of reasoning, but failed to see how I could generalize it to mod $n$. – Aaron Dufour Nov 06 '11 at 19:59
  • 1
    For 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! – André Nicolas Nov 06 '11 at 20:10

1 Answers1

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.

TonyK
  • 64,559