Browse Groups

• ## Unified test for Sophie Germain primes

(5)
• NextPrevious
• 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
Jan 19, 2010 1 of 5
View Source
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
• ... 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;
Jan 19, 2010 1 of 5
View Source
"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
• ... 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
Jan 19, 2010 1 of 5
View Source
>
> 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
• ... 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 =
Jan 20, 2010 1 of 5
View Source
"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]
• ... 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
Jan 20, 2010 1 of 5
View Source
>
>
> 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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.