首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

Fermat's little theorem(费马小定律)

2013-09-26 
Fermats little theorem(费马小定理)If p is prime, then for every a 1 and a p, a^p-1 % p 1.如

Fermat's little theorem(费马小定理)

If p is prime, then for every a >= 1 and a < p, a^p-1 % p = 1.

如果p是质数,那么对于所有的 大于1,小于p的 a,都有 a 的 p-1 次方 除以 p 的余数为1。

这个定理可以用来测试一个数是否为质数。

但是,这个定理不是充分必要的。如果 p 不是质数,也有可能通过这个测试;我们再看他的引论:

如果a和p互为质数,并且 a^p-1 % p 不等于1,那么这样的情况,一定至少涵盖了a<p的1/2。 

如果我么重复地进行测试,这个概率会成指数级的减少,减少到我们可以忽略。

热点排行