# True or false: There is no square $6$ mod $7$.

True or false: There is no square $6$ mod $7$. If you find an example, then you are finish. If you cannot find an example, then prove that the below statement is not true.

$$x^2 \equiv 6\mod 7$$

When I try some examples I get $0,1,2,4 \mod 7$ so I would have to prove that there is no square $6 \mod 7$ but I am having a hard time. Any ideas?

• You only need to try $7$ numbers, don't you? – cr001 Dec 13 '15 at 19:26

Suppose $x^2\equiv 6$ then $x^4\equiv 36 \equiv 1$, and clearly $x$ is not a multiple of $7$, so little Fermat tells us that $x^6\equiv 1$ but then $x^6=x^2\cdot x^4\equiv 6\times 1\equiv 6$ is a contradiction.

This also shows by easy generalisation that the congruence $x^2\equiv -1 \bmod p$ cannot be solved for any prime $p\equiv 3 \bmod 4$

• Very nice proof. – cr001 Dec 13 '15 at 19:57
• If $x^2\equiv 6\pmod{7}$, then $x^6\equiv 6^3\equiv (-1)^3\equiv -1\pmod{7}$, contradicting Fermat's Little theorem. – user236182 Dec 13 '15 at 22:17
• You're using a slightly different method, here's the other one (in the above comment) generalized: If $x^2\equiv -1\pmod{p}$ with $p=4k+3$, then raising both sides by $(p-1)/2$ (which is odd) gives $x^{p-1}\equiv (-1)^{(p-1)/2}\equiv -1\pmod{p}$, contradicting Fermat's Little theorem. – user236182 Dec 13 '15 at 22:50
• @mark p does not need to be prime? – GerichoLonmiboni Dec 16 '15 at 3:15
• @GerichoLonmiboni - Little Fermat is for primes - I've changed he answer. – Mark Bennet Dec 16 '15 at 7:07

Hint: prove for $x=1,2,3,4,5,6$

Just try all integers from 0 to 6. Square them and check the remainder modulo 7. If there's no such number among them (with a remainder of 6), then there's no such number at all.

For any real $x$, we have

$$x \equiv 0,1,2,3,4,5,6 \pmod 7$$ and $$x^2 \equiv 0,1,2,4 \pmod 7$$

Hence the statement is true.

$x^2\equiv-1\pmod{7}$ has no solution since $7\not\equiv1\pmod{4}$