模运算以及乘法逆元

基本的模运算

a,b,p 均为整数

模 p 加法：$(a+b)\mathrm{\%}p$

模 p 减法：$(a-b)\mathrm{\%}p$

模 p 乘法：$(a\ast b)\mathrm{\%}p$ ## Notes

同余式：正整数 a,b 对 p 取模，它们的余数相同，记作 $a\equiv b(modp)$

基本性质

1. 若 p=a-b, 则 $a\equiv b\mathrm{mod}p$ 例如 $11\equiv 4\mathrm{mod}7$

2. 传递性：若 $a\equiv b\mathrm{mod}p$ 且 $b\equiv c\mathrm{mod}p$, 则 $a\equiv c\mathrm{mod}p$

运算规则

$$\begin{array}{rl}(a+b)\mathrm{mod}p& =(a\mathrm{mod}p+b\mathrm{mod}p)\mathrm{mod}p\\ \\ (a-b)\mathrm{mod}p& =(a\mathrm{mod}p-b\mathrm{mod}p)\mathrm{mod}p\\ \\ (a\ast b)\mathrm{mod}p& =(a\mathrm{mod}p\ast b\mathrm{mod}p)\mathrm{mod}p\\ \\ (a^b)\mathrm{mod}p& =((a\mathrm{mod}p{)}^b)\mathrm{mod}p\\ \end{array}$$

结合律

$$\begin{array}{rl}((a+b\mathrm{mod}p+c)\mathrm{mod}p& =(a+(b+c)\mathrm{mod}p)\mathrm{mod}p\\ \\ ((a\ast b\mathrm{mod}p\ast c)\mathrm{mod}p& =(a\ast (b\ast c)\mathrm{mod}p)\mathrm{mod}p\\ \end{array}$$

交换律

分配律

$$(((a+b)\mathrm{mod}p)\ast c)\mathrm{mod}p=((a\ast c)\mathrm{mod}p+(b\ast c)\mathrm{mod}p)\mathrm{mod}p$$

重要定理

$\mathrm{若}a\equiv b\mathrm{mod}p$ 则对于任意的 c, 都有 $(a+c)\equiv (b+c)\mathrm{mod}p$

$\mathrm{若}a\equiv b\mathrm{mod}p$ 则对于任意的正整数 c, 都有 $(a\ast c)\equiv (b\ast c)\mathrm{mod}p$

$\mathrm{若}a\equiv b\mathrm{mod}p,c\equiv d\mathrm{mod}p$ 则对于任意的 c, 都有 $(a+c)\equiv (b+d)\mathrm{mod}p,(a-c)\equiv (b-d)\mathrm{mod}p,(a\ast c)\equiv (b\ast d)\mathrm{mod}p$

乘法逆元

定义

如果 ax≡1 (mod p), 且 gcd (a,p)=1（a 与 p 互质），则称 a 关于模 p 的乘法逆元为 x。

例子

例如：4 关于 1 模 7 的乘法逆元为多少？

4X≡1 mod 7

这个方程等价于求一个 X 和 K，满足

4X=7K+1

其中 X 和 K 都是整数。

若 ax≡1 (mod f), 则称 a 关于 1 模 f 的乘法逆元为 x。也可表示为 ax≡1 (mod f)。

当 a 与 f 互素时，a 关于模 f 的乘法逆元有解。如果不互素，则无解。如果 f 为素数，则从 1 到 f-1 的任意数都与 f 互素，即在 1 到 f-1 之间都恰好有一个关于模 f 的乘法逆元。

例如，求 5 关于模 14 的乘法逆元：

14=5*2+4

5=4*1+1

说明 5 与 14 互素，存在 5 关于 14 的乘法逆元。

1=5-4=5-(14-5*2)=5*3-14

因此，5 关于模 14 的乘法逆元为 3。

扩展欧几里得定理

欧几里得算法 (辗转相除法)

即以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数

证明

引理 1：若 d 是 a 和 b 的公约数，那么 d 也是 b 和 c 的公约数（c=a% b）

引理 2：若 d 是 b 和 c 的公约数 (c=a% b) 那么 d 也是 b 和 c 的公约数

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

证法：

a 可以表示成 $a=kb+r$(a,b,k,r 均为正整数且 r<b)

假设 d 是 a，b 的一个公约数，记作 $d|a,d|b$，即 a 和 b 都可以被 d 整除

而 $r=a-kb$，两边同时除以 d，$r/d=a/d-kb/d$，由等式右边可知 $m=r/d$ 为整数，因此 $d|r$

因此 d 也是 b，a mod b 的公约数

因 (a,b) 和 (b,a mod b) 的公约数相等，则其最大公约数也相等

def gcd(a,b):
    return gcd(b,a%b) if b else a

时间复杂度为 O (log n)

本体

设两个式子 $$\begin{array}{rl}ax+by& =gcd(a,b)\\ \\ b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime }& =gcd(b,a\mathrm{mod}b)\end{array}$$ 由欧几里得算法知:$gcd(a,b)=gcd(b,a\mathrm{mod}b)$

所以 $ax+by=b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime }$

而 $a\mathrm{mod}b=a-kb$

其中 k=[a/b]

所以有 $ax+by=b{x}^{\prime }+(a-kb)y^{\prime }$

展开移项得：$ax+by=a{y}^{\prime }+b(x^{\prime }-k{y}^{\prime })$

根据对应系数关系，可以设

$x=y^{\prime }、y=x^{\prime }-k{y}^{\prime }$ 来进一步求一个可行解

