M_n, S_n, and the k in k*2^n+/1

[jasong]

While I don't understand why the fact that M_n divides S_n means M_n is prime, and I definitely don't understand Fast Fourier Transforms, I at least know how M_n and S_n are generated. Or at least I understand how they would be generated if we could store the rather extreme S_n number around where we're at now with the exponents.

Here's my question: In terms of solving whether or not k*2^n+/-1 is prime, as opposed to the simpler 2^n+/-1, if I were to solve the problem manually(yes, I know this is impossible in my lifetime if I were to use pen and paper), how does the k come into the equation?

I don't totally understand why modular arithmetic solves the problem. Well, I understand HOW it works, I just don't know WHY it works. If I need to know WHY modular arithmetic works to know how k enters the equation, then I apologize for wasting your time. Otherwise, I'd appreciate an explanation.

[alpertron]

For numbers of the form n=h*2^k+1 where h is not too high (h < 2^k) you can use Proth's theorem:

Start with a=3. Then perform the modular exponentiation a^(n-1)/2 (mod n). If the result is n-1, the number is prime. If the result is not 1 or n-1, the number is composite, otherwise, increment the variable a and perform the modular exponentiation again.

You can read the proof on Chris Caldwell's site about primes