2020-01-22（学习笔记附录）

数论概论

• 同余式、幂与费马小定理
• 费马小定理：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互质的数的个数
• 费马小定理可以判断一个数是不是素数