Know Your Wisdom

近义词
博文

模运算

模运算

加减

理解加减法的最好方法就是假设你坐在一辆无限长的火车上，每节车厢有10000个座位，编号从No.0000到No.9999。

train seat number
train seat number

每当你从No.9999的座位向前移动1步，你就到达了下一节车厢的第一个座位(No.0000)。

print((9999+1) % 10000)
# 0

同样地，如果你从No.0000的座位向后移动1步，你就到达了上一节车厢的最后一个座位(No.9999)。

print((0-1) % 10000)
# 9999

这就是%(模运算符)具体怎么工作的。 +(加法)表示你需要向前移动多少步； -(减法)表示你需要向后移动多少步；

乘除

理解乘除最好的方法就是把数字看作是一个集合，比如9 = [3, 3]，12 = [2, 2, 3]。

乘法的本质就是把两个集合合并在一起，比如9 * 12 = [2, 2, 3, 3, 3]。

除法的本质就是把两个集合相减，12=[2,2,3]12 = [2, 2, 3] 和 9=[3,3]9 = [3, 3] 相减，结果：129=[2,2,3][3,3]=[2,2][3]\frac{12}{9} = \frac{[2, 2, 3]}{[3, 3]} = \frac{[2, 2]}{[3]}。

基于上述基本事实，可以推导出许多非常有用的定理。

  • a⋅bmod  p=(amod  p)⋅(bmod  p)mod  pa \cdot b \mod p = (a \mod p) \cdot (b \mod p) \mod p
  • (xamod  p)bmod  p=xa⋅bmod  p (x^{a} \mod p)^{b} \mod p = x^{a \cdot b} \mod p

互质

两个数的最大公约数为1时，这两个数互质。

所有的合数都是由质数相乘得到的。

所以：

  • 对于质数：任意两个都是互质的，因为他们本身就是最小单元
    • 比如 3=[3]3 = [3] 和 17=[17]17 = [17]。
  • 对于合数：当组成合数 aa 和 bb 的两个质数集合 AA 和 BB 没有任何共同元素时，aa 和 bb 互质。
    • 比如 8=[2,2,2]8 = [2, 2, 2] 和 15=[3,5]15 = [3, 5]，他们没有任何共同元素，所以 88 和 1515 互质。

同余

同余就是两个数余数相同，比如 7mod  15≡22mod  157 \mod 15 \equiv 22 \mod 15，他俩对15取模之后的结果都是 7。

本质上 7+15⋅kmod  15≡7mod  15 7 + 15 \cdot k \mod 15 \equiv 7 \mod 15, k∈Zk \in Z。

费马小定理

当 a, p 互质时，有下列公式成立：

ap−1mod  p≡1mod  pa^{p-1} \mod p \equiv 1 \mod p

证明过程可以参考这个视频：

首先证明当 p 和 互质时，a⋅rmod  pa \cdot r \mod p, r∈[1,(p−1)]r \in [1, (p-1)] 是对数集 [1,(p−1)][1, (p-1)] 的重排列。

假设存在 r1,r2∈[1,p−1],r1≠r2r_1, r_2 \in [1, p-1], r_1 \ne r_2, 使得 a⋅r1mod  p=a⋅r2mod  pa \cdot r_1 \mod p = a \cdot r_2 \mod p ,则：

a⋅(r1−r2)mod  p≡0mod  pa \cdot (r_1 - r_2) \mod p \equiv 0 \mod p

明显不存在这样的 r1,r2r_1, r_2 ，证毕。

则：

ap−1⋅(p−1)!mod  p≡（p−1)!mod  pa^{p-1} \cdot (p-1)! \mod p \equiv （p-1)! \mod pap−1mod  p≡1mod  pa^{p-1} \mod p \equiv 1 \mod p

模逆元

当 a⋅bmod  p=1a \cdot b \mod p = 1 时，b=a−1b = a^{-1} 就是 a 的模逆元。

用费马小定理可以快速求模逆元：

