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$
1
  • 2
    $\begingroup$ You only need to try $7$ numbers, don't you? $\endgroup$
    – cr001
    Dec 13, 2015 at 19:26

5 Answers 5

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

You must log in to answer this question.

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