0
$\begingroup$

I'm really stuck on how I might begin approaching the following proof; I've tried a few things, which I've listed at the bottom, and my own inklings of what I might try, but I'm thoroughly stumped. Here's the question I'm trying to answer"

$$ \forall\: m \in \mathbb{Z}, m^2 \mod{7} = {0,1,2,4}$$

I've tried breaking this into cases, where m is either odd or even, and then trying to find the remainder for m alone and using the fact that $$ a \equiv b \mod{d} $$and $$c \equiv e \mod{d}$$

then $$ ac \equiv be \mod{d}$$

And just using this to square the results. I've also tried going back to the definition of modulo, but I can't solve the floor function I get:

$$ m = 2k - 7(floor(\frac{2k}{7}))$$

Can anyone help me out here? Really struggling to figure out how to prove this :S

$\endgroup$
  • $\begingroup$ Square each of 0, 1, 2, 3, 4, 5, 6 modulus 7 and see what you get. $\endgroup$ – William Elliot Mar 26 '18 at 12:58
0
$\begingroup$

Just do it. There are only seven cases to test.

If $m\equiv 0 \mod 7$ then $m^2 \equiv 0 \mod 7$. So all $m = 7k$ will be such that $m^2 = 49k^2\equiv 0 \mod 7$.

If $m \equiv 1 \mod 7$ then $m^2 \equiv 1 \mod 7$. So all $m = 7k+1$ will be such that $m^2 = (7k+1)^2 =49k^2 + 14k + 1\equiv 1 \mod 7$.

If $m \equiv 2 \mod 7$ then $m^2 \equiv 4 \mod 7$. So all $m = 7k + 2$ will be such that $(7k +2)^2 = 49k^2 + 28k + 4 \equiv 4 \mod 7$.

And if $m \equiv 3 \mod 7$ then $m^2 \equiv 9 \equiv 2 \mod 7$. So all $m = 7k +3$ will be such that $(7k + 3) = 49k^2 + 42k + 9 \equiv 2 \mod 7$.

Now we can continue with $m \equiv 4,5,6 \implies m^2 \equiv 16, 24, 36 \equiv 2, 3, 1 \mod 7$. But it'd be cleverer to notic that $m\equiv 4,5,6 \equiv -3,-2, -1$ and if $m = 7k + i\implies (7k+i)^2 = 49k + 14ik + i^2 \equiv K \mod 7$ then $m = 7k - i\implies 7k^2 - 14ik + i^2 \equiv K \mod 7$ as well.

So if $m \equiv 0\mod 7$ then $m^2 \equiv 0\mod 7$.

If $m \equiv \pm 1\mod 7$ then $m^2 \equiv 1\mod 7$.

If $m\equiv \pm 2\mod 7$ then $m^2 \equiv 4 \mod 7$

And if $m \equiv \pm 3\mod 7$ then $m^2 \equiv 2\mod 7$.

And those are the only seven options.

So this is true of ALL integers.

$\endgroup$
0
$\begingroup$

We could also use Euler's criterion:

If $p$ is prime, and $a \neq 0$ then $a$ satisfies $m^2 \equiv a$ mod $p$ for some $m$ if and only if $a^{(p-1)/2} \equiv 1 $ mod $p$.

So for our case, $0$ obviously works. Testing the remaining cases:

\begin{align} a &= 1,2,3,4,5,6 \\ a^3 &= 1, 8, 27, 64, 125, 216 \\ &\equiv 1, 1, -1, 1, -1,-1 \,\text{mod}\, 7 \end{align}

So $0,1,2,4$ are the only solutions.

$\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.