公钥密码 之 素数，费马定理与欧拉定理
素数
素数是我们中学就知道的知识，关于概念就不再赘述，我们来给出形式化的定义：
任意整数a > 1都可以唯一的因子分解为多个素数的积，设P为所有素数的集合，则对任意正整数a可唯一表示为：
， 其中每一个
特性：
若，定义k＝ab，我们知道：
，则可以推出有
费马定理
描述如下：若p是素数，a是正整数且不能被p整除，则
另一种表示方式：若p为素数且a为任意正整数，则
证明：
式（4. 3）：
欧拉函数与欧拉定理
1 欧拉函数
：小于n且与n互素的正整数的个数。
习惯上，n=1时，
特别的，n为素数时，
比如5，n＝5，则欧拉函数(5)＝4，包含1，2，3，4。
比如6，n＝6，则欧拉函数(6)＝2，包含1，5。
假设两个素数pq，
，那么对n＝pq有：
比如p＝5，q＝7，则n＝35；欧拉函数（35）＝ 4*6 = 24，包含：
1， 2， 3， 4， 6，8，
9，11，12，13，16，17，
18，19，22，23，24，26，
27，29，31，32，33，34
2 欧拉定理
对任意互素的a和n，有
证明：
另一种表示形式：