Code-ZROI-D1-Number-Theory.html

exGCD

(a, b) = 1 => ax = 1 (mod b) have solution ……………………………………. (1)

prove:

0a, 1a, 2a, … ,(b-1)a

If ka % b == ta % b => (k-t)a % b = 0

So b | (k-t)a

But (a, b) = 1 and (k-t) < b

So it is not possible.

If (a, b) = 1, based on (1), we have x satisfy ax = 1 (mod b)

So ax = 1 + ky

So ax + by = 1, b = -k have solution …………………………………………….. (2)

For any a, b

Let d = gcd(a, b)

Based on (2) we have ax/d + by/d = 1

So ax + by = gcd(a, b) have solution …………………………………………….. (3). That’s exGCD

How to solve exgcd(x, y)?

Inspired by gcd, we want to get exgcd(x, y) from exgcd(y, y mod x)

乘法逆元

a^(-1) * a = 1 (mod p)

Let m be a^(-1) am = pc+ 1

So am - pc = 1

Based on (2) we have when (a, p) == 1, m exists.

互相配对？

(0, p-1) 内的每个a都有其乘法逆元

可以考虑将其两两配对消去

a^(P-1) = 1 (mod P) 在 P 为质数和 a != 0 时成立

1 * 2 * 3 * … * (P - 1) = (P - 1)! (mod P)

0a * 2a * 3a * … * (P-1)a = (P-1)! (mod P) = (P-1)!*a^(P-1) (mod P) (based on (1.1))

So a^(P-1) = 1 (mod P)

Lucas定理

用于求组合数问题。

Download ____.pdf