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

Unified test for Sophie Germain primes

Expand Messages
  • j_chrtn
    Hi, I ve read the new Mersenne Divisors conj. thread, and I propose the following test for Sophie Germain primes 3 that does not require 2 different cases
    Message 1 of 5 , Jan 19, 2010
    • 0 Attachment
      Hi,

      I've read the "new Mersenne Divisors conj." thread, and I propose the following test for Sophie Germain primes > 3 that does not require 2 different cases p = 1 (mod 4) and p = 3 (mod 4).

      The test is:

      Let p be a prime > 3; p is a Sophie Germain prime <=> 2p+1 divides 4^p-3^p.

      Proof:

      => : Suppose q = 2p+1 is prime.

      Then (3/q)(q/3) = (-1)^((q-1)/2) = (-1)^p = -1. So (3/q) = -(q/3).
      But since p > 3 and q are both primes, q = 2 (mod 3) and (q/3) = -1.
      This show that 3 is a square mod q. Let a be such that a^2 = 3 (mod q).

      Finally, 4^p-3^p = 2^(2p)-a^(2p) = 2^(q-1)-a^(q-1) = 1-1 = 0 (mod q).
      So q = 2p+1 divides 4^p-3^p.


      <= : Let q = 2p+1 be a factor of 4^p-3^p. Suppose q be composite.

      Let u be the smallest prime factor of q (which implies u^2 <= q and u^2 < q+1).
      Then 4^p-3^p = 0 (mod u) and so (3/4)^p = 1 (mod u) (since 4 != 0 (mod u))

      Let O be the order of 3/4 (mod u).
      O divides p and O divides u-1 => u > p => u^2 > p^2.
      But q+1 = 2p+2 > u^2 so 2p+2 > p^2 which is impossible since p > 3.

      Mike should appreciate this particular use of our favourite (n+1)^p-n^p numbers ;-)

      Best regards,

      J-L
    • djbroadhurst
      ... Looks good. But you can speed it up by a factor of 2 by working with Mod(3/4,2*p+1) JL(p)=Mod(3/4,2*p+1)^p==1;
      Message 2 of 5 , Jan 19, 2010
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "j_chrtn" <j_chrtn@...> wrote:

        > Mike should appreciate this particular
        > use of our favourite (n+1)^p-n^p numbers ;-)

        Looks good. But you can speed it up by a factor
        of 2 by working with Mod(3/4,2*p+1)

        JL(p)=Mod(3/4,2*p+1)^p==1;
        forprime(p=5,10^7,if(JL(p)!=isprime(2*p+1),print([p,fail])));

        David
      • j_chrtn
        ... Right. 3/4 appears in the proof. Do you know if this test is something well known? I ask this because I ve never seen it before. J-L
        Message 3 of 5 , Jan 19, 2010
        • 0 Attachment
          > --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
          >
          > Looks good. But you can speed it up by a factor
          > of 2 by working with Mod(3/4,2*p+1)
          >

          Right. 3/4 appears in the proof.

          Do you know if this test is something well known?
          I ask this because I've never seen it before.

          J-L
        • djbroadhurst
          ... It s not well known because it s quite unnecessary. The foolproof unified Sophie test that works in *all* cases is much simpler. If p is prime, then q =
          Message 4 of 5 , Jan 20, 2010
          • 0 Attachment
            --- In primenumbers@yahoogroups.com,
            "j_chrtn" <j_chrtn@...> wrote:

            > Do you know if this test is something well known?

            It's not well known because it's quite unnecessary.
            The foolproof "unified Sophie" test that works in
            *all* cases is much simpler.

            If p is prime, then q = 2*p+1 is prime iff 4^p = 1 mod q.

            Proof: Simply use base 2 in Pocklington's theorem and
            observe that 2^2-1 is coprime to 2*p+1 for every prime p.

            Note that this test detects *every* Sophie pair,
            including [2,5] and [3,7]. Here is a sanity check:

            Pock(p)=Mod(4,2*p+1)^p==1;
            forprime(p=2,10^6,if(Pock(p)!=isprime(2*p+1),print(fail)));
            \\ The rest is silence, signifying consent

            Entia non sunt multiplicanda praeter necessitatem :-)
            http://en.wikisource.org/wiki/The_Myth_of_Occam's_Razor

            David [second attempt at a reply; apologies if it appears twice]
          • j_chrtn
            ... Unnecessary but at least correct. ... This is closed to Henri Lifchitz s test 3^p = 1 (mod q) but your s also handles p=2 and p=3. ... There Is More Than
            Message 5 of 5 , Jan 20, 2010
            • 0 Attachment
              >--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
              >
              >
              > It's not well known because it's quite unnecessary.
              >
              Unnecessary but at least correct.

              >
              > If p is prime, then q = 2*p+1 is prime iff 4^p = 1 mod q.
              >
              This is closed to Henri Lifchitz's test 3^p = 1 (mod q) but your's also handles p=2 and p=3.

              >
              > Entia non sunt multiplicanda praeter necessitatem :-)
              >

              "There Is More Than One Way To Do It."
              http://en.wikipedia.org/wiki/There's_more_than_one_way_to_do_it

              However, some ways are more efficient than others ;-)

              Regards,
              J-L
            Your message has been successfully submitted and would be delivered to recipients shortly.