Prove that every odd integer is congruent to 1 modulo 4 or to 3 modulo 4.

So we know that 1 = 1 mod 4
5 = 1 mod 4, 9 = 1 mod 4..
inductively we can see that all numbers 4n+1 = 1 mod 4

we know that 3 = 3 mod 4, 7 = 3 mod 4, 11 = 3 mod 4, etc.
and we can see that all numbers 4n + 3 = 3 mod 4

Then we see that the set of odd numbers is the union of these two sets and we are done.

Claim:
Every integer can be written as either 4m, 4m + 1, 4m + 2, or 4m + 3, where m is an integer.

Proof:
Divide the given integer by 4. The remainder is either 0, 1, 2, or 3. Therefore we can write our integer as either
4m, 4m+1, 4m+2, or 4m + 3.

Claim:
If an integer n is odd, then n must be able to be written in the form 4m+1 or 4m + 3.

Proof:
Since we know n can be written in one of the forms 4m, 4m+1, 4m+2, or 4m + 3, all we need to show is that n cannot be written in the form 4m or 4m + 2. Since 4m = 2(2m) which is even, and 4m + 2 = 2(2m + 1) which is also even, and we know that n is odd, we know that n cannot be written in the form 4m or 4m+2. Therefore, n must be able to be written in the form 4m+1 or 4m + 3.

Claim:
If n is odd, n is congruent to 1 modulo 4 or 3 modulo 4.

Proof:
We showed above that n can be written in the form 4m+1 or 4m+3. Since 4m+1 is congruent to 1 mod 4 for all m, and since 4m+3 is congruent to 3 mod 4 for all m, we know that if n is odd, n is congruent to 1 mod 4 or 3 mod 4.

What is this, Chinese remainder theorem?