发表于 | 分类于 | 1 | 阅读次数 720

符号与约定

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

定义

若 整数 aa 和整数 bb 除以正整数 mm 的余数相等，则称 aa 和 bb 模 mm 同余，记为 a≡b(mod⁡ m)a \equiv b (\operatorname{mod} \ m)。

同余类与剩余系

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

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

1∼m1 \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,ai≠aj且gcd⁡(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)}\} 其中 b∈Z+b \in \mathbb{Z}^+。假设 ∀ai,aj\forall a_i,a_j 时有 b×ai≡b×aj(mod⁡ m)b \times a_i \equiv b\times a_j (\operatorname{mod} \ m)，则有:

b×ai−b×aj≡0(mod⁡ m)b\times a_i - b\times a_j \equiv 0 (\operatorname{mod} \ m)

b(ai−aj)≡0(mod⁡ m)b(a_i-a_j) \equiv 0 (\operatorname{mod} \ m)

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

ai≡aj(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

所以有：

∏A≡∏B(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)ai≡0(mod⁡ m)(b^{\varphi(m)} - 1) \times \prod_{i=1}^{\varphi(m)} a_i \equiv 0 (\operatorname{mod} \ m)

因为 gcd⁡m(A)=1\gcd_m{(A)}=1

bφ(m)−1≡0(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：

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

  • 封闭性：因为 gcd⁡(abmod  m,m)=gcd⁡(ab,m)=1\gcd(ab\mod m , m) = \gcd(ab , m) = 1，显然满足封闭性。

  • 结合律：显然。

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

  • ∀x∈G\forall x \in G，x−1x^{-1}（逆元）必定存在。

综上，该代数系统是群，且阶数为 φ(m)\varphi(m)，根据拉格朗日定理：：有限群的阶数是群中元素的阶数的整数倍，取任意 a∈Ga \in G，设 aa 的阶数为 φ(m)/k\varphi(m) / k，于是 aφ(m)/k mod⁡ m=1⇒aφ(m)≡a(φ(m)/k)k≡1k≡1(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,n∈Z+a,n \in \mathbb{Z}^+ 且 gcd⁡(a,n=1)\gcd(a,n=1)，则对于任意正整数 bb 有

ab≡abmod  φ(n)(mod⁡ n)a^b \equiv a^{b\mod \varphi(n)}(\operatorname{mod} \ n)

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

ab≡aq×φ(n)+r≡(aφ(n))q×ar≡1q×ar≡ar≡abmod  φ(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)

费马小定理

ap≡a(mod⁡ p)a^p \equiv a (\operatorname{mod} \ p)

证明：

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

ap−1≡1(mod⁡ p)⇔ap≡a(mod⁡ p)a^{p-1} \equiv 1 (\operatorname{mod} \ p) \Leftrightarrow a^p \equiv a (\operatorname{mod} \ p)

证毕。

扩展欧拉定理

当 b≥φ(m)b \ge \varphi(m) 有：

ab≡abmod  φ(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 时， ab≡abmod  φ(m)×1≡abmod  φ(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=p1q1p2q2p3q3⋯pnqnm = p_1^{q_1}p_2^{q_2}p_3^{q_3} \cdots p_n^{q_n}，只需证明对于每一个 piqip_i^{q_i} 都有 ab≡abmod  φ(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，则有：

ab≡a⌊b/φ(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)=piqi−1(pi−1)\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。

所以 piqi∣abmod  φ(m)+φ(m),piqi∣abp_i^{q_i} \mid a^{b\mod \varphi(m) + \varphi(m)},p_i^{q_i} | a^b，所以有

ab≡abmod  φ(m)+φ(m)≡0(mod⁡ piqi)a^b \equiv a^{b\mod \varphi(m) + \varphi(m)} \equiv 0 (\operatorname{mod} \ p_i^{q_i})

综上，该定理成立。