$p^2 - 2 q^2 = 5039$ for primes $p, q$ Are there primes $p$ and $q$ for which $p^2 - 2 q^2 = 5039$?
This is the least prime $r$ for which I don't know whether $p^2 - 2 q^2 = r$ has a solution in primes.   
The solutions of the Pell-type equation $x^2 - 2 y^2 = 5039$ are $x_n, y_n$ given by the recurrences
$x_{n+4} = 6 x_{n+2} - x_n$ with initial values $x_0 = 71, x_1 = 209, x_2 = 217, x_3 = 1183$ and
 $y_{n+4} = 6 y_{n+2} - y_n$ with initial values $y_{{0}}=1,y_{{1}}=139,y_{{2}}=145,y_{{3}}=835$.  Both $x_n$ and $y_n$ have lots of prime values. I haven't found any cases where they are both prime for the same $n$ (having tested up to $n=10000$).  There are some "near misses", e.g. neither $x_{179}$ nor $y_{179}$ is prime but they have no small factors. Thus there doesn't appear to be any   modular reason for solutions not to exist.
Heuristically, since $x_n$ and $y_n$ increase exponentially, each has probability $O(1/n)$ of being prime, so the probability of both being prime
is $O(1/n^2)$, and since $\sum_n 1/n^2 < \infty$, we might expect finitely 
many $n$ with both $x_n$ and $y_n$ prime.  So maybe there just happen to be none, but there's no way to actually prove that.  Still, I thought I'd put this to MSE in the hope that there's something clever that I'm missing.
EDIT: I might mention that in order for $p^2 - 2 q^2 = r$ to have prime solutions, where $r$ is prime, either $q=2$ or $3$ (so $r + 8$ or $r + 18$ is the square of a prime) or $r \equiv 23 \mod 24$.  Of the primes $\equiv 23 \mod 24$
less than $10000$, the only ones for which I haven't found prime solutions are 
$4079$, $5039$ and $7703$, but I can prove there are no prime solutions for $4079$ and $7703$ (all solutions to $x^2 - 2 y^2 = r$ in those cases have $x$ or $y$ divisible by $5$, $7$ or $11$).
EDIT: See OEIS sequence A308816.
Miracles do happen.  For $r = 96431$ the least primes $p$ and $q$ for which $p^2 - 2 q^2 = r$ have $685$ digits each.

COMMENT.- I do not handle powerful calculators but I want to suggest what seems to me a way to calculate solutions or impossibility of such with more comfort maybe (I am not sure of this!). 
The complementary formulas of the law of quadratic reciprocity allow to say that $2$ is a square module the prime $5039$. In effect, we have
$71^2=4968^2=2$ in $\mathbb  F_{5039}$.
Then we have in $\mathbb  F_{5039}$ the equations $$p ^ 2 - (71q) ^ 2 =0\\ p ^ 2 - (4968) ^ 2=0$$ 
Taking now, for example the equation
$$p+71q=5039t$$ we have the integer solutions
$$\begin{cases}q=5039n+2484p\\t=71n+35p\\n\in\mathbb Z\end{cases}$$
There are severe restrictions that could suggest impossibility. We must have $p$ and $q$ primes and in the zero of $\mathbb  F_{5039}$ i.e. $5039\mathbb Z$ the only $n\in\mathbb Z$ to be used at the end is $n=1$.
