Fermat定理

时间：2015-05-27 15:22:20 阅读：241 评论：0 收藏：0 [点我收藏+]

Fermat定理

Fermat小定理:

若n是素数，则对满足1≤a≤n-1的整数a，有a^(n-1)mod n=1;

逆否命题：

a^(n-1)mod n ！=1 ，则 n 为合数。

逆命题不一定成立：

满足 a^(n-1)mod n=1，n 既可能是 素数 ，也可能是 合数 ，不过很大几率是 素数

总而言之：

如果 n 是质数 ，则一定有 a^(n-1)mod n=1

如果 n 不是质数 ，则 a^(n-1)mod n=1 也有可能成立，但是几率很小

如果 a^(n-1)mod n=1 成立，则 n 有 较大概率是 素数。

注：

符合费马小定理而非素数的数叫做Carmichael（卡迈克尔数）.
前3个Carmichael数是561,1105,1729，Carmichael数是非常少的。
在1~100000000范围内的整数中，只有255个Carmichael数。

来自为知笔记(Wiz)

Fermat定理

原文：http://www.cnblogs.com/ZhangJinkun/p/1722bcdcc1096586e4ec477c75f0c270.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)