## 费马定理 若`p`是素数，`a`是正整数且不能被`p`整除，则： > a^(p-1)≡1(mod p) ### 证明 1. 令`X`为小于`p`的正整数集合：`X={1, 2, ..., p-1}` 2. 令`Y`为`a`乘以`X`内的所有元素对`p`取模：`Y={a mod p, 2a mod p, ..., (p-1)a mod p}` 3. 证明Y中元素互不相等：假设`Y`中有`ia≡ja(mod p)`，由于`a`与`p`互素，因此`i≡j(mod p)`，则`i=j`，矛盾 4. 由于`Y`中元素互不相等，则`X`与`Y`两个集合的内容相同 5. 因此`a\*2a\*...\*(p-1)a≡1\*2\*...\*(p-1) (mod p)` 6. 即`(p-1)! \* a^(p-1) ≡ (p-1)! (mod p)` 7. 由于`(p-1)!`与`p`互素，则`a^(p-1)≡1(mod p)` ## 欧拉定理 欧拉函数`φ(n)`：小于`n`的整数中与`n`互素的数的个数 性质：设`m`，`n`是两个素数，则 > φ(m*n)=φ(m)*φ(n) 欧拉定理：设`a`，`m`互素，则 > a^φ(m)≡1(mod m)

创建时间：2023-06-10 | 最后修改：2023-12-27 | ©允许规范转载