(16) Find all pairs of positive integers $(a, b)$ such that: $a^{2}+b+1$ is a power of a prime, $a^{2}+b+1$ divides $b^{2}-a^{3}-1$, and $a^{2}+b+1$ does not divide $(a+b-1)^{2}$.
Given that $\frac{(b+1)(a+b-1)}{a^{2}+b+1}=\frac{b^{2}-a^{3}-1}{a^{2}+b+1}+a$ is an integer. Let $p^{k}=m=a^{2}+b+1$, where $k$ is a positive integer, then $p^{k} \mid (b+1)(a+b-1)$. If $p$ does not divide $b+1$ or $a+b-1$, then $p^{k}$ must divide the other, but in this case $p^{k}=a^{2}+b+1>\max \{b+1, a+b-1\}$, which is a contradiction! Therefore,
$$
\begin{array}{l}
b+1 \equiv a+b-1 \equiv 0(\bmod p) \\
a^{2}=p^{k}-(b+1) \equiv 0(\bmod p) .
\end{array}
$$

Since $p$ is a prime, we have
$$
\begin{array}{l}
a \equiv 0(\bmod p), \\
0 \equiv (b+1)-(a+b-1)+a \equiv 2(\bmod p) \Rightarrow p=2 .
\end{array}
$$

Let
$$
\left\{\begin{array}{l}
a^{2}+b+1=2^{k}, \\
b+1=2^{k_{1}} t_{1}, \\
a+b-1=2^{k_{2}} t_{2} \\
k_{1}+k_{2} \geqslant k \\
k>2 k_{2},
\end{array}\right.
$$

where $t_{1}$ and $t_{2}$ are odd numbers, and $k_{1}$ and $k_{2}$ are positive integers, the last inequality is derived from $m \times (a+b-1)^{2}$.

Since $2^{k}=a^{2}+b+1>b+1=2^{k_{1}} t_{1}$, we also have
$$
k>k_{1} .
$$
(i) When $k_{1} \geqslant 3$.

Because
$$
a^{2}=\dot{2}^{k}-2^{k_{1}} t_{1} \equiv 0\left(\bmod 2^{3}\right),
$$

we have $\quad a \equiv 0(\bmod 4), a+b-1 \equiv 0-1-1 \equiv 2(\bmod 4)$, which implies $k_{2}=1$. From $k_{1}+k_{2} \geqslant k>k_{1}$, we know $k=k_{1}+1$. At this point, $2^{k_{1}} t_{1}=$ $b+1k_{1}$, so $k \geqslant 3$.
From $k_{1}+k_{2} \geqslant k$ and $k>2 k_{2}$, we have
$$
2 k_{2}<k \leqslant k_{2}+2 \Rightarrow k_{2}<2,
$$

thus $k \leqslant 3$, hence
$$
k=3 \text {. }
$$

But
$$
\left\{\begin{array} { l } 
{ b + 1 = 2 ^ { 2 } t _ { 1 } , . } \\
{ a ^ { 2 } + b + 1 = 8 }
\end{array} \Rightarrow \left\{\begin{array}{l}
t_{1}=1, \\
a=2, \\
b=3,
\end{array}\right.\right.
$$

which is discarded.
(iii) When $k_{1}=1$. Then
$$
2 k_{2}<k \leqslant k_{2}+1 \Rightarrow k_{2}<1,
$$

which is a contradiction!
In summary, the required pairs $(a, b)$ are $\left(2^{x}, 2^{2 x}-1\right),(x=2,3,4, \cdots)$.