Prove that, for any $x$, $x^2 \equiv 3 \pmod{9}$ cannot be true

Question

While reading through another proof it stated that, for any natural number $x$, $x^2 \equiv 3 \pmod{9}$ can never be true. Why is that?

My apologies Everyone I misread the question instead of (mod 59) its actually (mod 9).

Answer 1

To the revised question:

If $x^2\equiv 3 \bmod 9$, this would mean that $x^2=9k+3$ for some $k$, giving $x^2=3(3k+1)$.

Thus we would have that $3$ divides $x^2$ and since $3$ is prime, $3$ divides $x$. But then $3^2=9$ divides $x^2$ and $x^2\equiv 0 \bmod 9$.

So we cannot have $x^2\equiv 3 \bmod 9$ as it leads to a contradiction.

Answer 2

In fact $11^2 - 3= 118 = 2\cdot 59$, so there is an issue with your question.

We knew there was a solution because by quadratic reciprocity $$\left(\frac{3}{59}\right ) = - \left( \frac{59}{3}\right)= -\left(\frac{-1}{3}\right) = 1$$

The $b$'s for which the equation $x^2 \equiv b \bmod{59}$ has a solution are the numbers congruent $\bmod{59}$ to one of $$0, 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53,57$$

Answer 3

By manual brute force:

Let us compute all the modulo $59$ residues of the squared integers. To ease the task, we can use that

$$(n+1)^2\bmod59=(n^2\bmod59)+2n+1.$$

Starting from $0$,

$$0,1,4,9,16,25,36,49,7,22,41,\color{red}3.$$

Answer 4

For your actual question, consider how many powers of $3$ can divide $n^2$. Can it be exactly $1$?