最大公约数(Greatest Common Divisor, GCD)

如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。

几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。

例如 12, 16
其中 12 的约数(这里只讨论正约数) 1, 2, 3, 4, 6, 12
16的约数 1, 2, 4, 8, 16
可以看出来 12 16的公约数是 1, 2, 4, 其中最大公约数是 4

使用扩展的欧几里得算法

Number1:

Number2:

最大公约数:

其中 s 和 t 满足

gcd(Number1, Number2) = Number1 \times s + Number2 \times t = 最大公约数

最小公倍数(Least Common Multiple, LCM)

如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。

几个整数中公有的倍数，叫做这几个数的公倍数；其中最小的一个，叫做这几个数的最小公倍数。

例如 12, 16
其中 12 的倍数 12, 24, 36, 48, 60, 72, 84, 96 ...
16的倍数 16, 32, 48, 64, 80, 96...
可以看出来 12 16的公倍数是 48, 96... 其中最小倍数是 48

最小公倍数可以借助最大公约数的算法得出,公式:

lcm(Number1, Number2) = \frac{∣ Number1 \times Number2 ∣}{gcd(Number1, Number2)} = 最小公倍数

Number1:

Number2:

最小公倍数:

如果一个线性同余方程

a x \equiv 1 (mod b) ⟺ a x mod b = 1 mod b

，则 x 称为

a mod b

的逆元，记作

a^{- 1}

乘法逆元的作用: 在模运算下无法直接执行除法(直接乘法可能出现小数)，所以在模运算下乘上逆元就相当于除以了一个数

例:

a / x \equiv d mod m ⟺ a \times x^{- 1} = d mod m ⟺ a \times x 的逆元 = d mod m

Number:

Modulus模数:

Inverse逆元: