餘數可以連同證明一起計算
求最大公因數只是開始。同一個餘數計算還可以產生整數係數,讓別人核驗答案、判斷模意義下可否除法,並構造同時滿足兩個同餘式的數。關鍵是一個不變量:每個餘數始終是原輸入的整數線性組合。
先考慮非負整數 a , b a,b a , b ,且不全為零。以下算法使用精確整數運算。稍後模問題出現負係數時,我們會先正規化,再調用這個只接受非負輸入的算法。
為何用餘數取代一對數仍保留最大公因數
定義 11.1.1
(最大公因數與 Euclid 除法)
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,才用它計算新餘數,否則會失去原來要除的數。// 是該輪非負整數的精確向下整除,不是浮點除法後再四捨五入。
定理 11.1.2
(擴展 Euclid 回傳 Bézout 證書)
算法終止並回傳整數 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 . 初始化給出恆等表示。Euclid 取代保留公因數;一個表示減去另一個表示的 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 ) 。
若擴展 Euclid 得到 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 的倍數,而擴展歐幾里得(Euclid)算法把 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 。
常見錯誤
(把負係數直接交給只適用於非負輸入的迴圈)
擴展 Euclid 是針對非負輸入陳述的。若直接對 − 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 時,擴展 Euclid 可求 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 執行擴展 Euclid。列餘數序列與最大公因數的 Bézout 等式。哪些檢查可獨立確認答案?)
解答 · 答案 各除法為 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 的逆元。調用擴展 Euclid 時須遵守非負輸入條件,最後則用原負係數驗算。)
解答 · 答案 先正規化 − 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 整除,故不相容。每個式子各自都有很多解,卻不能由同一整數同時滿足。