To prove the necessity: Since $p$ is a prime, if the indeterminate equation (1) has a solution $x_{0}, y_{0}$, it must satisfy
$$\left(x_{0}, y_{0}\right)=\left(x_{0} y_{0}, p\right)=1,$$

Thus, there must be a $y_{0}^{-1}$ such that $y_{0}^{-1} y_{0} \equiv 1(\bmod p)$. This leads to
$$\left(x_{0} y_{0}^{-1}\right)^{2}+1+k p=\left(y_{0}^{-1}\right)^{2} p$$

If $p>2$, from the above equation we get
$$\left(x_{0} y_{0}^{-1}\right)^{2} \equiv-1(\bmod p)$$

That is, $\left(\frac{-1}{p}\right)=1$, which implies $p=4 k+1$ (see Chapter 4, §5, Corollary 3). This proves the necessity.

To prove the sufficiency: When $p=2$, we have $2=1^{2}+1^{2}$, so (1) has a solution. When $p>2$, from $\left(\frac{-1}{p}\right)=1$ (i.e., $p=4 k+1$), there must be an $x$ such that
$$x^{2}+1 \equiv 0(\bmod p), \quad 0 \leqslant x < p$$

Let $m_{0}$ be the smallest $m$ for which
$$x^{2}+y^{2}=m p$$

holds. If we can prove $m_{0}=1$, then we have proven the sufficiency. At this point, similar to the proof of Theorem 2 in §1, we can show that $(x, y)=1$ (left to the reader). We will use proof by contradiction to show that $m_{0}=1$. If $m_{0}>1$, take
$$\left\{\begin{array}{ll} u \equiv x\left(\bmod m_{0}\right), & |u| \leqslant m_{0} / 2, \\ v \equiv y\left(\bmod m_{0}\right), & |v| \leqslant m_{0} / 2 \end{array}\right.$$

From this and $(x, y)=1$, we immediately get
$$0<u^{2}+v^{2} \leqslant m_{0}^{2} / 2, \quad u^{2}+v^{2} \equiv x^{2}+y^{2}\left(\bmod m_{0}\right)$$

Using equation (3) with $m=m_{0}$, we get
$$\left(u^{2}+v^{2}\right)\left(x^{2}+y^{2}\right)=m_{1} m_{0}^{2} p, \quad 1 \leqslant m_{1}<m_{0} .$$

Using the well-known identity
$$\left(a_{1}^{2}+a_{2}^{2}\right)\left(b_{1}^{2}+b_{2}^{2}\right)=\left(a_{1} b_{1}+a_{2} b_{2}\right)^{2}+\left(a_{1} b_{2}-a_{2} b_{1}\right)^{2},$$

the above equation becomes
$$(u x+v y)^{2}+(u y-w x)^{2}=m_{1} m_{0}^{2} p .$$

From equation (4) and equation (3) with $m=m_{0}$, we have
$$\begin{array}{c} u x+v y \equiv x^{2}+y^{2} \equiv 0\left(\bmod m_{0}\right) \\ u y-v x \equiv 0\left(\bmod m_{0}\right) \end{array}$$

Thus, we have
$$\left(\frac{u x+v y}{m_{0}}\right)^{2}+\left(\frac{u y-v x}{m_{0}}\right)^{2}=m_{1} p, \quad 1 \leqslant m_{1}<m_{0}$$

This contradicts the minimality of $m_{0}$. Therefore, $m_{0}=1$. Proof complete.