判断素性

medie2005

设$n=a*b+1,0

gxqcn

谢谢！学到了。 这里有更多的介绍：http://primes.utm.edu/prove/prove3_1.html

mathe

原帖由 gxqcn 于 2008-12-26 21:13 发表 谢谢！学到了。 这里有更多的介绍：http://primes.utm.edu/prove/prove3_1.html

Theorem 2: Suppose n-1 = FR, where F>R, gcd(F,R) is one and the factorization of F is known. If for every prime factor q of F there is an integer a>1 such that $a^n-1=1(mod n)$, and gcd(a(n-1)/q-1,n) = 1; then n is prime. (Notice that different a's can be used for each prime q.) Theorem 2 can be improved even more: if F

gxqcn

直接用11# 的结论证明楼主的数是不行的，因为前提条件不满足， 后来我找了些资料，才知道允许 F < R 的一些前提，这才是我们需要的，也就是 mathe 上面叙述的。

mathe

11#的结论也可以用，不过复杂一些。 用11#的结论，由于已经得出$4337107|10^785 + 3$,取$F=4337107*10^785$就可以了，只是F多了一个素因子

medie2005

呵呵,还是mathe懂我.

无心人

我有疑惑 every是任何的意思吧 就是说光一个似乎不行吧

medie2005

F=4337107*10^785. F的素因子只有2,5,4337107. 因此,只要对某个a,计算: gcd(a^(n-1)/2-1,n) gcd(a^(n-1)/5-1,n) gcd(a^(n-1)/4337107-1,n) 就行了.

无心人

哦 明白了