文章目录
前言定义、定理和部分证明整除定义定理定理的证明 同余定义同余的性质同余的运算律运算律的证明 扩展欧几里得算法代码模板算法详解 乘法逆元求解逆元乘法逆元的作用 中国剩余定理出处中国剩余定理的内容 引用例题前言
本文从定义与定理说起,详细地讲解了扩展欧几里得算法和乘法逆元的推导与应用。
本文尽量把推导的步骤细化,并罗列所需基础知识,比网络上一些博客更加详尽,希望能够为大家的数论信竞学习带来帮助。
如果发现推导错误,或者有更好的推导方法,请及时告知博主。
未加特殊说明时,本文中字母代表的均为整数。
定义、定理和部分证明
整除
定义
设 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下的逆。
通过这个方法,我们可以快速地求出一些长成这样的一次同余方程组的解。
引用
《初等数论》第三版,潘承洞 潘承彪著,第一章 整除理论,第三章 同余的基本知识Luogu P1082 同余方程 题解区《算法竞赛 入门到进阶》罗勇军 郭卫斌著 第8章 数学bilibili, 视频 《中国古代稀有的一个数学定理,孙子定理是什么?…》 李永乐例题
Luogu P1082 同余方程 (本题也可以用欧拉函数求解,感兴趣的同学可以看题解)