MENU

求解同余方程

February 25, 2019 • Read: 246 • 算法

前置知识

$a,b$对$m$取模的结果相同,记为$a\equiv b(mod\ m)$,即$a\ mod\ m == b\ mod\ m$

如果$a\equiv b(mod\ m)$,且$c\equiv d(mod\ m)$,则

  • $a + b\equiv c + d(mod\ m)$
  • $a \times b\equiv c \times d(mod\ m)$

同余方程

设有同余方程$ax\equiv b(mod\ n)$对于未知数$x$有解,当且仅当$b$是$gcd(a,n)$的倍数。且方程有解时,方程有$gcd(a,n)$个解

求解方程$ax\equiv b(mod\ n)$相当于求解方程$ax+ny=b$($x,y$为整数)

对于上面的式子证明如下:

由$ax \equiv b(mod\ n)$得

$$ ax = ny_1 + p\\ b = ny_2 + p $$

用中文解释就是,$ax$等于$y_1$倍的$n$加上余数$p$;而$b$等于$y_2$倍的$n$加上余数$p$

两式相减得$ax+ny=b$,证毕

所以求解同余方程$ax\equiv b(mod\ n)$就转化为了求解裴蜀方程$ax+ny=b$,并且$(x,y)$有整数解当且仅当$b$为$gcd(a,n)$的倍数

例题POJ1061 青蛙的约会

Archives Tip
QR Code for this page
Tipping QR Code