素数又称质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。 长期以来，素数被认为在纯数学以外的地方只有极少数的应用。到了1970年代，发明公共密钥加密这个概念之后，情况改变了，素数变成了RSA加密算法等一阶算法之基础。 自1951年以来，所有已知最大的素数都由电脑所发现。对更大素数的搜寻已在数学界以外的地方产生出兴趣。在数学家仍持续与素数理论奋斗的同时，互联网梅森素数大搜索及其他用来寻找大素数的分散式运算计划变得流行。
Euler函数φ(n) 定义为小于n且与n互素的正整数的个数。 若n是素数，则φ(n) = n - 1 若p,q是互不相同的素数，n = pq, 则φ(n) = φ(p) φ(q) = (p-1) (q - 1)
费马小定理是数论中的一个重要定理，在1636年提出。 其内容为假如a是一个整数，p是一个质数的话，那么 ap-1 = 1 mod p 推论： a的p次方 模 p = a 模 p
标签：合数,自然数,质数,素数,txt,定理 From： https://www.cnblogs.com/Janly/p/17611272.html