只以2^k为底的强伪素数

mathematica

1. Clear["Global`*"];(*Clear all variables*)
   
2. n=26816952863;
   
3. m=n-1;s=0;
   
4. While[Mod[m,2]==0,m=m/2;s=s+1];
   
5. Do[t1=PowerMod[a,m,n];
   
6.     k=0;
   
7.     If[t1==1,Print[{a,k,t1,prime}];Continue[]];
   
8.     t2=t1;
   
9.     While[k<s-1&&t2!=n-1,k=k+1;t2=Mod[t2*t2,n]];
   
10.     If[t2==n-1,
    
11.         Print[{a,k,t2-n,prime}],
    
12.         Print[{a,k,composite}]
    
13.     ],
    
14. {a,2,100}]
    

复制代码

这个伪素数是26816952863=18287*1466449=(41*446+1)*(3288*446+1)
运行结果

1. {2,0,1,prime}
   
2. {3,0,composite}
   
3. {4,0,1,prime}
   
4. {5,0,composite}
   
5. {6,0,composite}
   
6. {7,0,composite}
   
7. {8,0,1,prime}
   
8. {9,0,composite}
   
9. {10,0,composite}
   
10. {11,0,composite}
    
11. {12,0,composite}
    
12. {13,0,composite}
    
13. {14,0,composite}
    
14. {15,0,composite}
    
15. {16,0,1,prime}
    
16. {17,0,composite}
    
17. {18,0,composite}
    
18. {19,0,composite}
    
19. {20,0,composite}
    
20. {21,0,composite}
    
21. {22,0,composite}
    
22. {23,0,composite}
    
23. {24,0,composite}
    
24. {25,0,composite}
    
25. {26,0,composite}
    
26. {27,0,composite}
    
27. {28,0,composite}
    
28. {29,0,composite}
    
29. {30,0,composite}
    
30. {31,0,composite}
    
31. {32,0,1,prime}
    
32. {33,0,composite}
    
33. {34,0,composite}
    
34. {35,0,composite}
    
35. {36,0,composite}
    
36. {37,0,composite}
    
37. {38,0,composite}
    
38. {39,0,composite}
    
39. {40,0,composite}
    
40. {41,0,composite}
    
41. {42,0,composite}
    
42. {43,0,composite}
    
43. {44,0,composite}
    
44. {45,0,composite}
    
45. {46,0,composite}
    
46. {47,0,composite}
    
47. {48,0,composite}
    
48. {49,0,composite}
    
49. {50,0,composite}
    
50. {51,0,composite}
    
51. {52,0,composite}
    
52. {53,0,composite}
    
53. {54,0,composite}
    
54. {55,0,composite}
    
55. {56,0,composite}
    
56. {57,0,composite}
    
57. {58,0,composite}
    
58. {59,0,composite}
    
59. {60,0,composite}
    
60. {61,0,composite}
    
61. {62,0,composite}
    
62. {63,0,composite}
    
63. {64,0,1,prime}
    
64. {65,0,composite}
    
65. {66,0,composite}
    
66. {67,0,composite}
    
67. {68,0,composite}
    
68. {69,0,composite}
    
69. {70,0,composite}
    
70. {71,0,composite}
    
71. {72,0,composite}
    
72. {73,0,composite}
    
73. {74,0,composite}
    
74. {75,0,composite}
    
75. {76,0,composite}
    
76. {77,0,composite}
    
77. {78,0,composite}
    
78. {79,0,composite}
    
79. {80,0,composite}
    
80. {81,0,composite}
    
81. {82,0,composite}
    
82. {83,0,composite}
    
83. {84,0,composite}
    
84. {85,0,composite}
    
85. {86,0,composite}
    
86. {87,0,composite}
    
87. {88,0,composite}
    
88. {89,0,composite}
    
89. {90,0,composite}
    
90. {91,0,composite}
    
91. {92,0,composite}
    
92. {93,0,composite}
    
93. {94,0,composite}
    
94. {95,0,composite}
    
95. {96,0,composite}
    
96. {97,0,composite}
    
97. {98,0,composite}
    
98. {99,0,composite}
    
99. {100,0,composite}
    

复制代码

n^0.5以下,似乎只有1 2 4 8 16 32 64 128 256"证明它是素数",
别的数都证明他是伪素数!

mathematica

26880359551=(4*4822+1)(289*4822+1)

mathematica

mathematica 发表于 2019-1-26 14:30
26880359551=(4*4822+1)(289*4822+1)

我发现第5个费马数似乎也是这样,2^(2^5)+1也是只以2 4 8 16 32为伪素数,不知道为什么

nyy

262144
最小的反例！