Feeds:
Posts
Comments

Archive for the ‘Math’ Category

在网上闲逛时发现一个超帅的Pick定理的证明。
http://www.math.ethz.ch/~blatter/Pick.pdf
英文不太好,看了老半天才看懂:(
把整个平面想象成一块大铁板,假设在0时刻在平面的每个格点上都有一个单位热量的热源并均匀向各个方向扩散,那么最终整个平面会达到热量均衡,于是简单格点多边形的面积就等于其内部的热量总和。考虑多边形的任意一条边,整个平面是以这条边的中点中心对称的,于是穿过这条边进入多边形内部的热量之和为0,所以多边形内部的热量全部来自于内部格点和边界格点。前者正好为内部格点数,而后者中每个点的热量只有一部分流向多边形内部且其数量等于对应属于多边形角度除以2PI,再利用简单多边形内角和就可以得到Pick定理了。
Advertisements

Read Full Post »

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.

Read Full Post »