Let n be an integer. Prove that $n^2$ leaves a remainder of $0, 1$ or $4$ when divided by $5$. Let $n$ be an integer. Prove that $n^2$ leaves a remainder of $0, 1$ or $4$ when divided by $5$.
I was asked to solve the problem stated in the title. I'd like to see if I'm correct. I'm not completely confident in what I'm doing and might've done this incorrectly.
Can someone also explain why this is correct if it is, so I can gain a full understanding of this proof?
Using the division theorem:
Case 1: $n = 5k$
$n^2 = 25k^2$
$n^2 = 5(5k^2)$
$\text{Remainder} = 0$
Case 2: $n = 5k + 1$
$n^2 = (5k + 1)^2 = 25k^2 + 10k + 1$
$n^2 = 5(5k^2 + 2k) + 1$
$\text{Remainder} = 1$
Case 3: $n = 5k + 4$
$n^2 = 25k^2 + 40k + 16$
$n^2 = 5(5k^2 + 8k + 3) + 1$
$\text{Remainder} = 1$
When $n^2$ is divided by $5$ in the cases above, the remainder are $0$ and $1$. Thus $n^2$ leaves a remainder of $0, 1,$ or $4$, when divided by $5$.
 A: High-falutin approach:
$$a^2=a^{\frac {5-1}2}=\pm1\pmod 5$$, which follows easily from Fermat's little theorem when $(a,5)=1.$
Replacement of $5$ by any odd prime yields an important fact from number theory, related to quadratic residues.
A: You've got the right approach: split the problem into five cases by considering numbers of the form $n = 5k + r$ for each $r \in \{0,1,2,3,4\}$. You just forgot to consider two of the five possible cases.
In fact, we can save a bit of work by delaying the split into different cases for as long as we can.  That is, instead of picking a specific value for $r$ and then squaring, let's square $n = 5k + r$ first:
$$\begin{aligned}
n^2 &= (5k + r)^2 \\
&= 25k^2 + 10kr + r^2
\end{aligned}$$
Now, clearly, the first two terms $25k^2$ and $10kr$ are both evenly divisible by $5$ , so the remainder from dividing $25k^2 + 10kr + r^2$ by $5$ is the same as for dividing $r^2$ by $5$.
Now we just need to check what this remainder is for each $r \in \{0,1,2,3,4\}$:
$$\begin{aligned}
r = 0 &\implies r^2 = 0 \\
r = 1 &\implies r^2 = 1 \\
r = 2 &\implies r^2 = 4 \\
r = 3 &\implies r^2 = 9 = 5 + 4 \\
r = 4 &\implies r^2 = 16 = 15 + 1 \\
\end{aligned}$$
Thus, in each of these five cases, the remainder of dividing $r^2$ by $5$ is either $0$, $1$ or $4$.  And since every integer can be written as $5k + r$ for some integer $k$ and some $r \in \{0,1,2,3,4\}$, this in fact holds for all integers.
Ps. As hawaiian earring group has noted in their answer, another way of stating this result is that $0$, $1$ and $4$ are the quadratic residues modulo $5$, and further examining this concept leads to a lot of interesting and useful results in number theory.  But I assume you'll get to those later, probably after you've become more familiar with modular arithmetic in general.
