Loading ...
Sorry, an error occurred while loading the content.

2^p+3 & 2^p-3 prime factors form

Expand Messages
  • Renaud LIFCHITZ
    Hello, If a prime q divides N=2^p+3 then : 2^p = -3 (mod q) so (2^p/q) = (-3/q) where (a/b) is the Legendre symbol it implies that (2/q) = (3/q).(-1/q) because
    Message 1 of 1 , May 3, 2002
    • 0 Attachment
      Hello,

      If a prime q divides N=2^p+3 then :
      2^p = -3 (mod q)
      so (2^p/q) = (-3/q) where (a/b) is the Legendre symbol
      it implies that (2/q) = (3/q).(-1/q) because p is odd, so q = 1, 5, 7, 11 (mod 24) (half of the primes)

      In the same way, if N=2^p-3, one can prove that q = +/- 1, +/- 5 (mod 24) (half of the primes)

      This speeds up a little bit the sieve...

      Good hunt,

      Renaud Lifchitz


      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.