A valid proof by complete induction includes a uniform proof for all $k$ of the inferences below. As such it necessarily includes a proof ($\rm\color{#0a0}{vacuous}$) of the base case $\color{#c00}{\,P(0)}.\,$ See the schema below.
$$\begin{align}
\color{#0a0}{\bbox[3px,border:2px solid #0a0]{\phantom{:}}}\Rightarrow\,\color{#c00}{ P(0)}\\
P(0)\Rightarrow\, P(1)\\
P(0),P(1)\Rightarrow\, P(2)\\
\vdots\qquad\ \ \ \ \\
P(0),P(1),\ldots,P(k-1)\,\Rightarrow\,P(k)\\
\end{align}\qquad\qquad\qquad\qquad\ \ $$
While a valid inductive proof necessarily implies a proof of $\,\color{#c00}{P(0)},\,$ this may not occur explicitly. Rather, it may be a special case of a much more general implication derived in the proof. For example, in many such proofs the natural base case(s) is not a single number but rather a much larger set. Let's examine a simple induction where the base cases are all odd naturals.
If $n\ge\color{#c00}1$ is an integer then $\,n = 2^{\large i} j\, $ for some odd $j$ and some integer $i\ge 0.\,$ For if $n$ is odd then $n = 2^0 n,\,$ else $\,n = 2k\,$ for $\,1 \le k < n\,$ so induction $\,\Rightarrow k = 2^{\large i} j,\,$ so $\, n = 2k = 2^{\large i+1} j.\ \ $ QED
Here the base case $\color{#c00}{P(1)}$ is not explicitly proved. Instead it is a special case of the more general inference that $\,n\,$ odd $\,\Rightarrow\, n = 2^0 n.\,$ In such factorization (decomposition) problems the natural base cases are all irreducibles (and units) - not only the $\rm\color{#c00}{least}$ natural in the statement, e.g. in the proof of existence of prime factorizations of integers $\,n > 1,\,$ with base cases being all primes.
Remark $ $ The same holds for infinite descent - the contrapositive form of complete induction: $\, $ if given a counterexample $\,\lnot P(n)\,$ we can prove there exists a smaller one $\lnot P(k),\ k < n,\,$ then no counterexample exists, else iterating the proof would yield an infinite descending chain of counterexamples, contra $\,\Bbb N\,$ is well-ordered. Or, reformulated, if there is a counterexample then, by well order, we can choose a minimal counterexample (a.k.a. minimal criminal), contra the proof yields a smaller one.
Best Answer
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].