2
$\begingroup$

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?

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

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$

$\endgroup$
  • $\begingroup$ Very nice proof. $\endgroup$ – cr001 Dec 13 '15 at 19:57
  • $\begingroup$ 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. $\endgroup$ – user236182 Dec 13 '15 at 22:17
  • $\begingroup$ 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. $\endgroup$ – user236182 Dec 13 '15 at 22:50
  • $\begingroup$ @mark p does not need to be prime? $\endgroup$ – GerichoLonmiboni Dec 16 '15 at 3:15
  • $\begingroup$ @GerichoLonmiboni - Little Fermat is for primes - I've changed he answer. $\endgroup$ – Mark Bennet Dec 16 '15 at 7:07
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

According to the first supplement to quadratic reciprocity https://en.wikipedia.org/wiki/Quadratic_reciprocity#.C2.B11_and_the_first_supplement

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.