摘要：对于任意正整数 a 和 任意正整数 m，存在唯一整数 q 和 r，满足 0≤r

对于任意正整数 a 和 任意正整数 m，存在唯一整数 q 和 r，满足 0≤r

a mod m = b mod m，即 a,b 除以 m 所得的余数相等，记作：a b(mod m)。

小于或等于 n 且与 n 互质的正整数的个数，称为欧拉函数，记为 φ(n)。

例如：φ(1)=1，φ(2)=1，φ(3)=2，φ(4)=2，φ(5)=4，φ(6)=2。

如果 n 是一个素数，那么 φ(n)=n-1。

定理：若 n 的质因数为 ，则欧拉函数表示为：φ

例：φ

引理：如果 p 是一个质数，n 是一个正整数，那么 φ。

例如：p=3，n=2，φ。

当 a,m 互素时，若 ax 1(mod m)，则称 x 是 a 关于模 m 的逆元，记做 。在 的范围内，逆元是唯一的。

证明

反证法：若 a 有两个逆元 0

那么有 成立，又由于 (a,m)=1，因此 ，与 0

欧拉定理：,如果 (α, m)=1，则 αφ(mod m)

由 ααφ(mod m)，可得 αφα(mod m)

若 m 是素数：αα(mod m)

证明：

假设有 m-1 个整数，那么 α，2α，3α，...，(m-1)α 中没有一个是 m 的倍数，也不存在任意两个数模 m 同余。

因此，这 m-1 个数对模 m 的同余是 1,2,3，...，(m-1) 的全排列。

可以化简为：α (mod m)

即 α (mod m) 得证。

设 i 为 [1,n] 中的整数，则 + (p mod i)

从而有 (mod) p

由于 p mod i

inv[i] = - (p / i) * inv[p % i] % p

来源：永生自媒体