I'm currently trying to go through Artin's Algebra textbook via a Harvard Extension Course (available on YouTube). I wanted to make sure that my proof was solid for this question.
Prove that the square of an integer a is congruent to 0 or 1 modulo 4
I’ll prove this using induction.
(i) It’s true for a = 1: $ 1^{2} $ = 1. 1%4 = 1. Done.
(ii) Assume it’s true for all n. That is $n^{2} % 4 $ = 1 or 0.
(iii) Prove: If it’s true for n → it’s true for all n+ 1.
That is $(n+1)^{2} $ % 4 = 1 or 0.
Well, $(n+1)^{2} = n^{2} + 2n + 1. $ We know from our inductive hypothesis that $n^{2} $% 4 = 1 or 0. More specifically, if n is odd, then $n^{2} $ is also odd which means $n^{2}$%4 = 1. Conversely, if n is even, then $n^{2} $ is even and $n^{2} $ % 4 = 0. Further, 2n + 1 % 4 = 3 or 1. This is because it’s a monotonically increasing set that goes up by 2 at each element.
When n is odd, (2n+1) % 4 = 3, and when it’s even (2n + 1) % 4 = 1. Therefore, using the associativity of the cosets, $ n^{2} $ % 4, when n is odd = 1 + 3 = 0. And $n^{2} $ % 4, when n is even, = 0 + 1 = 1.
Thus, in every case $n^{2} $ % 4 = 0 or 1.
Thanks in advance,
$\endgroup$ 42 Answers
$\begingroup$Why not just$$(2n)^2 = 4n^2$$ $$(2n+1)^2 = 4n^2+4n+1 = 4(n^2+n)+1$$
$\endgroup$ $\begingroup$An alternative solution:
- $a\equiv0\pmod4 \implies a^2\equiv0^2\equiv0\pmod4$
- $a\equiv1\pmod4 \implies a^2\equiv1^2\equiv1\pmod4$
- $a\equiv2\pmod4 \implies a^2\equiv2^2\equiv0\pmod4$
- $a\equiv3\pmod4 \implies a^2\equiv3^2\equiv1\pmod4$
