1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fleablood Dec 14 '17 at 23:19
2
$\begingroup$

You should consider cases

$$n \equiv i \pmod 5$$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user513683 Dec 14 '17 at 22:48
  • $\begingroup$ 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$ $\endgroup$ – Siong Thye Goh Dec 14 '17 at 23:52
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ why do you have 3^2 and $62 as equal to 1? $\endgroup$ – user513683 Dec 14 '17 at 22:47
  • $\begingroup$ $3^2 = 9 \equiv 4 \mod 5$. The $1$ was a typo on my part, sorry $\endgroup$ – infinitylord Dec 14 '17 at 22:52
0
$\begingroup$

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,4$

$r = 0 + 5(5j^2 + 2jm - 1)$ means $r= 0$

$r = 1 + 5(5j^2 + 2jm - 1)$ means $r = 1$.

$r = 4 + 5(5j^2 + 2jm - 1)$ means $r = 4$

$r = 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy