问题

数论 >> 一般数论 >> 初等数论
Questions in category: 初等数论 (Elementary Number Theory).

伪素数

Posted by haifeng on 2019-06-12 23:16:46 last update 2019-06-19 14:01:19 | Answers (4) | 收藏


所谓的伪素数是指满足费马小定理的合数.

Fermat 小定理: 设 $p$ 是一个素数, 且 $0 < a < p$, 则有 $a^{p-1}\equiv 1\pmod p$.

 

举出10000以内的所有伪素数. 比如1000以内的伪素数只有三个: 341, 561, 645.

10000 以内的pseudo prime 有:

341
561
645
1105
1387
1729
1905
2047
2465
2701
2821
3277
4033
4371
4681
5461
6601
7957
8321
8481
8911

------------

Total: 21


 

[10000, 20000] 以内的伪素数

10261, 10585, 11305,12801,13741,13747,13981,14491,15709,15841,16705,18705,18721,19951