Prime solutions to a congruence modulo a semi-prime

Question

Let $p$ and $q$ be primes.

Besides $\{3,13\}$ and $\{13,61\}$, find other solutions $\{p,q\}$ to the congruence $$ 1+ p+q+p^2+q^2 \equiv 0 \pmod {pq}$$ or show that there are none.

Answer 1

I don't see that this can be finished. There is at least one more solution with ratio 5, namely $$ p = 22419767768701 \; , \; \; \; q = 107419560853453 $$

Given any natural numbers $x < y,$ we get a new solution to $$ x^2 - 5xy + y^2 + x + y + 1 = 0 $$ with $$ (x,y) \mapsto (y, 5y-x-1) $$ This is called Vieta Jumping on this site and in contests. In the simple program below, if we get two primes in a row printed out, that pair satisfies your question.

int main()
{
  mpz_class bound = 1000000000;
  bound *= bound;
  mpz_class x = 1;
   mpz_class y = 3;

while (y < bound)
{
mpz_class z = 5 * y - x - 1; 
  x = y;
  y = z;
  cout << y << "   =  " << mp_Factored(y) << endl;
}

   cout << endl << endl;
  return 0;
}

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

13   =   13
61   =   61
291   =   3 97
1393   =   7 199
6673   =   6673
31971   =   3 10657
153181   =   7 79 277
733933   =   127 5779
3516483   =   3 73 16057
16848481   =   13 1296037
80725921   =   43 1877347
386781123   =   3 1531 84211
1853179693   =   1853179693
8879117341   =   26947 329503
42542407011   =   3 13^3 6454621
203832917713   =   65437 3114949
976622181553   =   976622181553
4679277990051   =   3 7 199 1119712369
22419767768701   =   22419767768701
107419560853453   =   107419560853453

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY 
WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 4000000, primelimit = 500000
? factor(22419767768701)
%1 = 
[22419767768701 1]

? factor(107419560853453 )
%2 = 
[107419560853453 1]

? 

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Alright, I ran the sequence up pretty high, taking $x_0 = 1,$ then $x_1 = 3,$ then $x_2 = 13,$ $x_3 = 61,$ after which:

2 :  13   Prime  
3 :  61   Prime  
6 :  6673   Prime  
14 :  1853179693   Prime  
18 :  976622181553   Prime  
20 :  22419767768701   Prime  
21 :  107419560853453   Prime  
56 :  70293079987740435611353046917706109661   Prime  
300 :     Prime  
384 :     Prime  
447 :     Prime  
477 :     Prime  
878 :     Prime  
1000  milestone not really Prime 
2000  milestone not really Prime 
3000  milestone not really Prime 
4000  milestone not really Prime 
5000  milestone not really Prime 
5906 :     Prime  
6000  milestone not really Prime 

There is another aspect: there are no positive integer solutions to $$ x^2 - kxy+y^2 + x + y + 1 = 0$$ for integer $k \geq 3$ unless $k=5.$ Here is the diagram that shows the geometric part of the argument when $k=7.$

Here is the diagram for $k=5$ showing the "fundamental solution" between the diagonal lines at $(1,1)$