# How to approach this modulo proof?

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

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

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.

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.