200字范文 > 扩展欧几里得算法乘法逆元与中国剩余定理

扩展欧几里得算法乘法逆元与中国剩余定理

时间：2022-07-20 15:20:57

相关推荐

扩展欧几里得算法乘法逆元与中国剩余定理

文章目录

前言定义、定理和部分证明整除定义定理定理的证明同余定义同余的性质同余的运算律运算律的证明扩展欧几里得算法代码模板算法详解乘法逆元求解逆元乘法逆元的作用中国剩余定理出处中国剩余定理的内容引用例题

前言

本文从定义与定理说起，详细地讲解了扩展欧几里得算法和乘法逆元的推导与应用。

本文尽量把推导的步骤细化，并罗列所需基础知识，比网络上一些博客更加详尽，希望能够为大家的数论信竞学习带来帮助。

如果发现推导错误，或者有更好的推导方法，请及时告知博主。

未加特殊说明时，本文中字母代表的均为整数。

定义、定理和部分证明

整除

定义

设 a , b ∈ Z a,b\in\Z a,b∈Z， a ≠ 0 a\neq0 a=0. 如果存在 q ∈ Z q\in\Z q∈Z，使得 b = a q b=aq b=aq，那么就说b b b 可被 a a a 整除，记做 a ∣ b a\mid b a∣b ，且称 b b b 是 a a a 的倍数， a a a 是 b b b 的约数. b b b 不能被 a a a 整除就记做 a ∤ b a\nmid b a∤b.

定理

a ∣ b ⇔ − a ∣ b ⇔ a ∣ − b ⇔ ∣ a ∣ ∣ ∣ b ∣ a\mid b \Leftrightarrow -a\mid b \Leftrightarrow a\mid -b \Leftrightarrow |a| \mid |b| a∣b⇔−a∣b⇔a∣−b⇔∣a∣∣∣b∣. (1)

a ∣ b a\mid b a∣b 且 a ∣ c ⇒ a\mid c \Rightarrow a∣c⇒对任意的 x , y ∈ Z x,y\in\Z x,y∈Z a ∣ b x + c y a\mid bx+cy a∣bx+cy (2)

定理的证明

由 b = a q ⇔ b = ( − a ) ( − q ) ⇔ − b = a ( − q ) ⇔ ∣ b ∣ = ∣ a ∣ ∣ q ∣ b=aq \Leftrightarrow b=(-a)(-q) \Leftrightarrow -b=a(-q) \Leftrightarrow |b|=|a||q| b=aq⇔b=(−a)(−q)⇔−b=a(−q)⇔∣b∣=∣a∣∣q∣，可证明(1)由 b = a q 1 b=aq_1 b=aq1， c = a q 2 c=aq_2 c=aq2 可推出 b x + c y = a ( q 1 x + q 2 y ) bx+cy=a(q_1x+q_2y) bx+cy=a(q1x+q2y)，则 a ∣ b x + c y a\mid bx+cy a∣bx+cy ，(2)成立

同余

定义

设 m ≠ 0 m\neq0 m=0. 若 m ∣ a − b m|a-b m∣a−b，即 a − b = k m a-b=km a−b=km，则称 m m m 为模，a a a 同余于 b b b 模 m m m以及b b b是 a a a对模 m m m的剩余，记做：

a ≡ b ( m o d m ) a m o d m = b a\equiv b\ (mod\ m) \\ a\ mod\ m=b a≡b(modm)amodm=b

不然，则称** a a a 不同余于 b b b 模 m m m，b b b 不是 a a a 对模 m m m 的剩余**，记做：

a ≠ b ( m o d m ) a m o d m ≠ b a\neq b\ (mod\ m) \\ a\ mod\ m\neq b a=b(modm)amodm=b

（注：上面第一条应该是在同余符号 ≡ \equiv ≡ 上打斜杠，然而我打不出来这个符号）

同余的性质

自反性： a ≡ a ( m o d m ) a\equiv a\ (mod\ m) a≡a(modm)对称性： a ≡ b ( m o d m ) ⇔ b ≡ a ( m o d m ) a\equiv b\ (mod\ m) \Leftrightarrow b\equiv a\ (mod\ m) a≡b(modm)⇔b≡a(modm)传递性：如果 a ≡ b ( m o d m ) a\equiv b\ (mod\ m) a≡b(modm) 并且 b ≡ c ( m o d m ) b\equiv c\ (mod\ m) b≡c(modm) ，那么 a ≡ c ( m o d m ) a\equiv c\ (mod\ m) a≡c(modm)

