Feeds:
Posts

## 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.

## A conjecture about network flow

G(s,t) denotes a network with source s and destination t.
G'(f) denotes the residual network of G(s,t) with flow f.
Let S*(f) be the set of vertices reachable from s in G'(f).
Let T*(f) be the set of vertices from which t is reachable in G'(f).
Then for any maximum flows f1 and f2S*(f1) =S*(f2) and T*(f1) =T*(f2).
And for any minimum cut (S,T), S*(f) is a subset of S and T*(f) is a subset of T.
Stronger conjecture:
For any flows f1 and f2 with same flow volume, S*(f1) =S*(f2) and T*(f1) =T*(f2).

A.容易看出G(f1-f2)中除s,t点外，其他点的出度入度同时大于0，
因为容易证明网络G(f1-f2)仍然对所有的点出入平衡。
B.又G(f1-f2)中的所有边都是f2的剩余网络Nr(f2)中的边，
所以stG(f1-f2)中无路径。
C.有G(f1-f2)中的所有边反向后都是f1的剩余网络Nr(f1)中的边，
所以t到s在G(f1-f2)中无路径。

Nr(f2)中原来有圈V1–V2–V3…Vn—>V1，增环流后有圈Vn–>Vn-1–>…V1—>Vn