2020-01-22（学习笔记附录）
2020-01-22 本文已影响0人
好之者不如乐之者
数论概论
- 同余式、幂与费马小定理
- 费马小定理：p为质数，a除以p不为0，则a^(p-1) 除以p余1
- 欧拉公式：若gcd(a, m) = 1, 则a^φ(m) 与1关于m同余
- 若gcd(a, m) = 1, 则数列b1a, b2a, ……, bφ(m)*a (mod m) 与数列b1, b2, ……, bφ(m) (mod m) 相同，次序可能不同
- p是素数，a是任何整数且a除以p不余0，则数a, 2a, 3a, ……, (p-1)*a (mod p) 与数1,2,3, ……, (p-1) (mod p) 相同，次序可能不同
- 欧拉函数φ(m) : 是指在<m的数中与m互质的数的个数
- 费马小定理可以判断一个数是不是素数
