Feeds:
Posts

## A wonderful proof of Pick’s Area Theorem

http://www.math.ethz.ch/~blatter/Pick.pdf

## Mersenne prime, Lucas-Lehmer and GIMPS

Mersenne prime is a prime in the form of 2p-1 denoted as Mp, where p must be a prime.
It can be showed by quadratic residue that any divisor q of Mp satisfies that:
1) q = +/-1 (mod 8)
2) q = 1 (mod p)
A deterministic primality test called Lucas-Lehmer test is suitable for testing Mersenne prime.
Let L1=4, Ln+1=Ln*Ln-2, then Mp is prime if and only if Lp-1 = 0 (mod Mp).
Sufficiency Proof:
Let w=2+sqrt(3), v=2-sqrt(3), then Ln=w2n-1+v2n-1
Say R is a divisor of Mp such that R*R <= Mp.
Lp-1=w2p-2+v2p-2 = 0 (mod Mp)
==> w2p-1=-1 (mod Mp)
==> w2p-1=-1 (mod R)
==> w2p=1 (mod R)
So the number of elements in the group {a+b*sqrt(3) (mod R) | a+b*sqrt(3) is invertible}
is at least the order of w, 2p.
Then R*R-1 >= 2==> Mp >= 2p, a contradiction.
Necessity Proof:
Say Mp is prime.
It’s easy to show that 3 is not a quadratic residue of Mp by Legendre sign.
We just need prove w2p-1=-1 (mod Mp).
It can be proved that for any a+b*sqrt(3):
(a+b*sqrt(3))Mp = a-b*sqrt(3) (mod Mp)
(a+b*sqrt(3))2p = a*a- 3b*b (mod Mp)
Let z=(1+sqrt(3))/sqrt(2) (mod Mp).
z must exist, because 2 is a quadratic residue of Mp.
So z2 = w (mod Mp) ==> w2p-1 = z2p = (-2/2) = -1 (mod Mp).
Q.E.D.
The generalized  Lucas-Lehmer primality test is not necessary.
Namely, prime p may not pass the test for some specific parameters.
GIMPS is a organization searching Mersenne prime by collecting spare
CPU time of computers in the Internet.
Now, they are searching for one million digits Mersenne prime.