Prove no solution to $x^2\equiv3\bmod5$

Question

Show that there is no solution to the congruence $x^2\equiv3\bmod5$.

I'm not sure if the fact that the only numbers divisible by $5$ are those ending in $0$ or $5$ will help…

Answer 1

$x = 0 \pmod 5$ or $x = \pm 1 \pmod 5$ or $x = \pm 2 \pmod 5$

Squaring those gives $x^2 = 0 \pmod 5$ or $x^2 = 1 \pmod 5$ or $x^2 = 4 \pmod 5$

None is equivalent to $3 \pmod 5$

Answer 2

$x$ can be only of the following forms: $x = 5k,5k+1,5k+2,5k+3,5k+4$.

Hence $x^2$ can be of the forms: $25k^2, 25k^2+10k+1, 25k^2+10k+4, 25k^2+10k+9, 25k^2+10k+16$.

Take the remainders on division by $5$, and you get $0,1,4,4,1$. Hence, $2,3$ don't appear as remainders.

Answer 3

For any integer $x$ we have exactly one of the following:

• $x \equiv -2 \pmod 5$

• $x \equiv -1 \pmod 5$

• $x \equiv 0 \pmod 5$

• $x \equiv 1 \pmod 5$

• $x \equiv 2 \pmod 5$

Now check each case!

Answer 4

I think user "kccu" has the right idea. Because $5$ is so small, we can see what all the possible values of squares are.

Every number $n$ has a value modulo $5$. I.e. it's $\;(0 \mod 5)$ or $(1 \mod 5)$ etc. What we can do is check by brute force what the squares in $\mod 5$ look like:

$$0^2 \mod 5 = 0 \mod 5$$ $$1^2 \mod 5 = 1 \mod 5$$ $$2^2 \mod 5 = 4 \mod 5$$ $$3^2 \mod 5 = 4 \mod 5$$ $$4^2 \mod 5 = 1 \mod 5$$

Well for any $n$, $n^2$ has to be one of these things. $3 \mod 5$ isn't in the list, so we know that for any $n$, $$n^2 \not\equiv_5 3$$

Answer 5

Any number 3 mod 5 has either 3 or 8 as its last digit. Have you seen a square ending in 3 or 8? This is for intuition. Now square $10n+k$, where $k$ is the last digit of a number and see that it is the same as the last digit of $k^2$. List out numbers 0,1,2,...,9, square them and look at the last digit.