Quick primality test?
 

as can be easily proven, the number n>2 is a prime iff Mod[ 2[SUP]n[/SUP] , n ] = 2
maybe someone might be able to come up with a [B]practical[/B] implementation of this relation as a (quick) primality test for mersenne numbers ?
i.e. M[SUB]p[/SUB] is a prime iff Mod[ 2[SUP]Mp[/SUP] , M[SUB]p[/SUB] ] = 2

[QUOTE=guptadeva;474839]as can be easily proven[/QUOTE]

[url]http://oeis.org/A001567[/url]

:goodposting: THANKS for correcting !

You just have to remove 1 "f", reverse the order of your statement and you are as correct as Fermat.:smile:

ffunny very :wink:

[QUOTE=guptadeva;474839]maybe someone might be able to come up with a [B]practical[/B] implementation of this relation as a (quick) primality test for mersenne numbers ?
i.e. M[SUB]p[/SUB] is a prime iff Mod[ 2[SUP]Mp[/SUP] , M[SUB]p[/SUB] ] = 2[/QUOTE]

In this case Mp would be Mersenne prime for every p (!!!)
This is also the reason why we choose base=3 and not base=2 for Prp testing Mersenne numbers.

n is a prime iff Mod[ n, k ] > 0 for each 1 < k < n

that's it :smile:

The number 2n is prime iff n = 1

This amazingly simple test eliminates fully half the candidates.

I tried to generalize this to the case of 2n + m, but the formulation I came up with had a few counterexamples.

This problem may be trickier than I thought. Does anyone know of any active research being done in this area?

Except
 

Even k values don't help, at least for odd n . edit: @OP

[QUOTE=GP2;474853]The number 2n is prime iff n = 1[/QUOTE]

i think you are on to something !!!
and we could maybe extend your theorem with

[QUOTE]The number 3n is prime iff n = 1[/QUOTE]however i'm currently stuck as i have not been able to find any sufficient and necessary condition for the number 4n to be prime.

maybe we should just continue with the case 5n instead ?

[QUOTE=guptadeva;474855]i think you are on to something !!!
and we could maybe extend your theorem with

however i'm currently stuck as i have not been able to find any sufficient and necessary condition for the number 4n to be prime.

maybe we should just continue with the case 5n instead ?[/QUOTE]

I can't tell who is being serious in this discussion. But for every prime p, it is a theorem that[INDENT]p*n is prime if and only if n = 1[/INDENT]while for any composite c it is a theorem that[INDENT]c*n is composite for all n[/INDENT].