a⋅bmod  p=1a\cdot b \mod p = 1a⋅bmod  p=ap−1mod  pa \cdot b \mod p = a^{p-1} \mod pbmod  p=ap−2mod  pb \mod p = a^{p-2} \mod p

举个例子：a=7,p=13a = 7, p = 13，则 a−1=713−2mod  13=2a^{-1} = 7^{13-2} \mod 13 = 2

用 python 中的 pow函数可以快速计算模逆元。更多求模逆元的方法可以参考algodoc的文章。

欧拉函数

对正整数n，欧拉函数 φ(n) 是小于等于 n 的正整数中与n互质的数的数目。

欧拉函数是费马小定理的延伸，欧拉函数（Euler’s totient function）通常用符号 ϕ(n)\phi(n) 表示，它表示小于等于 n 且与nn互质的正整数的个数。其公式在数学上可以表示为：

定义公式

ϕ(n)=n∏p∣n(1−1p)\phi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right)

其中：

  • pp表示nn的所有不同的素因子。
  • p∣np\mid n表示pp是nn的一个因子。

分解步骤

如果nn的素因子分解为：

n=p1k1p2k2⋯pmkmn = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}

则欧拉函数可以计算为：

ϕ(n)=n(1−1p1)(1−1p2)⋯(1−1pm)\phi(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \cdots \left( 1 - \frac{1}{p_m} \right)

计算示例

对于 n=12n = 12：

  1. 分解 n=22⋅31n = 2^2 \cdot 3^1 。
  2. 计算：
ϕ(12)=12(1−12)(1−13)=12⋅12⋅23=4\phi(12) = 12 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4

因此，欧拉函数 ϕ(12)=4\phi(12) = 4。

性质

素数的欧拉函数

  • 如果 n = p 是一个素数，则：ϕ(p)=p−1\phi(p) = p - 1

因为所有的数 1,2,…,p−11, 2, \ldots, p-1 都与 pp 互质。

幂次的欧拉函数

  • 如果n=pkn = p^k且pp是素数，则： ϕ(pk)=pk(1−1p)=pk−pk−1\phi(p^k) = p^k \left( 1 - \frac{1}{p} \right) = p^k - p^{k-1}，因为pkp^k中被pp整除的数有pk−1p^{k-1}个。

乘积性质

  1. 如果mm和nn互质（即gcd⁡(m,n)=1\gcd(m, n) = 1），则： ϕ(mn)=ϕ(m)⋅ϕ(n)\phi(mn) = \phi(m) \cdot \phi(n)
  2. 例子： ϕ(12)=ϕ(3⋅4)=ϕ(3)⋅ϕ(4)=2⋅2=4\phi(12) = \phi(3 \cdot 4) = \phi(3) \cdot \phi(4) = 2 \cdot 2 = 4 。

累加性质

  1. 如果nn是一个正整数，则所有小于nn的正整数中互质数的个数加起来为： ∑d∣nϕ(d)=n\sum_{d \mid n} \phi(d) = n ，其中d∣nd \mid n表示dd是nn的一个正因子。
  2. 例子： 对n=6n = 6 ，其因子为1,2,3,61, 2, 3, 6，计算ϕ(1)+ϕ(2)+ϕ(3)+ϕ(6)\phi(1) + \phi(2) + \phi(3) + \phi(6) ： 1+1+2+2=61 + 1 + 2 + 2 = 6

费马小定理延伸

aϕ(n)≡1(modn) (如果 gcd⁡(a,n)=1)a^{\phi(n)} \equiv 1 \pmod{n}\ \text{(如果 \( \gcd(a, n) = 1 \))}

欧几里得算法

欧几里得算法是一种用于计算两个数的最大公约数的算法。它的基本原理是，两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

证明：

假设 A>BA > B, A 和 B 的最大公约数是 N，则：C=A−B=N⋅(a−b)C = A - B = N \cdot(a - b)，显而易见 A,B,CA, B, C 的最大公约数都是 NN。

通过以上不断地求 CC，即可快速算出两个超大数的最大公约数。

参考资料

目录

目录