$p^2 - 2 q^2 = 5039$ for primes $p, q$

Question

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.

Answer 1

$$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.

Answer 2

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.

Answer 3

All solutions of equation $a^2-2b^2=5039$ derives from modulo polynomial $a+bx\equiv(-x\pm71)(x+1)^j\pmod{x^2-2}$ where $j\equiv_6(0,2,4)$.

 u= Mod(x+1,x^2-2);
 for(j=0, 50,
  if(j%6==0||j%6==2||j%6==4,
   s= lift((-x+71)*u^j);
   a= abs(polcoeff(s, 0)); b= abs(polcoeff(s, 1));  
   if(a^2-2*b^2==5039, print("("a", "b")"));
   s= lift((-x-71)*u^j);
   a= abs(polcoeff(s, 0)); b= abs(polcoeff(s, 1));  
   if(a^2-2*b^2==5039, print("("a", "b")"));
  )
 )

output:

(71, 1)
(71, 1)
(209, 139)
(217, 145)
(1183, 835)
(1231, 869)
(6889, 4871)
(7169, 5069)
(40151, 28391)
(41783, 29545)
(234017, 165475)
(243529, 172201)
(1363951, 964459)
(1419391, 1003661)
(7949689, 5621279)
(8272817, 5849765)
(46334183, 32763215)
(48217511, 34094929)
(270055409, 190958011)
(281032249, 198719809)
(1573998271, 1112984851)
(1637975983, 1158223925)
(9173934217, 6486951095)
(9546823649, 6750623741)
(53469607031, 37808721719)
(55642965911, 39345518521)
(311643707969, 220365379219)
(324310971817, 229322487385)
(1816392640783, 1284383553595)
(1890222864991, 1336589405789)
(10586712136729, 7485935942351)
(11017026218129, 7790213947349)
(61703880179591, 43631232100511)
(64211934443783, 45404694278305)
(359636568940817, 254301456660715)
(374254580444569, 264637951722481)
(2096115533465311, 1482177507863779)
(2181315548223631, 1542423016056581)
(12217056631851049, 8638763590521959)
(12713638708897217, 8989900144617005)
(71206224257640983, 50350404035267975)
(74100516705159671, 52396977851645449)
(415020288913994849, 293463660621085891)
(431889461522060809, 305391966965255689)
(2418915509226328111, 1710431559691247371)
(2517236252427205183, 1779954823939888685)
(14098472766443973817, 9969125697526398335)
(14671528053041170289, 10374336976674076421)
(82171921089437514791, 58104322625467142639)
(85511932065819816551, 60466067036104569841)
(478933053770181114929, 338656810055276457499)
(498400064341877729017, 352422065239953342625)

We have three subproblems:

1) how prove that $7\mid a\wedge5\mid b\quad\forall\quad j\equiv_6(4_{-x+71},2_{-x-71})$

 u= Mod(x+1,x^2-2);
 for(i=0, 10,
  j= 6*i+4;
  s= lift((-x+71)*u^j);
  a= abs(polcoeff(s, 0)); b= abs(polcoeff(s, 1));  
  print("i="i"    j="j"    (a,b)=("a", "b")");
  print("a="factorint(a)"    b="factorint(b));
 )

output:

i=0    j=4    (a,b)=(1183, 835)
a=[7, 1; 13, 2]    b=[5, 1; 167, 1]
i=1    j=10    (a,b)=(234017, 165475)
a=[7, 1; 101, 1; 331, 1]    b=[5, 2; 6619, 1]
i=2    j=16    (a,b)=(46334183, 32763215)
a=[7, 1; 6619169, 1]    b=[5, 1; 1151, 1; 5693, 1]
i=3    j=22    (a,b)=(9173934217, 6486951095)
a=[7, 1; 19, 1; 1709, 1; 40361, 1]    b=[5, 1; 79, 1; 16422661, 1]
i=4    j=28    (a,b)=(1816392640783, 1284383553595)
a=[7, 2; 31, 1; 2137, 1; 559561, 1]    b=[5, 1; 29, 1; 67, 1; 137, 1; 431, 1; 2239, 1]
i=5    j=34    (a,b)=(359636568940817, 254301456660715)
a=[7, 1; 272771, 1; 188350861, 1]    b=[5, 1; 23, 1; 482971, 1; 4578571, 1]
i=6    j=40    (a,b)=(71206224257640983, 50350404035267975)
a=[7, 1; 449, 1; 1229, 1; 18434089589, 1]    b=[5, 2; 8489183, 1; 237244993, 1]
i=7    j=46    (a,b)=(14098472766443973817, 9969125697526398335)
a=[7, 1; 13, 2; 61, 1; 195369826177459, 1]    b=[5, 1; 61404647, 1; 32470264661, 1]
i=8    j=52    (a,b)=(2791426401531649174783, 1973836537706191602355)
a=[7, 1; 398775200218807024969, 1]    b=[5, 1; 19, 1; 89, 1; 6949, 1; 55819, 1; 60185685
1, 1]
i=9    j=58    (a,b)=(552688329030500092633217, 390809665340128410867955)
a=[7, 1; 31, 1; 479, 1; 211709627, 1; 25115650997, 1]    b=[5, 1; 29, 1; 1361, 1; 198033
7304416774739, 1]
i=10    j=64    (a,b)=(109429497721637486692202183, 77378339900807719160252735)
a=[7, 1; 1542192942443, 1; 10136724762883, 1]    b=[5, 1; 15475667980161543832050547, 1]

