Prime Numbers in the Diophantine equation q=(n^2+1)/p and p is Prime

[AntonVrba]

Investigating the Diophantine equation q = \frac{n^2+1}{p}} where {p} is a prime number, n,q are integers per definition

The prime numbers can be sorted into two groups

Group 1 has no solution and

Group 2 has the solution n = \{ a\times p - b{ \ },{ \ } a\times p + b \} {\ \ \ }\forall { \ \ }a>=0

The table below list results for the first view primes, there is no particular pattern which divides the primes into either group 1 or 2 nor a pattern for the value b and there seem to be an equal number group1 and group2 primes.
\begin{array}{cc,c,c}
{No.&Group\ 1&Group\ 2&b\\
1&{}&2&1\\
2&3&{}&{}\\
3&{}&5&2\\
4&7&{}&{}\\
5&11&{}&{}\\
6&{}&13&5\\
7&{}&17&4\\
8&19&{}&{}\\
9&23&{}&{}\\
10&{}&29&12\\
11&31&{}&{}\\
12&{}&37&6\\
13&{}&41&9\\
14&43&{}&{}\\
15&47&{}&{}\\
16&{}&53&23
\end{array}


example the for the 10th prime =29 q= (12^2+1)/29 = 5
and 29-12 = 17 q =(17^2+1)/29 =10
and 29+12 = 41 q =(41^2+1)/29 =58
and 2x29-12=46 q =(46^2+1)/29 =73
and 2x29+12=46 q =(70^2+1)/29 =169 which is a perfect square.
etc

A further interesting property is that for many (if not all)p_2 a prime in Group 2 a infinite number of a exists, such that \frac{(a\times p_2 \pm b)^2+1}{p_2}} is a perfect square. (read \pm as plus or minus b)
47318x29-12=1372210 q =(1372210^2+1)/29 =64929664969 = 254813^2

My question is - are there other properties that can be attributed to the Group1 or Group2 primes?

[Hurkyl]

Have you tried looking at your answers modulo some number? mod 2, mod 3, mod 4, or mod 8 often tell you something interesting about integer equations involving squares.

[AntonVrba]

Have you tried looking at your answers modulo some number? mod 2, mod 3, mod 4, or mod 8 often tell you something interesting about integer equations involving squares.
Interesting - all Group2 primes have remainder 1 when divided by 4

[shmoe]

Interesting - all Group2 primes have remainder 1 when divided by 4

Except 2.

You can say more and assert that every prime congruent to 1 mod 4 is in your group 2. You're just asking for what primes p does the equation n^2\equiv -1\ \mod\ p have a solution n, or when is -1 a square mod p. Look up the Legendre symbol, quadratic residues,Euler's criteria etc.

[ramsey2879]

Let a(n) = n^2 +1. Let p, q be primes from group 2 and P, Q be the unique numbers less than p/2 or q/2, respectively, such that a(P) equals 0 mod p and a(Q) equals 0 mod q.
A. If a(n) equals 0 mod p then n equals either +/- P mod p.
B. If a(P) is composite, i.e. = p*d*q (q is prime, d >/= 1) then all other prime factors of a(P) correspond to still smaller numbers Q such that a(Q) equals 0 mod q. An example is a(12) equals 0 mod 29. Since 12 < 29/2, then 12 is the lowest positive number n such that a(n) = 0 mod 29. The other prime factor of a(12) is 5 which corresponds to q = 5 where Q=2 and 12= 2 mod 5.
C. The P, Q numbers etc and the corrresponding primes (->1 means that all prime factors were previously listed) for n < 16 are
1->2
2->5
3->1
4->17
5->13
6->37
7->1
8->1
9->41
10->101
11->61
12->29
13->1
14->197
15->113

[AntonVrba]

Ramsey - 100% correct - this helps me further