递归地使用 x'、y' 表示 “上一步” 的 x、y，就能递归地把问题转化为 $$b{x}^{\prime }+(a\mathrm{mod}b)y^{\prime }=gcd(b,a\mathrm{mod}b)$$ x 和 y 会不断减小，类似 gcd () 的递归终点，当扩展欧几里得算法 exgcd () 的 a$a^{\prime }{x}^{\prime }+b^{\prime }{y}^{\prime }=gcd(a^{\prime },b^{\prime })$ 中的 $b^{\prime }$ 为 0 时，可以得到递归终点的 $x^{\prime }=1,y^{\prime }=0$，层层回溯套用前面等式 $$\begin{array}{rl}x& =y^{\prime }\\ \\ y& =x^{\prime }-k{y}^{\prime }\end{array}$$ 就能得到 $ax+by=gcd(a,b)$ 的一组可行解

算法

对于任意两个整数 a, b，必存在整数 x, y，使得 ax + by = gcd (a,b) 成立，求出整数解 x, y，可以得到 gcd (a,b).

具体步骤

1. 定义 x₁ = 1, y₁ = 0, x₂ = 0, y₂ = 1

2. 若 b ≠ 0，使用带余除法，用 b 除以 a 得到余数 r；否则转到第 4 步

3. 用 b 代替 a, 用 r 代替 b， 令 x₁, y₁, x₂, y₂ = x₂, y₂, x₁ - q·x₂, y₁ - q·y₂，重复第 2 步

4.a 的值就是最大公约数 d，x₁ 和 y₁ 的值就是所求 x 和 y

代码实现

def exgcd(a,b):
    if(b==0):
        return 1,0,a
    x,y,g=exgcd(b,a%b)
    x,y=y,(x-(a//b)*y)
    return x,y,g

模拟矩阵运算的扩展欧几里得算法：https://www.cnblogs.com/kentle/p/14975039.html

求逆元

逆元：a 关于模 b 得逆元整数 d 满足 $a\ast d\mathrm{mod}b\equiv 1$

扩展欧几里得：求方程 $ax+by=gcd(a,b)$ 的一组可行解

关系：$(a\ast d)(modb)\equiv 1$，等价于 ad-kb=1, 其中 k 为未知整数

设 d 为 x，-k 为 y，则 $ad-kb=1$ 转化为 $ax+by=1$

求出 x 即可得到 a 关于模 b 的逆元

当 x 为负值的时候

代码实现

def exgcdinv(a,b):
    if(b==0):
        return 1,0,a
    x,y,g=exgcdinv(b,a%b)
    t=x
    x=y
    y=t-a//b*y
    return x,y,g

时间复杂度为 O (log n)（斐波那契复杂度）

补充

1. 显然，当 x 求出负值时，由于乘法逆元应为正，经验证，若 $a\ast d\mathrm{mod}b\equiv 1$，d=x+b（证明推导留待时候）

2.python 自带的 pow 函数 pow (a,b,c)，当 b 为 - 1 的时候，可以求 a 关于模 c 的乘法逆元

存在即可求

费马小定理

前置知识

费马小定理

对于整数 a 与质数 b，若 a 与 b 互质，则有 $$a^{b-1}\mathrm{mod}b\equiv 1$$

快速幂取模

两数之积取模等于对两数分别取模然后对积取模 $$(a\ast b)\mathrm{mod}p=((a\mathrm{mod}p)\ast (b\mathrm{mod}p))\mathrm{mod}p$$

代码实现

def powmod(a,n,mod):
    ret=1
    while n>0:
        if n%2 ==1:
            ret=a*a % mod
        a=a*a % mod
        n//=2
    return ret

求逆元

$a^{b-1}\mathrm{mod}b\equiv 1$ 等价于 $a\ast a^{b-2}\mathrm{mod}b\equiv 1$

显然 $a^{b-2}$ 就是 a mod b 的逆元

用 b-2 和 b 代替快速幂取模中的 n 和 mod:

def Fermatinv(a,b):
    return powmod(a,b-2,b)

时间复杂度：大约 O (log b)

适用范围：在模数 b 是质数时

Stein 算法

只有整数的移位和加减法，便于大素数求公约数

前置知识

$gcd(a,a)=a$，即一个数和他自身的公约数是其自身

$gcd(ka,kb)=kgcd(a,b)$ 也就是最大公约数运算和倍乘运算可以交换，特殊的，当 k=2 时，说明两个偶数的最大公约数必然能被 2 整除

算法步骤

假设 A₁=A,B₁=B,C₁=1

for n=1,2,3...do:

1. 若 A_n=0 或 B_n=0，则 max (A_n,B_n)*C_n 为最大公约数，算法结束

2. 若 A_n 和 B_n 均为偶数，则 A_n+1= 若 A_n/2，B_n+1=B_n/2，C_n+1=2*C_n

3. 若 A_n 为偶数，B_n 为奇数，则 A_n+1=A_n/2,B_n+1=B_n

4. 若 A_n 为奇数，B_n 为偶数，则 A_n+1=A_n，B_n+1=B_n/2

5. 若 A_n，B_n 均为奇数，则 A_n+1=|A_n-B_n|/2

B_n+1=min（A_n,B_n）,C_n+`=C_n

代码实现

def Stein(a,b):
    if a<b:
        a,b=b,a
        if(b==0):return a
    if a%2==0 and b%2 == 0:
        return 2*Stein(a>>1,b>>1)
    if a%2==0:
        return Stein(a>>1,b)
    if b%2==0:
        return Stein(a,b>>1)
    return Stein(abs(a-b)>>1,min(a,b))