TITLE: $a^2 \equiv b^2$ mod 4 equivalence classes.
QUESTION [0 upvotes]: so we have the relation $a^2 \equiv b^2$ mod 4. And to find equivalence classes we say b or a = 0 so $a^2=4k$ so $a=+-2\sqrt{k} $ so all even numbers. But when we get to a=1 then $a^2=4k+1$ after plugging stuff in i see it is all the odd numbers, but how to prove it? Thanks in advance. Keep in mind i do not want to check if it is true for odd/even i want to prove it form zero.

REPLY [1 votes]: whatever the parity of $a$ and $b$ we have $a-b=(a+b)-2b$ this shows that
$$
2|(a+b) \Leftarrow\Rightarrow 2|(a-b) \tag{1}
$$
keeping this in mind throughout, we notice that if
$$
a^2 \equiv b^2 \mod 4
$$
then
$$
4|(a^2-b^2)=(a+b)(a-b)
$$
from which
$$
2|(a-b)
$$
or
$$
a \equiv b \mod 2
$$
given (1), these steps are reversible
{"set_name": "stack_exchange", "score": 0, "question_id": 1540706}