$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.
 A: Not a solution, too long for comment:
I am pretty close to finish checking the first billion prime values of $q$ with no solution so far. Currenttly I'm at $q=19,047,324,319$ 
To make things even worse, it seems that the solutions of the equation $p^2-2q^2=5039$ for prime $q$ are extremely rare, even if you allow $p$ to be composite. So far I have found only two such solutions:
$$p=209, \ q=139$$
$$p=6889, \ q=4871$$
Both 209 and 6889 are composite numbers (the latter also being a perfect square) so both have to be discarded. I'll let the code run over the weekend but this looks more and more like mission impossible.
A: $$p^2-2q^2=24k+23$$
Things to note are:


*

*mod 9 we have squares 0,1,4,7 the first of which can't happen with primes.

*$24k+23\equiv 6k+5\bmod 9$

*$p^2\equiv q^2\bmod 9\implies -(p^2)\equiv 6k+5\bmod 9$

*$p^2\equiv q^2+3\bmod 9 \implies -(q^2)+3\equiv 6k+5\bmod 9\implies -(q^2)\equiv 6k+2\bmod 9$

*$p^2\equiv q^2-3\bmod 9 \implies -(q^2)-3\equiv 6k+5\bmod 9\implies -(q^2)\equiv 6(k+1)+2\bmod 9$

*$p^2\equiv q^2+6\bmod 9 \implies -(q^2)+6\equiv 6k+5\bmod 9\implies -(q^2)\equiv 6(k-1)+5\bmod 9$

*$p^2\equiv q^2-6\bmod 9 \implies -(q^2)-6\equiv 6k+5\bmod 9\implies -(q^2)\equiv 6(k+1)+5\bmod 9$
using the fact that primes>3 squared are 1 mod 24
we get that the negatives are 5 mod 6. which then determines parity of the multiplier of 9. and we can knock out some values given a prime square type mod 9.
addendum My note on legendre points towards q is not 3 mod 4 unless $$5039^{q-1\over 2}\equiv 2q+1 \bmod 4q$$ showing 5039 is a power possibly,  but not a square when exponentiated. as the full number can't be 1 mod 4 without q being 2 mod 4 which is not 3 mod 4. with q being  1 mod 4, I have so far found no problem.
$p^2\equiv 2q^2 \bmod 5039$ a sometimes faulty PARIDroid gives 1301 residues mod 5039 that $p^2$ can be and be twice $q^2$ that means 2437 less residue classes p can be in to fit the bill once you account for the basic symmetry of squares. might be more. 
A: 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$.
