$\textit{Why}$ the cases in 4 $\nmid n^2 - 3?$ (bases cases in modular induction)

This question has already been answered here. My question is, when we suppose the hypothesis is not true (proof by contradiction), namely that $4 \mid (n^2 - 3)$, we get $n^2 - 3 = 4k$ for some integer $k$ and then we have two cases. But where does the two cases come from? In addition, why does putting them into two cases work to prove the statment? My thought process would be to try to prove this statement by contradiction and somehow figure out a way to produce a contradiction similar to how $\sqrt{2}$ is proved by contradiction. Any help is great!

Let me know if I need to clarify more!

Solution 1:

But why the cases, and where do the two cases come from? In addition, why does putting them into two cases work to prove the statment?

Since these specific questions were not addressed in prior answers, we explicitly address them here. In this type of induction (by modular cases) there are generally multiple base cases corresponding to each possible remainder $\bmod n$. Let's bring to the fore the logical essence of matter.

Congruence $\!\bmod 4\,$ is an equivalence relation on $\,\Bbb Z\,$ whose classes partition $\,\Bbb Z\,$ into $\,4\,$ cosets (arithmetic progressions) $\,r_i + 4\Bbb Z$, $\,r_i \in \{0,1,2,3\}.\,$ The naturals in each coset have the same order structure as $\Bbb N,\,$ so we can use induction to prove that a statement is true for all elements in the coset. If we prove that for all $4$ cosets ($4$ case analyses) then that suffices as a proof that the statement is true for all naturals since, the union of the cosets $= \Bbb Z \supset \Bbb N$.

Sometimes we can give a single proof that works uniformly for all cosets, but generally we may need a (brute force) case analysis, examining each of the $\,n\,$ possible cosets, e.g. when $\,n = 2\,$ this amounts to a proof by parity using two base cases even & odd. A prototypical example, is the Parity Root Test, which shows that an integer coefficient polynomial has no integer roots if it has no roots $\bmod 2$, essentially performing a parity analysis on possible roots, i.e. if it has no even root and no odd root then it has no integer root, e.g. if $\,n\,$ is odd then $\,x^2+x+n\,$ has no integer roots because it is always odd $\,f(0)\equiv 1\equiv f(1)\pmod{\!2}.\,$ The same idea works $\!\bmod n,\,$ i.e. an integer coef polynomial $\,f(x)\,$ has no integer roots if it has no roots $\!\bmod n\,$ i.e. if $\,f(0),f(1),\ldots,f(n-1)\,$ are all $\not\equiv 0.\,$ The OP follows from the special case $\,f(x) = x^2-3,\ n = 4\,$ (the common proof you linked is essentially just a slight optimization of this modular root test).

As in the proof of this root test, in practice said induction in each coset is not usually explicitly done because typically we employ other results that help to simplify the matter - so the induction in the cosets actually ends up being hidden somewhere down the line in another theorem or lemma. For example, in the proof of the root test it boils down to $\,n\equiv (n\bmod 2)\in \{0,1\}\,$ by the Division Algorithm (computing the least element (remainder) in each coset is essentially induction in that coset). [Down the line it also implicitly uses (structural) induction in the proof of the Polynomial Congruence Rule (to essentially decompose the polynomial into compositions of sums and products) but this is not the modular case induction that we are concerned with here].