2
$\begingroup$

What is the procedure to solving $x^2$ $mod$ $23 = 7^2$? According to WolframAlpha, there is no integer solution but I am completely confused as to what steps was taken to determine that.

Before asking the question, I did try to solve this using brute force by plugging in some arbitrary numbers to see whether the square of that number mod $23$ gave me a remainder of $49$ but the procedure was quite tedious. Hence the reason I turned to WolframAlpha.

Going back to the question, I want to know how WoflramAlpha determined that there was no integer solution to solving for $x$.

$\endgroup$
3

1 Answer 1

Reset to default
3
$\begingroup$

I'm not sure what WolframAlpha did, and it would be helpful if you posted a link to the result of your input. However, it should be fairly obvious that there is at least one solution to this equation, namely, if $x \equiv 7 \pmod{23}$, certainly $x^2 \equiv 7^2 \pmod{23}$.

It turns out you have the additional solution of $x \equiv -7 \equiv 16 \pmod{23}$, and that's it. In fact, whenever you're solving a quadratic equation modulo a prime, you will have at most two roots, sometimes one, and sometimes none.

$\endgroup$
4
  • $\begingroup$ Perhaps Alpha is interpreting mod 23 as an operator, so $7^2\pmod{23}$ is evaluated as 3, and then it's $x^2=3$ that has no integer solution. $\endgroup$
    – Gerry Myerson
    Nov 30, 2013 at 4:39
  • $\begingroup$ But W|A does give the correct solutions! wolframalpha.com/input/… $\endgroup$
    – tc1729
    Nov 30, 2013 at 4:44
  • $\begingroup$ I am actually trying to solve $x^2$ $mod$ $23 = 7^2$. $\endgroup$
    – user67527
    Dec 1, 2013 at 1:19
  • 1
    $\begingroup$ Well, you'll never get a remainder of $49$ because the remainder upon division by $23$ is always a number from $0$ to $22$. However, you can get a solution to $x^2 \mod{23} = 7^2 \mod{23}$, which is what I discuss above. $\endgroup$
    – Ben Grossmann
    Dec 1, 2013 at 3:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .