Show that if $n > 0$ is an integer, then $n^2$ is congruent to only $0,1,2$ or $4$ modulo $7$

Question

No solution please, I just need some guidance. I've tried various approaches so far yet no prevail.

• I've looked at small number cases and tried to identify something interesting. Couldn't find much though.
• I've thought about how n can only be odd or even, hence I took the form n = 2k or n = 2k+1 and squared each respectively. Which was indeed interesting because the odd took the form of $2k^2 + 4k + 1$ after being squared which seems interesting because n^2 can be congruent to 2,4 and 1 mod 7. But I can't really advance from there, or if this isn't relevant.

I'm hoping to get a sense of direction from you. Thanks.

Answer 1

You only have to consider $7$ numbers:

$$0,1,2,3,4=7-3, 5=7-2, 6=7-1$$

Square each of them and you are done.

Another way to phrase it is each number can be written as $7k+r$ where $r \in \{0,1,2,3,4,5,6\}$, just study $(7k+r)^2$ to convince yourselves that it suffices to study $7$ numbers.

Answer 2

Just do it.

All integers are either congruent to $0, \pm 1, \pm 2, \pm 3 \mod 7$. So any integer square with be congruent to $0, 1 , 4, 9\mod 7$ or in other words to $0,1,4,2 \mod 7$.

That's all there is to it.

===

Big picture: For any positive integer $n$, we know by division algorithm that for any integer $m$ there are unique integers $q$ and $r$ so that $m = q*n + r; 0\le r < n$. In other words $r$ is the remainder of dividing $m$ by $n$.

This means each integer will have a unique remainder $r$ and as there are exactly $n$ possible values for $r$, we can classify all the integers into $n$ different class types depending upon which of $n$ possible remainders it has. For example: in modulo $7$ we can separate the integers into $7$ classes. One class $\{...-11,-4, 3, 10, 17,....\}$ are all the integers that have $3$ as a remainder. $\{....,-10,-3, 4, 11, 18,...\}$ are all the integers that have $4$ as a remainder.

$a \equiv b \mod n$ means that $a$ and $b$ both belong to the same class. $a = qn + r$ and $b=pn + r$ for possibly different $p,q$ but both the same $r$. Now keep in mind, ALL integers belong to one of only $n$ possible classes.

Big result: Belonging to modulo classes is closed/maintained under addition, multiplication and raising to powers. That is: if $a \equiv b \mod n$ and $c \equiv d \mod n$. Then $a+c \equiv b+d \mod n$.

Proof: If $a$ and $b$ both have remainder $r$ and $c$ and $d$ both have remainder $s$ then $a+c$ and $d + d$ will both have whatever remainder $r+s$ is. So the integers $a+c$, $b+d$, and $r+s$ will all belong to the same class of integers.

Likewise $a = q*n + r; c = p*n + r$ and $c = v*n + s; d=w*n + s$ then $ac = qv*n^2 + rvn + sqn + rs$ and $bd = pwn^2 + rwn + spn + rs$. And if $rs = \gamma n + \beta$ then $ac$, $bc$, and $rs$ all belong to the class that has $\beta$ as remainders.

And this is IMPORTANT, there are only $n$ possible classes and every integer is in one.

So to solve the problem:

There are only $7$ possible classes that $n^2$ belong to. And which class each $n$ belongs to will be determined distinctly by what class $n$ is in.

So all you have to do is test each of the seven classes directly.

If $n$ is in the class of integers that has $0$ as a remainder, then $n^2$ will be in the class that has $0$ as a remainder.

If $n$ is in the class that has $1$ as a remainder, then $n^2$ will be in the class that has $1$ as a remainder.

If $n$ is in the class that has $5$ as a remainder. Then $n^2$ is in the same class that $25$ is in. And that is the class that has $4$ as a remainder.

There are only $7$ possibilities and we can check each one.

Now $-3$ is in the same class as $4$ so we could check $-3$ instead of $4$. THis is useful for checking the integers that are in the class that has $6$ as a remainder. They are in the same class that $-1$ is in. So their squares will be in the class of those that have $1$ as a remainder. That is easier than recognizing the will all be in the same class as $6*6 =36$ which is in the class that has $1$ as a remainder.

Answer 3

Note: $$n\equiv 0,1,2,3,4,5,6 (\mod 7)$$ $$\begin{align}n^2&\equiv 0^2,1^2,2^2,3^2,4^2,5^2,6^2 (\mod 7) \\ &\equiv 0,1,4,2,2,1,1 (\mod 7) \\ &\equiv 0,1,2,4 (\mod 7).\end{align}.$$ Also, note: $(2k+1)^2=\color{red}{4}k^2+4k+1$.