符号与约定

  1. 未知数 pp 均为质数。
  2. gcdm(A):=gcd(a1,a2,,aA,m)\gcd_m(A):=\gcd(a_1,a_2,\ldots,a_{|A|,m}) 其中 aiAa_i \in A
  3. A=mBA =_m B 表示集合 AA 和集合 BB 在模 mm 意义下相等。

定义

若 整数 aa 和整数 bb 除以正整数 mm 的余数相等,则称 aabbmm 同余,记为 ab(mod m)a \equiv b (\operatorname{mod} \ m)

同余类与剩余系

对于 a[0,m1]\forall a \in [0,m-1],集合 {a+km}(kZ)\{a + km\}(k \in \mathbb{Z}) 的所有数模 mm 同余,余数都是 aa,该集合称为一个模 mm 的同于类,简记为 a\overline{a}

mm 的同余类一共有 mm 个,分别为 1,2,3,,m1\overline{1},\overline{2},\overline{3},\cdots,\overline{m-1}。它们构成 mm 的完全剩余系。

1m1 \sim m 中与 mm 互质的数代表的同余类有 φ(m)\varphi(m) 个,它们构成 mm 的简化余系。例如,模 1010 的简化剩余系为 {1,3,7,9}\{\overline{1},\overline{3},\overline{7},\overline{9}\}

显然,简化同余系关于模 mm 乘法封闭。

欧拉定理

对于 a,m\forall a,m ,当 gcd(a,m)=1\gcd(a,m)=1 时有:

aφ(m)1(mod m)a^{\varphi(m)} \equiv 1 (\operatorname{mod} \ m)

证明1:

A={a1,a2,a3,aφ(m)}A=\{a_1,a_2,a_3\ldots,a_{\varphi(m)}\} 其中 ai,aj,aiajgcd(ai,m)=1\forall a_i,a_j,a_i \neq a_j \text{且} \gcd(a_i,m)=1,显然这个集合包含了所有比 mm 小且与 mm 互质的数。令 B={b×a1,b×a2,b×a3,b×aφ(m)}B=\{b\times a_1,b\times a_2,b\times a_3,\ldots b\times a_{\varphi(m)}\} 其中 bZ+b \in \mathbb{Z}^+。假设 ai,aj\forall a_i,a_j 时有 b×aib×aj(mod m)b \times a_i \equiv b\times a_j (\operatorname{mod} \ m),则有:

b×aib×aj0(mod m)b\times a_i - b\times a_j \equiv 0 (\operatorname{mod} \ m)

b(aiaj)0(mod m)b(a_i-a_j) \equiv 0 (\operatorname{mod} \ m)

因为 gcd(a,m)=1\gcd(a,m)=1,所以有

aiaj(mod m)a_i \equiv a_j (\operatorname{mod} \ m)

因为 bi≢bj(mod m)b_i \not\equiv b_j (\operatorname{mod} \ m),所以出现矛盾,假设不成立。

所以 A=mBA =_m B

所以有:

AB(mod m)\prod A \equiv \prod B (\operatorname{mod} \ m)

a1×a2××aφ(m)bφ(m)×a1×a2××aφ(m)(mod m)a_1 \times a_2 \times\cdots\times a_{\varphi{(m)}} \equiv b^{\varphi(m)} \times a_1 \times a_2 \times\cdots\times a_{\varphi{(m)}} (\operatorname{mod} \ m)

(bφ(m)1)×i=1φ(m)ai0(mod m)(b^{\varphi(m)} - 1) \times \prod_{i=1}^{\varphi(m)} a_i \equiv 0 (\operatorname{mod} \ m)

因为 gcdm(A)=1\gcd_m{(A)}=1

bφ(m)10(mod m)b^{\varphi(m)} - 1 \equiv 0 (\operatorname{mod} \ m)

所以有

bφ(m)1(mod m)b^{\varphi(m)} \equiv 1 (\operatorname{mod} \ m)

证毕。

证明2:

mZ+m \in \mathbb{Z}^+,则小于 mm 且与 mm 互质的集合著称集合 GG,设二元运算 ab=ab mod ma*b = ab\ \operatorname{mod} \ m,则代数系统 <G,>< G , * > 满足:

  • 封闭性:因为 gcd(abmodm,m)=gcd(ab,m)=1\gcd(ab\mod m , m) = \gcd(ab , m) = 1,显然满足封闭性。

  • 结合律:显然。

  • 存在单位元 1\mathbb{1}

  • xG\forall x \in Gx1x^{-1}(逆元)必定存在。

