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

1. May 17, 2005

### 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?

2. May 17, 2005

### Hurkyl

Staff Emeritus
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.

3. May 17, 2005

### AntonVrba

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

4. May 17, 2005

### shmoe

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.

5. May 17, 2005

### 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

Last edited: May 17, 2005
6. May 18, 2005

### AntonVrba

Ramsey - 100% correct - this helps me further

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?