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}<br /> {No.&Group\ 1&Group\ 2&b\\<br /> 1&{}&2&1\\<br /> 2&3&{}&{}\\<br /> 3&{}&5&2\\<br /> 4&7&{}&{}\\<br /> 5&11&{}&{}\\<br /> 6&{}&13&5\\<br /> 7&{}&17&4\\<br /> 8&19&{}&{}\\<br /> 9&23&{}&{}\\<br /> 10&{}&29&12\\<br /> 11&31&{}&{}\\<br /> 12&{}&37&6\\<br /> 13&{}&41&9\\<br /> 14&43&{}&{}\\<br /> 15&47&{}&{}\\<br /> 16&{}&53&23<br /> \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]

unique identifiers for Group 2 primes

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