Math Is Fun Forum

Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

#1 2019-01-08 12:36:40

Member
Registered: 2013-01-22
Posts: 149

Sophie Germain primes and Mersenne number divisors

It is known from Wikipedia that:

“ If a Sophie Germain prime p is congruent to 3 (mod 4), then it’s matching safe prime 2p + 1 will be a divisor of the Mersenne number 2^p - 1.”

And:

“ Fermat's little theorem states that if p is a prime number, then for any integer a, the number a^p − a is an integer multiple of p.”

However if an integer, 2p + 1, where p is a prime number, is a divisor of the Mersenne number 2^p - 1, then 2p + 1 is a safe prime and p it’s matching Sophie Germain prime.

Divisors of the Mersenne number 2^p - 1 can’t be < p if p is a prime number. Therefore if 2p +1 is a divisor of 2^p - 1 it has no divisors as p is > the square root of 2p + 1. This will therefore make 2p + 1 a safe prime and p it’s matching Sophie Germain prime.

For example 11 which is prime, (11*2) + 1 = 23. 2^11 - 1 is divisible by 23 making 11 a Sophie Germain prime and 23 it’s matching safe prime.

"Time not important. Only life important." - The Fifth Element 1997

Offline