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

  • Thread starter AntonVrba
  • Start date
  • #1
92
0
Investigating the Diophantine equation [tex]q = \frac{n^2+1}{p}}[/tex] where [tex]{p}[/tex] is a prime number, [tex]n,q[/tex] are integers per definition

The prime numbers can be sorted into two groups

Group 1 has no solution and

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

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 [tex]b[/tex] and there seem to be an equal number group1 and group2 primes.
[tex]\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}[/tex]


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

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

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

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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
92
0
Hurkyl said:
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
 
  • #4
shmoe
Science Advisor
Homework Helper
1,992
1
AntonVrba said:
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 [tex]n^2\equiv -1\ \mod\ p[/tex] have a solution n, or when is -1 a square mod p. Look up the Legendre symbol, quadratic residues,Euler's criteria etc.
 
  • #5
841
0
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:
  • #6
92
0
Ramsey - 100% correct - this helps me further
 

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

Replies
3
Views
4K
  • Last Post
Replies
5
Views
3K
  • Last Post
2
Replies
25
Views
11K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
15
Views
9K
Replies
39
Views
22K
  • Last Post
Replies
1
Views
3K
Replies
4
Views
2K
Replies
2
Views
7K
  • Last Post
Replies
4
Views
2K
Top