Classic modular proofs

• Many "impossibility" number theory proofs come from restricting what values are possible modulo a small number. A famous example: for any integer n, n^2 == 0 or 1 (mod 4). The proof is by cases on parity. If n is even, n = 2k, so n^2 = 4k^2 == 0 (mod 4). If n is odd, n = 2k + 1, so n^2 = 4k(k+1) + 1 == 1 (mod 4). This is extremely useful because it means n^2 can never be congruent to 2 or 3 mod 4.
• Once you know the possible residues, you can prove impossibility statements cleanly. For instance, there is no integer n with n^2 == 2 (mod 4) because squares mod 4 are only 0 or 1. This style generalizes: learn what values an expression can take mod m, then use that to rule out equations or divisibility claims. It's a controlled version of proof by cases, and it becomes a major technique in contest math and in early number theory.

• 1Prove: n divisible by 3 iff sum of digits divisible by 3 (outline ok).
• 2Prove: For any integer n, n^2 == 0 or 1 (mod 4).
• 3Prove: There is no integer n such that n^2 == 2 (mod 4).

• 1Prove: If a == b (mod m) then a^2 == b^2 (mod m).
• 2Evaluate: 2^10 mod 7.

MCQ

For any integer n, n^2 mod 4 can be: