x^{n-1} mod n=1以及gcd(x^{(n-1)/p}-1,n)=1,则n是素数.
而10^785 + 3有小素因子4337107.
因此,问题很简单了. 谢谢！学到了。
这里有更多的介绍：http://primes.utm.edu/prove/prove3_1.html 原帖由 gxqcn 于 2008-12-26 21:13 发表 http://bbs.emath.ac.cn/images/common/back.gif
谢谢！学到了。
这里有更多的介绍：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<R, but either every factor of R is greater than $sqrt(R/F)$; or $n<2F^3$, R=rF+s, 0<s<F, and r is odd or $s^2-4r$ is not a square; then n is prime.If you are interested in these theorems, then it is well worth going to the source: .
所以对于$n=(10^785 + 3)*10^785+1$
取$F=10^785,R=10^785+3$,那么R=1*F+3, 所以$s=3,r=1,s^2-4r=5$不是平方数。
所以只要找到一个a,使得$a^{n-1}=1(mod n)$,但是$a^{{n-1}/2}-1$和$a^{{n-1}/5}-1$都同n互素就可以了 直接用11# 的结论证明楼主的数是不行的，因为前提条件不满足，
后来我找了些资料，才知道允许 F < R 的一些前提，这才是我们需要的，也就是 mathe 上面叙述的。 11#的结论也可以用，不过复杂一些。
用11#的结论，由于已经得出$4337107|10^785 + 3$,取$F=4337107*10^785$就可以了，只是F多了一个素因子 呵呵,还是mathe懂我.:lol :lol :lol 我有疑惑
every是任何的意思吧
就是说光一个似乎不行吧 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)
就行了. 哦
明白了
页:
1
[2]