Welcome to NRICH.

 
Mersenne primes and Germain primes
By Sudha Srinivasan (M647) on Tuesday, March 27, 2001 - 10:10 am:

Mersenne primes are those primes that can be made from the expression 2n-1. I can generate prime numbers when I give prime values for n . But this does not work when n=11, 23...
I would like to know why?

By Olof Sisask (P3033) on Tuesday, March 27, 2001 - 06:42 pm:

Perhaps you should look at it like this instead: if 2n-1 is prime then n is prime. You cannot infer from this that if n is prime then so is 2n-1. If that makes sense.

Regards,
Olof.

By Anonymous on Wednesday, March 28, 2001 - 04:29 pm:

Is it true that if n is a Germain prime and n º-1 mod 12 then 2n-1 is divisible by 2n+1?

By Michael Doré (Md285) on Wednesday, March 28, 2001 - 06:29 pm:

Olof is right about the first question. In general, a statement and its converse are not logically equivalent. (For example, x = 3 implies x2 = 9 but x2 = 9 does not imply x = 3.) Specifically in this case it is true that for integers a,n >1 then if:

an - 1

is prime then n is prime. To prove this, assume n is composite, so n = pq where p,q are integers >1.

an - 1 = apq - 1 = (ap - 1)(apq - p + apq - 2p + apq - 3p + ... + ap + 1)

So the expression has a proper factor ap - 1 which is a contradiction, so we're done.

However it is not true that if a,n are integers >1 with n prime then an - 1 is prime.

As for the last question, I think I remember someone at college saying that a Germain prime n is one such that n,2n+1 are prime. So if n = 12k-1, 2n+1 = 24k-1. So we want to investigate whether:

212k - 1 = 1 (mod 24k - 1)

where 12k - 1 and 24k - 1 are primes.

Well firstly, by Fermat's Little Theorem:

224k - 2 = 1 (mod 24k - 1)

Therefore:

(212k - 1 - 1)(212k - 1 + 1) = 0 (mod 24k - 1)

By unique prime factorisation, we deduce:

212k - 1 = 1 or -1 (mod 24k - 1)

We want to show that 212k - 1 = 1, so we need some way of eliminating the second possibility. I can't yet see it...

By Michael Doré (Md285) on Wednesday, March 28, 2001 - 08:50 pm:

OK, I see how to do it now. We want to show that if n and 2n+1 are prime with n+1 a multiple of 12 then 2n-1 is divisible by 2n+1. In fact we don't need all these conditions. We will drop the condition that n is prime and only insist n+1 is a multiple of 4 not 12.

So, we're going to show that if n+1 is a multiple of 4 with 2n+1 prime then 2n-1 is divisible by 2n+1. I need to assume a result from Gauss:

Gauss' Lemma

Let p be an odd prime, and let a be natural number which isn't divisible by p. Let f(x) be the number in [0,p-1] satisfying f(x) = x (mod p). There exists an integer x such that x2 = a (mod p) if and only if the number of f(a),f(2a),...,f((p-1)/2 a) which exceed p/2 is even.

For a proof see the start of Andrew Smith's message of July 26 here.

Now n+1 is a multiple of 4, so 2n+1 = -1 (mod 8). 2n+1 is prime and it is easy to see with Gauss' Lemma that this implies that there exists x such that x2 = 2 (mod 2n+1). Raise both sides to the power of n and we get:

x2n = 2n (mod 2n+1)

But by Fermat's Little Theorem the left hand side = 1 (mod 2n+1) so 2n - 1 is a multiple of 2n+1 as desired.