根据以下两个定理,可以求出线性同余方程 a x ≡ b ( m o d n ) ax\equiv b \pmod n a x ≡ b ( mod n ) 的解。
定理 1 :线性同余方程 a x ≡ b ( m o d n ) ax\equiv b \pmod n a x ≡ b ( mod n ) 可以改写为如下线性不定方程:
a x + n k = b ax + nk = b a x + nk = b 其中 x x x 和 k k k 是未知数。这两个方程是等价的,有整数解的充要条件为 gcd ( a , n ) ∣ b \gcd(a,n) \mid b g cd( a , n ) ∣ b 。
应用扩展欧几里德算法可以求解该线性不定方程。根据定理 1,对于线性不定方程 a x + n k = b ax+nk=b a x + nk = b ,可以先用扩展欧几里得算法求出一组 x 0 , k 0 x_0,k_0 x 0 , k 0 ,也就是 a x 0 + n k 0 = gcd ( a , n ) ax_0+nk_0=\gcd(a,n) a x 0 + n k 0 = g cd( a , n ) ,然后两边同时除以 gcd ( a , n ) \gcd(a,n) g cd( a , n ) ,再乘 b b b 。就得到了方程
a b gcd ( a , n ) x 0 + n b gcd ( a , n ) k 0 = b a\dfrac{b}{\gcd(a,n)}x_0+n\dfrac{b}{\gcd(a,n)}k_0=b a g cd( a , n ) b x 0 + n g cd( a , n ) b k 0 = b 于是找到方程的一个解。
定理 2 :若 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 ,且 x 0 x_0 x 0 、k 0 k_0 k 0 为方程 a x + n k = b ax+nk=b a x + nk = b 的一组解,则该方程的任意解可表示为:
并且对任意整数 t t t 都成立。
根据定理 2,可以从已求出的一个解,求出方程的所有解。实际问题中,往往要求出一个最小整数解,也就是一个特解
x = ( x m o d t + t ) m o d t x=(x \bmod t+t) \bmod t x = ( x mod t + t ) mod t 其中有
t = n gcd ( a , n ) t=\dfrac{n}{\gcd(a,n)} t = g cd( a , n ) n 如果仔细考虑,用扩展欧几里得算法求解与用逆元求解,两种方法是等价的。
实现
复制 int ex_gcd ( int a , int b , int& x , int& y) {
if (b == 0 ) {
x = 1 ;
y = 0 ;
return a;
}
int d = ex_gcd (b , a % b , x , y);
int temp = x;
x = y;
y = temp - a / b * y;
return d;
}
bool liEu ( int a , int b , int c , int& x , int& y) {
int d = ex_gcd (a , b , x , y);
if (c % d != 0 ) return false ;
int k = c / d;
x *= k;
y *= k;
return true ;
}