# Show that $n^2 \mod 5$ equals $0,1$, or $4$ for every integer $n$.

Show that $n^2 \mod 5$ equals $0,1$, or $4$ for every integer $n$. Using divison in to cases.

Proof: let integer $n$ be given.

Case $1$: Suppose there exists an integer $k$ such that $n = 2k$

Case $2$: Suppose there exists an integer $k$ such that $n = 2k+1$

Do I have the right idea of having two cases for all integers, one that covers even numbers and one that covers odd, or am I not on the right track?

• Even and odd were a good attempt. If $n = 2k$ then $n^2 = 4k^2 \equiv -k^2 \mod 5$. But what is $k^2 \mod 5$? Since we are looking of the modulo 5 after squaring, what if we look at the modulo 5 before squaring. There are only 5 possible $n \equiv i \mod 5$ so there are only 5 possible $n^2\equiv i^2 \mod 5$. Maybe those five $i^2$ onlly have three results. – fleablood Dec 14 '17 at 23:19

You should consider cases

$$n \equiv i \pmod 5$$

where $i \in \{0\,\ldots, 4\}$.

• okay but i am confused it said for every integer. So i should have a case for when the remainder is 0, 1, 2, 3,4 is that what you are saying? – user513683 Dec 14 '17 at 22:48
• yes, it suffices to consider those $5$ cases and they would cover all the integers. $(5k+r)^2=25k^2+10kr+r^2=5(5k^2+2kr)+r^2$ – Siong Thye Goh Dec 14 '17 at 23:52

This can be done explicitly very easily, as there are only $5$ (distinct) elements in $\mathbb{Z}_5$:

$$0^2 \equiv 0 \mod 5 \\ 1^2 \equiv 1 \mod 5 \\ 2^2 \equiv 4 \mod 5 \\ 3^2 \equiv 4 \mod 5 \\ 4^2 \equiv 1 \mod 5$$

Thus the only possibilities are $0, 1, 4$.

This works primarily because all numbers greater $4$ are equivalent to one of the above cases. More explicitly, every integer can be written as one of $5k, 5k+1,... 5k + 4$ for some $k \in \mathbb{Z}$, and

$$5k \equiv 0 \ \ \ \ \ \ \mod 5 \\ 5k + 1 \equiv 1 \mod 5 \\ 5k + 2 \equiv 2 \mod 5 \\ 5k + 3 \equiv 3 \mod 5 \\ 5k + 4 \equiv 4 \mod 5$$

• why do you have 3^2 and $62 as equal to 1? – user513683 Dec 14 '17 at 22:47 •$3^2 = 9 \equiv 4 \mod 5$. The$1$was a typo on my part, sorry – infinitylord Dec 14 '17 at 22:52 You want to know the outcome modulo$5$so if we are to break things into cases it makes sense to break things into cases of modulo$5$. If$n \equiv 0,1,2,3,4 \mod 5$then$n^2 \equiv 0^2, 1^2, 2^2, 3^2, 4^2 \mod 5$and ... the proof then practically writes itself. It writes itself even better when you realize$3 \equiv -2 \mod 5$and$4\equiv -1 \mod 5$so If$n \equiv 0,1,2,-2,-1 \mod 5$then$n^2 \equiv 0^2, 1^2, 2^2, (-2)^2, (-1)^2 \mod 5$. ====== P.S. If you want to do it the hard way we are trying to prove:$n^2 = 5k + r$and$0 \le r < 5$then$r= 0,1$or$4$(and never$2$or$3$). We are dealing with remainders when divided by$5$so if we let$n = 5j + m$then$n^2 = (5j + m)^2 = 25j^2 + 10jm + m^2 = 5(5j^2 + 2jm) + m^2 = 5k + r$so we must have$r = m^2 + 5(5j^2 + 2jm - 1)$. And$m$may be$0,1,2,3,4$so$m^2$may be$0,1,4,9,16$and$r$may be$0,1,2,3,4r = 0 + 5(5j^2 + 2jm - 1)$means$r= 0r = 1 + 5(5j^2 + 2jm - 1)$means$r = 1$.$r = 4 + 5(5j^2 + 2jm - 1)$means$r = 4r = 9 + 5(5j^2 + 2jm - 1)= 4 + 5(5j^2 + 2jm)$means$r =4$.$r = 16 + 5(5j^2 + 2jm - 1)= 1 + 5(5j^2 + 2jm+2)$means$r = 1\$.

But that was the hard way.