Mersenne primes are those primes that can be made from the expression 2ⁿ -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?

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

Regards,
Olof.

Is it true that if n is a Germain prime and

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

aⁿ - 1

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

aⁿ - 1 = a^pq - 1 = (a^p - 1)(a^{pq - p} + a^{pq - 2p} + a^{pq - 3p} + ... + a^p + 1)

So the expression has a proper factor a^p - 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 aⁿ - 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:

2^{12k - 1} = 1 (mod 24k - 1)

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

Well firstly, by Fermat's Little Theorem:

2^{24k - 2} = 1 (mod 24k - 1)

Therefore:

(2^{12k - 1} - 1)(2^{12k - 1} + 1) = 0 (mod 24k - 1)

By unique prime factorisation, we deduce:

2^{12k - 1} = 1 or -1 (mod 24k - 1)

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

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 2ⁿ -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 2ⁿ -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 x² = 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 x² = 2 (mod 2n+1). Raise both sides to the power of n and we get:

x²ⁿ = 2ⁿ (mod 2n+1)

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