2) how prove that $11\mid a\vee 11\mid b\quad\forall\quad j\equiv_6(2_{-x+71},4_{-x-71})$

i=0    j=2    (a,b)=(209, 139)
a=[11, 1; 19, 1]    b=Mat([139, 1])
i=1    j=8    (a,b)=(40151, 28391)
a=Mat([40151, 1])    b=[11, 1; 29, 1; 89, 1]
i=2    j=14    (a,b)=(7949689, 5621279)
a=[11, 1; 647, 1; 1117, 1]    b=[467, 1; 12037, 1]
i=3    j=20    (a,b)=(1573998271, 1112984851)
a=Mat([1573998271, 1])    b=[11, 1; 101180441, 1]
i=4    j=26    (a,b)=(311643707969, 220365379219)
a=[11, 1; 9931, 1; 2852809, 1]    b=Mat([220365379219, 1])
i=5    j=32    (a,b)=(61703880179591, 43631232100511)
a=[13, 2; 365111717039, 1]    b=[11, 1; 19, 1; 37, 1; 5642212867, 1]
i=6    j=38    (a,b)=(12217056631851049, 8638763590521959)
a=[11, 1; 47, 1; 1913, 1; 55381, 1; 223049, 1]    b=[29, 1; 109, 1; 203339, 1; 13440221,
 1]
i=7    j=44    (a,b)=(2418915509226328111, 1710431559691247371)
a=[370611433, 1; 6526823767, 1]    b=[11, 2; 23561, 1; 745391, 1; 804901, 1]
i=8    j=50    (a,b)=(478933053770181114929, 338656810055276457499)
a=[11, 1; 157, 1; 1301, 1; 213159737607827, 1]    b=[349, 1; 970363352593915351, 1]
i=9    j=56    (a,b)=(94826325730986634427831, 67052337959385047337431)
a=[4177, 1; 513570433, 1; 44204291591, 1]    b=[11, 1; 23, 1; 131, 1; 1237, 1; 185959, 1
; 8794987099, 1]
i=10    j=62    (a,b)=(18775133561681583435595609, 13276024259148184096353839)
a=[11, 1; 19, 1; 67, 1; 1340793655765306251203, 1]    b=[137, 1; 173, 1; 560146165104771
279539, 1]

3) how prove that or $a$ is prime or $b$ is prime $\quad\not\forall\quad j\equiv_60$

 u= Mod(x+1,x^2-2);
 for(i=0, 100,
  j= 6*i;
  s= lift((-x+71)*u^j);
  a= abs(polcoeff(s, 0)); b= abs(polcoeff(s, 1));  
  if(a^2-2*b^2==5039,
   if(ispseudoprime(a)||ispseudoprime(b),
    print("j="j"    (a,b)=("a", "b")");
    if(isprime(a), print("a is prime\n"));
    if(isprime(b), print("b is prime\n"));
   )
  );
  s= lift((-x-71)*u^j);
  a= abs(polcoeff(s, 0)); b= abs(polcoeff(s, 1));  
  if(a^2-2*b^2==5039,
   if(ispseudoprime(a)||ispseudoprime(b),
    print("j="j"    (a,b)=("a", "b")");
    if(isprime(a), print("a is prime\n"));
    if(isprime(b), print("b is prime\n"));
   )
  )
 )

output:

j=0    (a,b)=(71, 1)
a is prime

j=0    (a,b)=(71, 1)
a is prime

j=6    (a,b)=(6889, 4871)
b is prime

j=24    (a,b)=(53469607031, 37808721719)
a is prime

j=30    (a,b)=(10586712136729, 7485935942351)
b is prime

j=30    (a,b)=(11017026218129, 7790213947349)
a is prime

j=132    (a,b)=(12167021834477455269744371985101433510589932022768591, 86033836460037960
15413218787600105026201217570636261)
a is prime

j=144    (a,b)=(476971589644817826289513860072248109567371008636324307111, 3372698454711
77935736771497169255527075346523437614023121)
a is prime

j=156    (a,b)=(17967905587119283390651264160875432770187076568655406836804111, 12705227
884371699847335383156986593692183041761112427922888379)
a is prime

j=168    (a,b)=(704377834367908593508292249928987734875750805440251131430663245591, 4980
70343199042956502047366529827721155272682801128638474640095239)
a is prime

j=180    (a,b)=(28735395811680665938967684109447224161181130402044414445733898077365871,
 20318993238518914843387201487205122282994587437391395557207361707490901)
a is prime

Answer 4

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$.