10^n+1素数问题

winxos · 发表于 2009-8-27 18:32:48

您需要登录才可以下载或查看，没有账号？欢迎注册

×

形如$10^n+1$的素数，头两个是11，101
下一个是多少位数？当n为哪些数的时候一定是合数？

看看大家有没有什么好的想法。

winxos · 发表于 2009-8-27 18:35:20

游客，如果您要查看本帖隐藏内容请回复

mathe · 发表于 2009-8-27 23:03:16

必要条件,n是2的幂.
其实这个同费马素数问题很类似

winxos · 发表于 2009-8-28 01:16:36

必要条件,n是2的幂.
其实这个同费马素数问题很类似
mathe 发表于 2009-8-27 23:03

为什么这么多问题都涉及到2的幂呢？是否有什么必然性？

mathe · 发表于 2009-8-28 05:23:19

显然,对于n不是2的幂,多项式$x^n+1$可以因子分解,这个是因为对于任何奇数n,$x+1|x^n+1$

mathe · 发表于 2009-8-28 05:24:56

而对于$10^{2^k}+1$,在$2<=k<=14$时都不是素数.

mathe · 发表于 2009-8-28 05:30:48

mathe · 发表于 2009-8-28 05:44:03

根据第二个链接的定理2,对于$P=10^{2^k}+1$,只要找到一个数a,使得
$a^{P-1}-=1(mod P)$,
$gcd(a^{(P-1)/5}-1","P)=1$
那么P是素数.

mathe · 发表于 2009-8-28 05:50:46

当然如果$a^{P-1} !-= 1(mod P)$那么P不是素数.
对于$k=15$时,光计算$2^{P-1}(mod P)$已经挺慢的了.不知道gxqcn是否可以用HugeCalc来写个判断这一类数的素性的程序

gxqcn · 发表于 2009-8-28 07:34:06

有空我试试看。
HugeCalc 针对 10^n+1 型的模运算有加速算法。

账号		自动登录	找回密码
密码			欢迎注册

[猜想] 10^n+1素数问题