Let n be an arbitrary odd natural number. Prove that $n^2≡1$ (mod4)
I know that this is true, but I'm not exactly sure how to write the proof for it. I found out then when you square any odd number, it will end in a 1,5,or 9, which I think is important. But then I can't say that whenever you subtract 1 from those to get a number ending in 0,4,or 8, that every number ending in 0,4, and 8 is divisible by 4 since for example, 38 is not, and others.
Let $n$ be odd. Then there exists an integer $k \in \mathbb{Z}$ such that $n = 2k+1$
$$n^2-1 = (2k+1)^2 - 1$$
$$= 4k^2+4k+1-1$$
$$=4k(k+1)$$
Then if $k$ is odd, then $k+1$ is even, and thus $k(k+1)$ is even, and if $k$ is even, then you know $k(k+1)$ is also even.
So there exists $m \in \mathbb{Z}$ s.t $k(k+1) = m$. Thus we have $n^2-1 = 4k(k+1) = 4(m) = 4m$.
Hence we have $4|n^2 − 1$, that is, $n^2≡1$ (mod$4$)
Even more: if $n$ is odd then $n^2 \equiv 1 \bmod 8 $.
Simple proof:
If $n$ is odd, then $n = 2m+1$, so that $n^2 =(2m+1)^2 =4m^2+4m+1 =4m(m+1)+1 $. $m(m+1)$ is even since it is the product of two consecutive integers, so $4m(m+1)$ is divisible by $8$.
Another simple proof:
$n^2-1 =(n-1)(n+1) =2m(2m+2) =4m(m+1) $ is divisible by 8 as before.
