余数可以连同证明一起计算
求最大公约数只是开始。同一个余数计算还可以产生整数系数,让别人核验答案、判断模意义下可否除法,并构造同时满足两个同余式的数。关键是一个不变量:每个余数始终是原输入的整数线性组合。
先考虑非负整数 a , b a,b a , b ,且不全为零。以下算法使用精确整数运算。稍后模问题出现负系数时,我们会先归一化,再调用这个只接受非负输入的算法。
为何用余数替换一对数仍保留最大公约数
gcd ( a , b ) \gcd(a,b) g cd( a , b ) 是同时整除两输入的最大正整数。若 b > 0 b>0 b > 0 ,欧几里得(Euclid)除法给出唯一整数 q , r q,r q , r ,使 a = q b + r a=qb+r a = q b + r 且 0 ≤ r < b 0\le r<b 0 ≤ r < b 。
正整数 d d d 同时整除 a , b a,b a , b ,等价于同时整除 b , a − q b b,a-qb b , a − q b 。正向是因为公约数整除线性组合 a − q b a-qb a − q b ;反向是因为 b , a − q b b,a-qb b , a − q b 的公约数也整除 q b + ( a − q b ) = a qb+(a-qb)=a q b + ( a − q b ) = a 。所以两对数的公约数集合完全相同,从而
gcd ( a , b ) = gcd ( b , a m o d b ) ( b > 0 ) . \gcd(a,b)=\gcd(b,a\bmod b)\qquad(b>0). g cd( a , b ) = g cd( b , a mod b ) ( b > 0 ) .
反复作此替换。第二分量是非负整数,只要原来为正就严格下降,过程必定终止。到达 ( d , 0 ) (d,0) ( d , 0 ) 时,最大公约数是 d d d ,因为两者的正公约数恰是 d d d 的正约数。原输入不全为零,保证最后 d > 0 d>0 d > 0 。
扩展循环,保留线性组合
为两个当前余数各保存一对系数。起初 a = 1 a + 0 b a=1a+0b a = 1 a + 0 b 、b = 0 a + 1 b b=0a+1b b = 0 a + 1 b 。若当前 u = s 0 a + t 0 b u=s_0a+t_0b u = s 0 a + t 0 b 、v = s 1 a + t 1 b v=s_1a+t_1b v = s 1 a + t 1 b ,下一余数就是
u − q v = ( s 0 − q s 1 ) a + ( t 0 − q t 1 ) b . u-qv=(s_0-qs_1)a+(t_0-qt_1)b. u − q v = ( s 0 − q s 1 ) a + ( t 0 − q t 1 ) b .
因此余数更新已经决定系数怎样更新,不必另外猜最后答案。
EXTENDED_GCD(a, b):
require a >= 0, b >= 0, and a + b > 0
old_r, r = a, b
old_s, s = 1, 0
old_t, t = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q * r
old_s, s = s, old_s - q * s
old_t, t = t, old_t - q * t
return old_r, old_s, old_t
每个逗号赋值都是同时进行:右侧使用该对变量的旧值。尤其不可先覆盖 old_r,才用它计算新余数,否则会失去原来要除的数。// 是该轮非负整数的精确向下整除,不是浮点除法后再四舍五入。
算法终止并返回整数 d , s , t d,s,t d , s , t ,满足
d = gcd ( a , b ) > 0 , s a + t b = d . d=\gcd(a,b)>0,\qquad sa+tb=d. d = g cd( a , b ) > 0 , s a + t b = d .
每次进入循环时,不变量为
gcd ( old_r , r ) = gcd ( a , b ) , old_r = old_s a + old_t b , r = s a + t b . \begin{aligned}
\gcd(\texttt{old\_r},\texttt{r})&=\gcd(a,b),\\
\texttt{old\_r}&=\texttt{old\_s}\,a+\texttt{old\_t}\,b,\\
\texttt{r}&=\texttt{s}\,a+\texttt{t}\,b.
\end{aligned} g cd( old_r , r ) old_r r = g cd( a , b ) , = old_s a + old_t b , = s a + t b . 初始化给出恒等表示。欧几里得替换保留公约数;一个表示减去另一个表示的 q q q 倍,正好得到系数更新。新第二余数小于旧正余数,所以过程终止。
终止时 r 为 0,而 old_r 是正的最大公约数;其表示式就是返回的贝祖(Bézout)等式。此证明也包含 b = 0 b=0 b = 0 ,此时不进循环;以及 a = 0 < b a=0<b a = 0 < b ,此时首商为 0,下一对直接是 ( b , 0 ) (b,0) ( b , 0 ) 。
例题 11.1.3
(给 gcd(240,46) 的每个余数带上系数)
起初余数 240、46 的系数分别是 ( 1 , 0 ) (1,0) ( 1 , 0 ) 、( 0 , 1 ) (0,1) ( 0 , 1 ) 。每行列出一个新生成余数:
最后非零余数为 2,其行给出 2 = − 9 ⋅ 240 + 47 ⋅ 46 2=-9\cdot240+47\cdot46 2 = − 9 ⋅ 240 + 47 ⋅ 46 。直接验算是 − 2160 + 2162 = 2 -2160+2162=2 − 2160 + 2162 = 2 。余数 0 那行也是正确等式,却不是应返回的最大公约数证书。
独立核验证书需要证明什么
若有人给正数 d d d 及系数 s , t s,t s , t ,声称 d = gcd ( a , b ) d=\gcd(a,b) d = g cd( a , b ) ,要同时检查 d d d 整除 a , b a,b a , b ,以及 s a + t b = d sa+tb=d s a + t b = d 。整除检查说明 d d d 是公约数;等式说明每个公约数都整除 d d d ,因为它整除所有整数线性组合。因此不会有更大的正公约数。
反例模式
只有整数线性组合还不是最大公约数证书 对 18 与 30,12 = − 18 + 30 12=-18+30 12 = − 18 + 30 确实成立,却不表示 12 是最大公约数,因为 12 不整除任一输入。真正最大公约数为 6。
特殊等式 1 = s a + t b 1=sa+tb 1 = s a + t b 确实能证明互素,因为 1 自动是所有整数的正公约数。对一般声称的正最大公约数,不可省略公约数检查。
证明透视
除法次数不等于比特运算次数 先设 a ≥ b > 0 a\ge b>0 a ≥ b > 0 。若 a = b a=b a = b ,第一次除法就终止循环。否则对正余数对 u > v u>v u > v ,若 v ≤ u / 2 v\le u/2 v ≤ u /2 ,下一余数已小于 u / 2 u/2 u /2 ;若 v > u / 2 v>u/2 v > u /2 ,商为 1,下一余数 u − v u-v u − v 也小于 u / 2 u/2 u /2 。所以至多两次替换后,当前较大余数至多是先前的一半,或者循环早已终止。
第一次除法后,余数都不超过 b b b ,故除法次数为 O ( 1 + log b ) O(1+\log b) O ( 1 + log b ) 。原输入大小相反,最多加一次商为 0 的交换;有零分量则立即或交换一次后终止。
这计算算术步数。大整数除法与乘法不是常数成本的比特运算,扩展版本也更新可能很大的系数。完整比特时间分析必须计入这些成本;除法次数是对数,本身不等于完成该分析。
模意义下的除法是求逆元
u ≡ v ( m o d m ) u\equiv v\pmod m u ≡ v ( mod m ) 表示 m m m 整除 u − v u-v u − v 。以下固定 m ≥ 2 m\ge2 m ≥ 2 。若整数 z z z 满足 a z ≡ 1 ( m o d m ) az\equiv1\pmod m a z ≡ 1 ( mod m ) ,便称它是 a a a 模 m m m 的逆元。
整数 a a a 模 m m m 有逆元,当且仅当 gcd ( a , m ) = 1 \gcd(a,m)=1 g cd( a , m ) = 1 。存在时,逆元在模 m m m 意义下唯一。
先以最小非负余数 a 0 = a m o d m a_0=a\bmod m a 0 = a mod m 替换 a a a 。( a , m ) (a,m) ( a , m ) 与 ( a 0 , m ) (a_0,m) ( a 0 , m ) 有相同公约数,且对任意整数 x x x 都有 a x ≡ a 0 x ( m o d m ) ax\equiv a_0x\pmod m a x ≡ a 0 x ( mod m ) 。
若扩展欧几里得得到 s a 0 + t m = 1 sa_0+tm=1 s a 0 + t m = 1 ,模 m m m 化简便有 a s ≡ 1 ( m o d m ) as\equiv1\pmod m a s ≡ 1 ( mod m ) ,故 s m o d m s\bmod m s mod m 是逆元。反之,有逆元便有某整数 t t t 使 a z + t m = 1 az+tm=1 a z + t m = 1 ;任何 a , m a,m a , m 的公约数都整除 1,因此最大公约数为 1。
若 z , z ′ z,z' z , z ′ 都是逆元,则 a ( z − z ′ ) ≡ 0 ( m o d m ) a(z-z')\equiv0\pmod m a ( z − z ′ ) ≡ 0 ( mod m ) 。乘上一个逆元,得 z − z ′ ≡ 0 ( m o d m ) z-z'\equiv0\pmod m z − z ′ ≡ 0 ( mod m ) 。这证明余数类唯一,不是整数代表唯一。
例如 43 = 2 ⋅ 17 + 9 43=2\cdot17+9 43 = 2 ⋅ 17 + 9 、17 = 9 + 8 17=9+8 17 = 9 + 8 、9 = 8 + 1 9=8+1 9 = 8 + 1 。反向代入得到 1 = 9 − 8 = 2 ⋅ 9 − 17 = 2 ⋅ 43 − 5 ⋅ 17 1=9-8=2\cdot9-17=2\cdot43-5\cdot17 1 = 9 − 8 = 2 ⋅ 9 − 17 = 2 ⋅ 43 − 5 ⋅ 17 。所以 17 模 43 的逆元是 − 5 ≡ 38 -5\equiv38 − 5 ≡ 38 ;验算 17 ⋅ 38 = 646 = 15 ⋅ 43 + 1 17\cdot38=646=15\cdot43+1 17 ⋅ 38 = 646 = 15 ⋅ 43 + 1 。
普通整数除法不能替代它。只有逆元存在时,分式 c / a c/a c / a 才能转成乘以 a − 1 a^{-1} a − 1 的模运算。例如 2 模 6 没有逆元。
概念视角 代数
最大公约数是所有组合的生成元 考虑所有整数组合 a x + m y ax+my a x + m y 组成的集合 a Z + m Z a\mathbb Z+m\mathbb Z a Z + m Z 。设 d = gcd ( a , m ) d=\gcd(a,m) d = g cd( a , m ) ,每个组合都是 d d d 的倍数,而扩展欧几里得算法把 d d d 本身表示成一个组合,所以这个集合恰好是 d Z d\mathbb Z d Z 。于是 a a a 在模 m m m 下可逆,当且仅当 1 1 1 是一个组合,即这个集合就是整个 Z \mathbb Z Z ,亦即 d = 1 d=1 d = 1 。当 a = 2 a=2 a = 2 、m = 6 m=6 m = 6 时,这个集合是 2 Z 2\mathbb Z 2 Z ,不含 1 1 1 。
常见错误
(把负系数直接交给只适用于非负输入的循环)
扩展欧几里得是针对非负输入陈述的。若直接对 − 7 -7 − 7 与 26 26 26 运行,商与余数就取决于语言如何舍入带符号除法,上面的证明也不再描述程序实际计算的内容。应先化简:− 7 ≡ 19 ( m o d 26 ) -7\equiv19\pmod{26} − 7 ≡ 19 ( mod 26 ) ,再对 19 19 19 与 26 26 26 运行循环。
系数不可逆仍可能有解
对整数 a , c a,c a , c 与 m ≥ 2 m\ge2 m ≥ 2 ,设 d = gcd ( a , m ) d=\gcd(a,m) d = g cd( a , m ) 。a x ≡ c ( m o d m ) ax\equiv c\pmod m a x ≡ c ( mod m ) 有解,当且仅当 d ∣ c d\mid c d ∣ c 。有解时,模 m m m 恰有 d d d 个不同余数类。
必要性是因为 a x − c = k m ax-c=km a x − c = k m 蕴含 d ∣ c d\mid c d ∣ c 。充分性方面,若 d ∣ c d\mid c d ∣ c ,便把整个整数方程、包括模数,都除以 d d d 。设 a ′ = a / d a'=a/d a ′ = a / d 、c ′ = c / d c'=c/d c ′ = c / d 、m ′ = m / d m'=m/d m ′ = m / d ,则
a x ≡ c ( m o d m ) ⟺ a ′ x ≡ c ′ ( m o d m ′ ) . ax\equiv c\pmod m
\quad\Longleftrightarrow\quad
a'x\equiv c'\pmod {m'}. a x ≡ c ( mod m ) ⟺ a ′ x ≡ c ′ ( mod m ′ ) .
若 m ′ > 1 m'>1 m ′ > 1 ,化简系数与 m ′ m' m ′ 互素,其逆元给出模 m ′ m' m ′ 的一个余数 x 0 x_0 x 0 。模 m m m 的解为
x = x 0 + j m ′ ( m o d m ) , j = 0 , 1 , … , d − 1. x=x_0+j m'\pmod m,\qquad j=0,1,\ldots,d-1. x = x 0 + j m ′ ( mod m ) , j = 0 , 1 , … , d − 1.
这 d d d 类互异:m m m 整除 ( j − j ′ ) m ′ (j-j')m' ( j − j ′ ) m ′ 只可能在 d d d 整除 j − j ′ j-j' j − j ′ 时成立。它们也穷尽所有解,因为每个解都模 m ′ m' m ′ 同余于 x 0 x_0 x 0 。若 m ′ = 1 m'=1 m ′ = 1 ,化简同余没有任何限制;此时 d = m d=m d = m ,全部 m m m 类都是解,不需要模 1 逆元。
只除系数与右侧、却保留模数,通常不对。2 x ≡ 2 ( m o d 6 ) 2x\equiv2\pmod6 2 x ≡ 2 ( mod 6 ) 应化为 x ≡ 1 ( m o d 3 ) x\equiv1\pmod3 x ≡ 1 ( mod 3 ) ,所以模 6 有 1 与 4 两类。若错留模 6,就会漏掉 4。
解 6 x ≡ 9 ( m o d 15 ) 6x\equiv9\pmod{15} 6 x ≡ 9 ( mod 15 ) 。这里 d = gcd ( 6 , 15 ) = 3 d=\gcd(6,15)=3 d = g cd( 6 , 15 ) = 3 ,而 3 整除 9,所以恰有三类解。把整个式子连同模数一并除以 3:2 x ≡ 3 ( m o d 5 ) 2x\equiv3\pmod5 2 x ≡ 3 ( mod 5 ) 。2 模 5 的逆元是 3,故 x ≡ 9 ≡ 4 ( m o d 5 ) x\equiv9\equiv4\pmod5 x ≡ 9 ≡ 4 ( mod 5 ) 。模 15 的解是 x = 4 + 5 j x=4+5j x = 4 + 5 j (j = 0 , 1 , 2 j=0,1,2 j = 0 , 1 , 2 ),即 4 , 9 , 14 4,9,14 4 , 9 , 14 。验算:6 ⋅ 4 = 24 ≡ 9 6\cdot4=24\equiv9 6 ⋅ 4 = 24 ≡ 9 ,6 ⋅ 9 = 54 = 3 ⋅ 15 + 9 6\cdot9=54=3\cdot15+9 6 ⋅ 9 = 54 = 3 ⋅ 15 + 9 ,6 ⋅ 14 = 84 = 5 ⋅ 15 + 9 6\cdot14=84=5\cdot15+9 6 ⋅ 14 = 84 = 5 ⋅ 15 + 9 。相反,6 x ≡ 8 ( m o d 15 ) 6x\equiv8\pmod{15} 6 x ≡ 8 ( mod 15 ) 无解,因为 3 ∤ 8 3\nmid8 3 ∤ 8 。
构造中国剩余解,不靠猜测
考虑 x ≡ α ( m o d m ) x\equiv\alpha\pmod m x ≡ α ( mod m ) 、x ≡ β ( m o d n ) x\equiv\beta\pmod n x ≡ β ( mod n ) ,其中 m , n ≥ 2 m,n\ge2 m , n ≥ 2 。写成 x = α + m t x=\alpha+mt x = α + m t 便先满足第一式;第二式变成 m t ≡ β − α ( m o d n ) mt\equiv\beta-\alpha\pmod n m t ≡ β − α ( mod n ) 。设 d = gcd ( m , n ) d=\gcd(m,n) d = g cd( m , n ) ,前述定理立即给出:有解当且仅当 d ∣ ( β − α ) d\mid(\beta-\alpha) d ∣ ( β − α ) 。
相容且 n / d > 1 n/d>1 n / d > 1 时,扩展欧几里得可求 m / d m/d m / d 模 n / d n/d n / d 的逆元,然后解
t ≡ ( m d ) − 1 β − α d ( m o d n / d ) , x = α + m t . t\equiv\left(\frac md\right)^{-1}
\frac{\beta-\alpha}{d}\pmod {n/d},\qquad
x=\alpha+mt. t ≡ ( d m ) − 1 d β − α ( mod n / d ) , x = α + m t .
若 n / d = 1 n/d=1 n / d = 1 ,取 t = 0 t=0 t = 0 即可:相容性已保证任意这样的 t t t 都满足第二式。答案模 lcm ( m , n ) = m n / d \operatorname{lcm}(m,n)=mn/d lcm ( m , n ) = mn / d 唯一,因为两解之差是两模数的公倍数,故是最小公倍数的倍数;反之,加最小公倍数保留两式。等价地,t t t 增加 n / d n/d n / d 时,x x x 正好增加 m n / d mn/d mn / d 。
求 x ≡ 2 ( m o d 5 ) x\equiv2\pmod5 x ≡ 2 ( mod 5 ) 、x ≡ 3 ( m o d 7 ) x\equiv3\pmod7 x ≡ 3 ( mod 7 ) 。设 x = 2 + 5 t x=2+5t x = 2 + 5 t ,得 5 t ≡ 1 ( m o d 7 ) 5t\equiv1\pmod7 5 t ≡ 1 ( mod 7 ) 。因为 5 ⋅ 3 = 15 ≡ 1 5\cdot3=15\equiv1 5 ⋅ 3 = 15 ≡ 1 ,5 模 7 的逆元为 3,所以 t ≡ 3 ( m o d 7 ) t\equiv3\pmod7 t ≡ 3 ( mod 7 ) ,并得 x ≡ 17 ( m o d 35 ) x\equiv17\pmod{35} x ≡ 17 ( mod 35 ) 。
直接验算 17 = 3 ⋅ 5 + 2 = 2 ⋅ 7 + 3 17=3\cdot5+2=2\cdot7+3 17 = 3 ⋅ 5 + 2 = 2 ⋅ 7 + 3 。模 35 的余数类代表全部整数解,不只是展示的 17。
模数不必互素,但此时相容性很重要。上述推导同时给出相容测试与正确合并模数。若一律把两模数相乘,当最大公约数大于 1 时,便看不出真正较小的周期。
附解答练习
快速检查
(对 99 与 78 运行扩展欧几里得。列余数序列与最大公约数的贝祖等式。哪些检查可独立确认答案?)
解答 · 答案 各除法为 99 = 78 + 21 99=78+21 99 = 78 + 21 、78 = 3 ⋅ 21 + 15 78=3\cdot21+15 78 = 3 ⋅ 21 + 15 、21 = 15 + 6 21=15+6 21 = 15 + 6 、15 = 2 ⋅ 6 + 3 15=2\cdot6+3 15 = 2 ⋅ 6 + 3 、6 = 2 ⋅ 3 6=2\cdot3 6 = 2 ⋅ 3 。21、15、6、3 的系数依次是 ( 1 , − 1 ) (1,-1) ( 1 , − 1 ) 、( − 3 , 4 ) (-3,4) ( − 3 , 4 ) 、( 4 , − 5 ) (4,-5) ( 4 , − 5 ) 、( − 11 , 14 ) (-11,14) ( − 11 , 14 ) 。
所以 gcd ( 99 , 78 ) = 3 = − 11 ⋅ 99 + 14 ⋅ 78 \gcd(99,78)=3=-11\cdot99+14\cdot78 g cd( 99 , 78 ) = 3 = − 11 ⋅ 99 + 14 ⋅ 78 。检查 3 整除两输入,以及 − 1089 + 1092 = 3 -1089+1092=3 − 1089 + 1092 = 3 。前者让 3 成为公约数;等式让每个公约数都整除 3,合起来就核验了最大公约数。
快速检查
(求 − 7 -7 − 7 模 26 的逆元。调用扩展欧几里得时须遵守非负输入条件,最后则用原负系数验算。)
解答 · 答案 先归一化 − 7 ≡ 19 ( m o d 26 ) -7\equiv19\pmod{26} − 7 ≡ 19 ( mod 26 ) 。由 26 = 19 + 7 26=19+7 26 = 19 + 7 、19 = 2 ⋅ 7 + 5 19=2\cdot7+5 19 = 2 ⋅ 7 + 5 、7 = 5 + 2 7=5+2 7 = 5 + 2 、5 = 2 ⋅ 2 + 1 5=2\cdot2+1 5 = 2 ⋅ 2 + 1 ,得 1 = 11 ⋅ 19 − 8 ⋅ 26 1=11\cdot19-8\cdot26 1 = 11 ⋅ 19 − 8 ⋅ 26 ,所以逆元为 11。
用原系数验算,( − 7 ) ⋅ 11 = − 77 = 1 − 3 ⋅ 26 (-7)\cdot11=-77=1-3\cdot26 ( − 7 ) ⋅ 11 = − 77 = 1 − 3 ⋅ 26 。不必让已给循环处理负余数,也不必假定某编程语言的带符号除法规则。
快速检查
(解 14 x ≡ 30 ( m o d 100 ) 14x\equiv30\pmod{100} 14 x ≡ 30 ( mod 100 ) ,并判断右侧改为 31 是否有解。另解 0 x ≡ 6 ( m o d 3 ) 0x\equiv6\pmod3 0 x ≡ 6 ( mod 3 ) 与 0 x ≡ 1 ( m o d 3 ) 0x\equiv1\pmod3 0 x ≡ 1 ( mod 3 ) 。)
解答 · 答案 最大公约数为 2 且整除 30,化简得 7 x ≡ 15 ( m o d 50 ) 7x\equiv15\pmod{50} 7 x ≡ 15 ( mod 50 ) 。因为 7 ⋅ 43 = 301 ≡ 1 ( m o d 50 ) 7\cdot43=301\equiv1\pmod{50} 7 ⋅ 43 = 301 ≡ 1 ( mod 50 ) ,所以 x ≡ 43 ⋅ 15 ≡ 45 ( m o d 50 ) x\equiv43\cdot15\equiv45\pmod{50} x ≡ 43 ⋅ 15 ≡ 45 ( mod 50 ) 。模 100 的两类为 45 与 95,代入都余 30。31 不被 2 整除,故改成 31 时无解。
对 0 x ≡ 6 ( m o d 3 ) 0x\equiv6\pmod3 0 x ≡ 6 ( mod 3 ) ,最大公约数为 3,化简模数是 1,所以 0、1、2 全部三类都可行。对 0 x ≡ 1 ( m o d 3 ) 0x\equiv1\pmod3 0 x ≡ 1 ( mod 3 ) ,最大公约数不整除右侧,因此无解。
快速检查
(解 x ≡ 2 ( m o d 6 ) x\equiv2\pmod6 x ≡ 2 ( mod 6 ) 、x ≡ 5 ( m o d 9 ) x\equiv5\pmod9 x ≡ 5 ( mod 9 ) 。若第二余数改为 4,结果如何?相容系统的正确周期是多少?)
先求两模数的最大公约数,再看它是否整除两余数之差。
解答 · 答案 最大公约数为 3,而 5 − 2 = 3 5-2=3 5 − 2 = 3 可被 3 整除,所以原系统相容。设 x = 2 + 6 t x=2+6t x = 2 + 6 t ,得 6 t ≡ 3 ( m o d 9 ) 6t\equiv3\pmod9 6 t ≡ 3 ( mod 9 ) ,即 2 t ≡ 1 ( m o d 3 ) 2t\equiv1\pmod3 2 t ≡ 1 ( mod 3 ) ,所以 t ≡ 2 ( m o d 3 ) t\equiv2\pmod3 t ≡ 2 ( mod 3 ) ,并得 x ≡ 14 ( m o d 18 ) x\equiv14\pmod{18} x ≡ 14 ( mod 18 ) 。
周期为 lcm ( 6 , 9 ) = 18 \operatorname{lcm}(6,9)=18 lcm ( 6 , 9 ) = 18 ,不是 54;14 模两数的余数确为 2、5。第二余数改为 4 时,差 4 − 2 = 2 4-2=2 4 − 2 = 2 不被 3 整除,故不相容。每个式子各自都有很多解,却不能由同一整数同时满足。