Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. May 17, 2005 #1
    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?
     
  2. jcsd
  3. May 17, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  4. May 17, 2005 #3
    Interesting - all Group2 primes have remainder 1 when divided by 4
     
  5. May 17, 2005 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. May 17, 2005 #5
    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
  7. May 18, 2005 #6
    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?



Similar Discussions: Prime Numbers in the Diophantine equation q=(n^2+1)/p and p is Prime
  1. *p>n? set prime (Replies: 4)

  2. 2^n-1 is prime (Replies: 5)

Loading...