为什么n^2-n+41(n=1\2\3...40)是质数
发布网友
发布时间：2024-10-04 01:07
共2个回答
热心网友
时间：2024-10-05 16:05
因为n^2+n+41=n(n+1)+41其中n(n+1)是偶数，则f必须是奇数，其质因子p必须是奇数
又因为，f≤39^2+39+41=1601
所以，只要它不是质数，它的最小质因子p必然满足p<√f≤40
（因为若f含有一个小于f的因子x>40，即它满足√f<x<f，那么，必含有另一个因子y，1<y<√f。）
此题相当于证明，n=0，1，2...39时，f=n^2+n+41，不能被任何小于41的质因子整除，
假设f存在这样一个质因子p
又因为4f=4n^2+4n+164=(2n+1)^2+163
可知即假设 勒让德符号(-163/p)=1
因为(-163/p)=(-1/p)*(163/p)
且由二次互反律可知，(163/p)*(p/163)=(-1)^[(p-1)(163-1)/4]
(163/p)=(-1)^[(p-1)(163-1)]*(p/163)
所以，(-163/p)=(-1/p)*(163/p)
=(-1/p)*(-1)^[(p-1)(163-1)]*(p/163)
=(-1)^[(p-1)/2]*(-1)^[(p-1)(163-1)/4]*(p/163)
=(-1)^[(p-1)(163-1)/4+(p-1)/2]*(p/163)
=(-1)^{(p-1)/2*[(163-1)/2+1]}*(p/163)
=(-1)^[(p-1)/2*82]*(p/163)
因为(p-1)/2为整数，所以，(p-1)/2*82为偶数
所以，(-163/p)=(p/163)
（也就是x^2+163是否能被p整除等价于y^2-p能否被163整除，x,y为任意整数）
(p/163)=p^[(163-1)/2] mod(163)=p^81 mod(163)
其实对任意奇质因子p<41，均有，p^81 mod(163)=-1
（这一步需要的验证略因为我只有基本验证，抛这块请更专家们回答这一步，看能否有巧妙的证明。）
故这与假设(-163/p)=1矛盾。所以，f不含有小于41的质因子。故f的因子只有1和它本身。
其实这一题是可以扩展的，它的大致形式是
对任意整数n，n^2+n+41不能被小于41的质数整除。
而且楼上的强化证明n^2+n+p并不能成立，它仅限于4p-1也是质数的情形才能成立（更甚至可能是这其中的一部分才成立，我不知道是否到极大数字时，这就不成立了，这没有验证过），否则不成立。
比如，4*7-1=27是合数，那么，n^2+n+7，就不满足n=0,1……5时均是质数。
像当n=1时，1^2+1+7=9=3*3是合数。
（补上它吧，笨方法一，对任意正整数y，y^2 mod(163)的余数列表为，
0 1 4 6 9 10 14 15 16 21 22 24 25 26 33 34 35 36 38 39 40 41 43 46 47 49 51 53 54 55 56 57 58 60 61 62 64 65 69 71 74 77 81 83 84 85 87 88 90 91 93 95 96 97 100 104 111 113 115 118 119 121 126 131 132 133 134 135 136 140 143 144 145 146 150 151 152 155 156 158 160 161
所以，当a不是上述列表中的数字时，不存在正整数y,使得y^2-a能被163整除。显然小于41的质数均不在此列，所以，（p/163)=-1，这与假设(-163/p)=1，矛盾。
说明，这方面最简单的例子是3，比如x^2 mod(3)的余数表为，0，1，所以有，对任意正整数x,不存在x^2-2能被3整除。当然，大于除数的按减除数的整数倍计，像x^2-4=x^2-1-3 mod(3)=x^2-1 mod(3)，这也是上面列表中只列到小于的163的原因。）
热心网友
时间：2024-10-05 16:04
1 41
2 43
3 47
4 53
5 61
6 71
7 83
8 97
9 113
10 131
11 151
12 173
13 197
14 223
15 251
16 281
17 313
18 347
19 383
20 421
21 461
22 503
23 547
24 593
25 641
26 691
27 743
28 797
29 853
30 911
31 971
32 1033
33 1097
34 1163
35 1231
36 1301
37 1373
38 1447
39 1523
40 1601
经验证，当n小于41时 n²-n+41的确是质数。
但当n等于41时 n²-n+41=1681=41²则不是质数。