同余的运算律

模 m m m 意义下，如果 a ≡ b a\equiv b a≡b 并且 c ≡ d c\equiv d c≡d，那么 a + c ≡ b + d a+c\equiv b+d a+c≡b+d (1)模 m m m 意义下，如果 a ≡ b a\equiv b a≡b 并且 c ≡ d c\equiv d c≡d，那么 a c ≡ b d ac\equiv bd ac≡bd (2)

运算律的证明

(1)由 m ∣ a − b m\mid a-b m∣a−b 和 m ∣ c − d m\mid c-d m∣c−d 可以得到 m ∣ ( a − c ) + ( c − d ) m\mid(a-c)+(c-d) m∣(a−c)+(c−d) 也就是 m ∣ ( a + c ) − ( b + d ) m\mid (a+c)-(b+d) m∣(a+c)−(b+d)，

则 a + c ≡ b + d ( m o d m ) a+c \equiv b+d\ (mod\ m) a+c≡b+d(modm)

(2)由 a − b = k 1 m a-b=k_1m a−b=k1m， c − d = k 2 m c-d=k_2m c−d=k2m 可得到 a = b + k 1 m a=b+k_1m a=b+k1m， c = d + k 2 m c=d+k_2m c=d+k2m

那么 a c = ( b + k 1 m ) ( d + k 2 m ) = b d + b k 2 m + d k 1 m + k 1 k 2 m ac=(b+k_1m)(d+k_2m)=bd+bk_2m+dk_1m+k_1k_2m ac=(b+k1m)(d+k2m)=bd+bk2m+dk1m+k1k2m

那么 a c − b d = ( b k 2 + d k 1 + k 1 k 2 ) m ac-bd=(bk_2+d_k1+k_1k_2)m ac−bd=(bk2+dk1+k1k2)m 也就是 m ∣ a c − b d m\mid ac-bd m∣ac−bd，也就是 a c ≡ b d ( m o d m ) ac \equiv bd\ (mod\ m) ac≡bd(modm)

扩展欧几里得算法

详情请见《算法竞赛入门到进阶》P159-P160 （或其他算法书）关于扩展欧几里得算法的部分

代码模板

扩展欧几里得算法可以写成这样：

void exgcd(int a,int b,int &x,int &y) //x y是解，需要在每一次计算中改变{if(b==0){x=1,y=0;return;} exgcd(b,a%b,x,y);int tmp=x;x=y;y=tmp-(a/b)*y;}

如果不想理解其中为什么要写&x和&y，也可以写成这样（我不知道有没有人会这么写）

pair<int,int> exgcd(int a,int b){if(b==0)return make_pair(1,0);pair<int,int> t=exgcd(b,a%b);pair<int,int> res;res.first=t.second;res.second=t.first-(a/b)*t.second;return res;}

算法详解

下面我们来解释一下：

如果不看对于x和y的运算部分，那么这个函数就是普通的欧几里得算法，求的是 g c d ( a , b ) gcd(a,b) gcd(a,b)

我们想要求 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)的一组特解，那么显然在最底层的时候（也就是正好求得 g c d ( a , b ) gcd(a,b) gcd(a,b) 的时候，此时函数中的 a = g c d ( a , b ) a=gcd(a,b) a=gcd(a,b) ，函数中的 b = 0 b=0 b=0），这个特解就是