综上,该代数系统是群,且阶数为 φ(m)\varphi(m),根据拉格朗日定理::有限群的阶数是群中元素的阶数的整数倍,取任意 aGa \in G,设 aa 的阶数为 φ(m)/k\varphi(m) / k,于是 aφ(m)/k mod m=1aφ(m)a(φ(m)/k)k1k1(mod m)a^{\varphi(m)/k} \ \operatorname{mod} \ m = 1 \Rightarrow a^{\varphi(m)} \equiv a^{(\varphi(m)/k)k} \equiv 1^k \equiv 1 (\operatorname{mod} \ m),证毕。

欧拉定理的推论

a,nZ+a,n \in \mathbb{Z}^+gcd(a,n=1)\gcd(a,n=1),则对于任意正整数 bb

ababmodφ(n)(mod n)a^b \equiv a^{b\mod \varphi(n)}(\operatorname{mod} \ n)

证明:设 b=q×φ(n)+rb = q \times \varphi(n)+r,其中 0r<φ(n)0 \le r < \varphi(n),即 r=bmodφ(n)r = b\mod \varphi(n)。于是:

abaq×φ(n)+r(aφ(n))q×ar1q×ararabmodφ(n)(mod n)a^b \equiv a^{q \times \varphi(n)+r} \equiv (a^{\varphi(n)})^q \times a^r \equiv 1^q \times a^{r} \equiv a^r \equiv a^{b \mod\varphi(n)} (\operatorname{mod} \ n)

费马小定理

apa(mod p)a^p \equiv a (\operatorname{mod} \ p)

证明:

因为 pp 为质数,所以有 φ(p)=p1\varphi(p)=p-1,显然 gcd(a,p1)=1\gcd(a,p-1)=1,根据欧拉定理有:

ap11(mod p)apa(mod p)a^{p-1} \equiv 1 (\operatorname{mod} \ p) \Leftrightarrow a^p \equiv a (\operatorname{mod} \ p)

证毕。

扩展欧拉定理

bφ(m)b \ge \varphi(m) 有:

ababmodφ(m)+φ(m)(mod m)a^b \equiv a^{b\mod \varphi(m) + \varphi(m)} (\operatorname{mod} \ m)

gcd(a,m)=1\gcd(a,m)=1 时, ababmodφ(m)×1abmodφ(m)×aφ(m)(mod m)a^b \equiv a^{b \mod \varphi(m)} \times 1 \equiv a^{b \mod \varphi(m)} \times a ^{\varphi(m)} (\operatorname{mod} \ m),显然成立。

gcd(a,m)1\gcd(a,m) \neq 1 时,设 m=p1q1p2q2p3q3pnqnm = p_1^{q_1}p_2^{q_2}p_3^{q_3} \cdots p_n^{q_n},只需证明对于每一个 piqip_i^{q_i} 都有 ababmodφ(m)+φ(m)(mod piqi)a^b \equiv a^{b\mod \varphi(m) + \varphi(m)} (\operatorname{mod} \ p_i^{q_i}) 即可。

  • gcd(a,piqi)=1\gcd(a,p_i^{q_i}) = 1,则有:

abab/φ(m)φ(m)+bmodφ(m)abmodφ(m)(mod piqi)a^b \equiv a^{\lfloor b / \varphi(m)\rfloor\varphi(m) + b \mod \varphi(m)} \equiv a^{b \mod \varphi(m) (\operatorname{mod}\ p_i^{q_i})}

原因: φ\varphi 是积性函数。

  • gcd(a,piqi)1\gcd(a,p_i^{q_i}) \neq 1,则 aa 必然是 pp 的倍数,设 a=kpa = kp,因为 φ(piqi)=piqi1(pi1)\varphi(p_i^{q_i})=p_i^{q_i-1}(p_i-1),易证 φ(piqi)qi\varphi(p_i^{q_i}) \ge q_i,则 bφ(m)φ(piqi)qib \ge \varphi(m) \ge \varphi(p_i^{q_i}) \ge q_i

所以 piqiabmodφ(m)+φ(m),piqiabp_i^{q_i} \mid a^{b\mod \varphi(m) + \varphi(m)},p_i^{q_i} | a^b,所以有

ababmodφ(m)+φ(m)0(mod piqi)a^b \equiv a^{b\mod \varphi(m) + \varphi(m)} \equiv 0 (\operatorname{mod} \ p_i^{q_i})

综上,该定理成立。