<s>[INST] On the Diophantine equation $m^2 - p^k = 4z$, where $z \in \mathbb{N}$ and $p$ is a prime satisfying $p \equiv k \equiv 1 \pmod 4$ The title says it all:

Do there always exist $m, p, k \in \mathbb{N}$ such that $m^2 - p^k = 4z$, $z \in \mathbb{N}$ and $p$ is prime satisfying $p \equiv k \equiv 1 \pmod 4$?

MY ATTEMPT FOR $z=1$
When $z = 1$, I get
$$m^2 - p^k = 4$$
$$p^k = m^2 - 4 = (m+2)(m-2)$$
Hence, we have the simultaneous equations $p^{k-x} = m+2$ and $p^x = m-2$ where $k \geq 2x + 1$.  Consequently, we have $p^{k-x} - p^x = 4$, which implies that 
$$p^x (p^{k-2x} - 1) = 4$$
where $k-2x$ is odd.  Since $(p-1) \mid (p^y - 1) \hspace{0.05in} \forall y \geq 1$, this last equation implies that $(p-1) \mid 4$.  Likewise, the congruence $p \equiv 1 \pmod 4$ implies that $4 \mid (p-1)$.  These two divisibility relations imply that $p-1=4$, or $p=5$.  Hence,
$$5^x (5^{k-2x} - 1) = 4.$$
Since $5$ does not divide $4$, $x=0$ and thus $5^k - 1 = 4$, which means that $k=1$.
Therefore, $p=5$, $k=1$, and $x=0$.  Consequently, $p^{k-x} = 5^{1-0} = 5 = m + 2$ and $p^x = 5^0 = 1 = m - 2$.  Either way, $m=3$.
CONCLUSION

Thus, for the equation $m^2 - p^k = 4$, I get the solution $m=3$, $p=5$, and $k=1$.

QUESTION

How does one treat the case for general $z \in \mathbb{N} \setminus \{1\}$?

For one, I cannot seem to wrap my head around $m^2 - p^k = 8$.
I could, of course, rewrite it as 
$$(m+3)(m-3) = m^2 - 9 = p^k - 1 = (p-1)\sigma(p^{k-1})$$
(where $\sigma$ is the classical sum-of-divisors function), but then I am no longer able to apply Euclid's Lemma.
UPDATE TO QUESTION (January 20, 2020)
The equation $m^2 - p^k = 4z$ (under the given constraints) does not have a solution when $z=4$.
Here is my additional question:

When is the equation $m^2 - p^k = 4z$, where $z \in \mathbb{N}$ and $p$ is a prime satisfying $p \equiv k \equiv 1 \pmod 4$, guaranteed to have a solution?

 [/INST] Consider the case $z = 4$.
We obtain
$$m^2 - p^k = 16$$
$$m^2 - 16 = p^k$$
$$(m + 4)(m - 4) = p^k$$
$$p^{k-x} = m + 4$$
$$p^x     = m - 4$$
$$p^{k-x} - p^x = 8$$
$$p^x (p^{k-2x} - 1) = 8$$
Since $p$ is prime and $p \equiv 1 \pmod 4$, then we have $\gcd(p^x, 8) = 1$, which implies that
$$p^{k-2x} - 1 = 8$$
$$p^{k-2x} = 9$$
$$p = 3 \land k - 2x = 2$$
contradicting $p \equiv 1 \pmod 4$.
Therefore, under the given constraints, the Diophantine equation
$$m^2 - p^k = 16$$
does not have any solutions.
</s>