{ x = 1 y = 0 \begin{cases} x=1\\ y=0 \end{cases} {x=1y=0

因为$ 1gcd(a,b)+00=gcd(a,b)$。

因此我们知道了这个简单的特解，如何倒推回去，找到我们需要的特解呢？

也就是说，当我们运行到第9行（指第一块代码）时，

我们已经解出了 b x 1 + ( a m o d b ) y 1 = g c d ( b , a m o d b ) = g c d ( a , b ) bx_1+(a\ mod\ b)y_1=gcd(b,a\ mod\ b)=gcd(a,b) bx1+(amodb)y1=gcd(b,amodb)=gcd(a,b) 的解，

我们怎么通过这个特解，找到 a x 2 + b y 2 = g c d ( a , b ) ax_2+by_2=gcd(a,b) ax2+by2=gcd(a,b) 的解呢？

我们不妨把 a m o d b a\ mod\ b amodb 写成 a − ⌊ a / b ⌋ ∗ b a-\lfloor a/b\rfloor*b a−⌊a/b⌋∗b （向下取整，在C++中，如果变量 a , b a,b a,b都是 i n t int int类型，那么自动向下取整）

我们进行一些推导

{ b x 1 + ( a − ⌊ a / b ⌋ ∗ b ) y 1 = g c d ( a , b ) a x 2 + b y 2 = g c d ( a , b ) ⇒ a x 2 + b y 2 = b x 1 + ( a − ⌊ a / b ⌋ ∗ b ) y 1 ⇒ a x 2 + b y 2 = a y 1 + ( x 1 − ⌊ a / b ⌋ y 1 ) b ⇒ { x 2 = y 1 y 2 = x 1 − ⌊ a / b ⌋ y 1 \begin{cases} bx_1+(a-\lfloor a/b\rfloor*b)y_1=gcd(a,b)\\ ax_2+by_2=gcd(a,b) \end{cases} \\ \Rightarrow ax_2+by_2=bx_1+(a-\lfloor a/b\rfloor*b)y_1 \\ \Rightarrow ax_2+by_2=ay_1+(x_1-\lfloor a/b\rfloor y_1)b \\ \Rightarrow \begin{cases} x_2=y_1\\ y_2=x_1-\lfloor a/b\rfloor y_1 \end{cases} {bx1+(a−⌊a/b⌋∗b)y1=gcd(a,b)ax2+by2=gcd(a,b)⇒ax2+by2=bx1+(a−⌊a/b⌋∗b)y1⇒ax2+by2=ay1+(x1−⌊a/b⌋y1)b⇒{x2=y1y2=x1−⌊a/b⌋y1

这样我们就求出来了 x 1 , y 1 x_1,y_1 x1,y1和 x 2 , y 2 x_2,y_2 x2,y2的对应关系，就可以一步一步地求出来 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)的特解了。

乘法逆元

详情请见《算法竞赛入门到进阶》P161-P162 （或其他算法书）关于乘法逆元的部分

求解逆元

定义

a a a 模 m m m 的逆，是方程 a x ≡ 1 ( m o d m ) ax\equiv 1\ (mod\ m) ax≡1(modm)的解。

首先 a x ≡ 1 ( m o d m ) ⇔ a x − 1 = y m ⇔ a x + m y = 1 ax\equiv 1\ (mod\ m) \Leftrightarrow ax-1=ym \Leftrightarrow ax+my=1 ax≡1(modm)⇔ax−1=ym⇔ax+my=1 （这里的 y y y 只是我们设的一个未知数）

那么我们发现 a x + m y = 1 ax+my=1 ax+my=1 刚好可以用扩展欧几里得算法求解。

乘法逆元的作用

有时我们需要求解 ( a b ) m o d m \Big( \frac{a}{b} \Big) \ mod\ m (ba)modm，但是苦于 a b \frac{a}{b} ba 的精度不够，因此我们需要另寻一个办法。而运用逆元可以很方便地解决这个问题。

设 k k k 是模 m m m 意义下 b b b 的逆元，也就是说 k b ≡ 1 ( m o d m ) kb\equiv 1\ (mod\ m) kb≡1(modm) ，也就是 b k m o d m = 1 bk\ mod\ m=1 bkmodm=1 ，则有如下的推导：

( a b ) m o d m = ( a b ) m o d m ∗ 1 = ( a b ) m o d m ∗ ( ( b k ) m o d m ) = ( a b b k ) m o d m = ( a k ) m o d m \big(\frac{a}{b}\big)\ mod\ m=\big(\frac{a}{b}\big)\ mod\ m*1=\big(\frac{a}{b}\big)\ mod\ m*((bk)\ mod\ m)=\big(\frac{a}{b}bk\big)\ mod\ m=\big( ak\big)\ mod\ m (ba)modm=(ba)modm∗1=(ba)modm∗((bk)modm)=(babk)modm=(ak)modm

我们巧妙地把除法化为了乘法，避免了精度问题。

中国剩余定理

出处

对于中国剩余定理，我们决定先不看那又长又难的定义。

不如我们先来讲个故事吧：

中国剩余定理，即孙子定理，出自《孙子算经》。

《孙子算经》（成书于1500年前左右）是我国古代一本重要的数学著作，大家耳熟能详的鸡兔同笼问题就出自于此。就在《孙子算经》上，有一则引出今天所讲的定理的问题：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

意思就是说，有一个数，模3余2，模5余3，模7余2，让我们求出这个数是多少。

我们可以先用暴力枚举尝试一下：

模3余2的数：2,5,8,11,14,17,20,23,26,29…

模5余3的数：3,8,13,18,23,28,33…

模7余2的数：2,9,16,23,30…

很快就找到了答案，就是23，不过需要注意的是，这个数并不唯一，而23是这个问题的最小整数解。

聪明绝顶的古人们对于这道题，想出了一个绝妙的口诀：

三人同行古来稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。

（古稀就是70岁，廿一为21，半月是15天）

意思就是说用 70 70 70 乘上对 3 3 3 的余数 2 2 2，用 21 21 21 乘上对 5 5 5 的余数 3 3 3，用 15 15 15 乘上对 7 7 7 的余数 2 2 2，结果是：

2 ∗ 70 + 3 ∗ 21 + 2 ∗ 15 = 233 ( 2 ∗ 70 + 3 ∗ 21 + 2 ∗ 15 ) m o d 105 = 23 2*70+3*21+2*15=233\\ (2*70+3*21+2*15)\ mod\ 105=23 2∗70+3∗21+2∗15=233(2∗70+3∗21+2∗15)mod105=23

和我们的答案一致。不过这里的 70 , 21 , 15 70,21,15 70,21,15是怎么来的呢？

我们拿 70 70 70举例，发现 5 ∣ 70 5|70 5∣70 并且 7 ∣ 70 7|70 7∣70 ，而 70 ≡ 1 ( m o d 3 ) 70\equiv 1\ (mod\ 3) 70≡1(mod3) ，这也就是说 70 70 70乘多少倍，不会产生 5 , 7 5,7 5,7的余数，但是会给 3 3 3产生余数， 70 70 70模 3 3 3的余数是 1 1 1， 70 70 70乘多少倍，就会对模 3 3 3产生多少倍的余数。这样，我们轻轻松松地就控制了 3 3 3的余数部分。同理，我们用 21 21 21轻松地控制了 5 5 5的余数，用 15 15 15轻松地控制了 7 7 7的余数。

而这并不是最小的解，我们只需要模 3 , 5 , 7 3,5,7 3,5,7的最小公倍数 105 105 105（对三个数都不会产生余数），就可以求出来最小正整数解。

然而…

5 ∗ 7 = 35 35 ∗ 2 = 70 3 ∗ 7 = 21 21 ∗ 1 = 21 3 ∗ 5 = 15 15 ∗ 1 = 15 5*7=35\quad35*2=70\\3*7=21\quad21*1=21\\3*5=15\quad15*1=15 5∗7=3535∗2=703∗7=2121∗1=213∗5=1515∗1=15

有的乘了 2 2 2，有的乘了 1 1 1，我怎么知道如何才能求出来最终满足对于其他数都没有余数，而只对自己对应的数产生1的余数的那个数呢？其实，如果你认真阅读乘法逆元部分，你会很敏感地发现 2 ∗ 35 ≡ 1 ( m o d 3 ) 2*35\equiv1\ (mod\ 3) 2∗35≡1(mod3)，乘的倍数，正是 35 35 35模 3 3 3意义下的逆！

中国剩余定理的内容

这下子我们终于可以给出中国剩余定理的内容了：

设正整数 m 1 , m 2 , . . . , m k m_1,m_2,...,m_k m1,m2,...,mk是两两既约（互素，若 a a a 与 b b b 互素，则 a a a 和 b b b 的最大公约数为 1 1 1 ）的正整数，那么对于任意整数 a 1 , . . . , a k a_1,...,a_k a1,...,ak，一次同余方程组

x ≡ a j ( m o d m j ) , 1 ≤ j ≤ k x\equiv a_j\ (mod\ m_j),\quad1\leq j\leq k x≡aj(modmj),1≤j≤k

在模 M = m 1 ⋅ m 2 ⋅ . . . ⋅ m k M=m_1·m_2·...·m_k M=m1⋅m2⋅...⋅mk（也就是他们的最小公倍数）的意义下，有且仅有一个解，

这个解是

x = ( ∑ j = 1 k a j M j M j − 1 ) m o d m x=(\sum_{j=1}^k a_jM_jM_j^{-1})\ mod\ m x=(j=1∑kajMjMj−1)modm

其中 M j = M / m j M_j=M/m_j Mj=M/mj， M j − 1 M_j^{-1} Mj−1为 M j M_j Mj在模 m j m_j mj下的逆。

通过这个方法，我们可以快速地求出一些长成这样的一次同余方程组的解。