素因子

mathe

请问$1+2^{2t+1}$的素因子是否都是模4为3？
如果是请证明，如果不是请给出一个批量构造方法

wayne

这题很刁，素的真因子肯定不是2^k+1型的，所以批量构造反例有点难

qianyb

我来乱证
当t=1时，$1+2^{2t+1}$ ＝3*3
当t=2时，$1+2^{2t+1}$ ＝3*11
当t=3时，$1+2^{2t+1}$ ＝3*43
...
由归纳法可知，每$1+2^{2t+1}$ 都是由3和u组成（u1=3,$u_(t+1)=u_t*4-1$)
所以结果就每个素因子模4为3
可以推出一个素数公式$(1+2^{2t+1})/3$ 都是素数

wayne

3# qianyb
数学归纳法不是这样用的，呵呵。

wayne

$2^29+1= 3*59*3033169$
$2^33+1=3^2*67*683*20857$
$2^35+1=3*11*43*281*86171$
t可以是：
{14, 16, 17, 18, 20, 22, 23, 24, 25, 26, 28, 29, 31, 33, 34, 35, 36, 37, 38, 40, 41, 43, 44, 46, 47, 48, 49, 51, 52, 53, 54, 55, 56, 58, 59, 61, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 81, 82, 85, 86, 87, 88, 89, 92, 94, 96, 97, 98, 100}

wayne

1# mathe
只要2t+1 是 29, 33, 35, 37, 41, 45, 47, 49, 51, 53, 57, 59, 63, 67, 69, 71, 73, 75, 77, 81, 83, 89, 93, 95, 97, 103, 107, 109, 113, 117, 119, 129, 131, 133, 137, 139, 143, 149, 151, 155, 157, 163, 173, 179, 193, 195,197 的奇数倍，那么，就2^(2t+1)+1就存在4m+1 的素因子。

比如：  
2t+1 = 29*(2m+1) ，那么，2^(2t+1)+1就有素因子3033169
2t+1 = 33*(2m+1) ，那么，2^(2t+1)+1就有素因子20857
2t+1 = 35*(2m+1) ，那么，2^(2t+1)+1就有素因子281
2t+1 = 37*(2m+1) ，那么，2^(2t+1)+1就有素因子1777
。。。。

      素因子
29        3033169
33        20857
35        281
37        1777
41        8831418697
45        18837001
47        165768537521
49        4363953127297
51        2857        6529
53        28059810762433
57        160465489
59        2833        1824726041
63        77158673929
67        7327657
69        168749965921
71        13952598148481
73        1753
75        1133836730401
77        617        78233
81        135433        272010961
83        2657        155377
89        62020897        18584774046020617
93        2903110321
95        2281
97        1553        31817        1100876018364883721
103        415141630193
107        84115747449047881488635567801
109        104124649
113        48817        636190001        491003369344660409
117        5302306226370307681801
119        143162553165560959297
129        1033        1591582393
131        1049        4744297
133        106788290443848295284382097033
137        1097        32127963626435681        105498212027592977
139        4506937
143        6156182033
149        1193        650833        7984559573504259856359124657
151        18717738334417
155        11161        29126056043168521
157        15073        17751783757817897        96833299198971305921
163        11281292593        337570547050390415041769
173        4153        1643464247728189221623609
179        58745093521
193        1871670769        7455099975844049
195        571403921126076957182161
197        197002597249        1348959352853811313

wayne

突然想到att上面应该有，一查果然：
http://www.research.att.com/~njas/sequences/A163184

只是感觉数据太少了，不知道有没有谁能多添点数据进去

gxqcn

5# wayne

我现在才注意到，原来该帖是在提供反例：如“281”（因为它模4为1）。

wayne

8# gxqcn
发现这题放在编程擂台里比较合适，
我搞出了好多特大号的反例，前11个是一致的，后面就缺项了