1. 同余問題從“時鐘算術”到現代密碼學的基石如果你玩過24點游戲或者對數字的周期性規律感到好奇那么“同余”這個概念其實已經在你身邊了。簡單來說同余就是研究整數除以同一個數后余數相同的學問。聽起來有點抽象想象一下時鐘下午3點和凌晨3點在12小時制下指針的位置是完全一樣的。這里“12”就是那個除數而“3”就是那個相同的余數。我們說15下午3點和3凌晨3點關于模12同余。這不僅僅是數學游戲從古老的歷法計算、商品校驗碼到現代互聯網的加密通信、計算機的哈希算法同余理論無處不在。它以一種簡潔而強大的方式處理著離散、循環和有限范圍內的數學問題。對于程序員、密碼學愛好者或者任何需要處理周期性數據、進行高效整數運算的人來說理解同余是繞不開的基本功。這篇文章我們就來徹底拆解它從最直觀的時鐘模型到解決實際問題的核心技巧再到它如何支撐起我們數字世界的安全防線。2. 同余問題的核心概念與符號體系要玩轉同余首先得熟悉它的“語言”。這套符號和定義是我們進行一切推理和計算的基礎。2.1 同余式的定義與基本性質給定三個整數 a, b 和 m (m 0)如果 a 和 b 除以 m 所得的余數相同我們就說a 和 b 關于模 m 同余記作a ≡ b (mod m)。這里的“mod”就是“模”modulo的縮寫m 稱為模數。例如17 除以 5 余 27 除以 5 也余 2所以 17 ≡ 7 (mod 5)。用數學定義來表述就是a ≡ b (mod m) 當且僅當 m | (a - b)即 m 能整除 (a - b)。這個定義比看余數更本質也更好用。同余關系具有一些非常友好、類似于等式的性質這使得我們可以像處理方程一樣處理同余式自反性a ≡ a (mod m)。對稱性若 a ≡ b (mod m)則 b ≡ a (mod m)。傳遞性若 a ≡ b (mod m) 且 b ≡ c (mod m)則 a ≡ c (mod m)。加減法性質若 a ≡ b (mod m) c ≡ d (mod m)則 a ± c ≡ b ± d (mod m)。乘法性質若 a ≡ b (mod m) c ≡ d (mod m)則 a * c ≡ b * d (mod m)。注意乘法性質可以直接用但除法或說“消去”要格外小心這是新手最容易踩坑的地方。簡單來說你不能直接在同余式兩邊除以一個數。例如2 ≡ 8 (mod 6) 是成立的但兩邊同時除以2得到 1 ≡ 4 (mod 6) 就不成立了。正確的做法是如果 ac ≡ bc (mod m)且 c 和 m 互質即最大公約數 gcd(c, m) 1那么才可以消去 c得到 a ≡ b (mod m)。如果 c 和 m 不互質消去后模數需要相應改變。例如從 2 ≡ 8 (mod 6) 兩邊除以2因為 gcd(2,6)2所以正確的結論是 1 ≡ 4 (mod 3)模數6也除以了公約數2。2.2 剩余類與完全剩余系這是理解同余“結構”的關鍵視角。給定模 m所有整數可以被劃分為 m 個“抽屜”每個“抽屜”里的數彼此同余。這些“抽屜”就叫作模 m 的剩余類。例如模 3 的剩余類有三個余數為0的類{..., -6, -3, 0, 3, 6, ...}余數為1的類{..., -5, -2, 1, 4, 7, ...}余數為2的類{..., -4, -1, 2, 5, 8, ...}從每個剩余類中挑一個代表元組成一個集合這個集合就稱為模 m 的一個完全剩余系。最常用的完全剩余系是最小非負剩余系{0, 1, 2, ..., m-1}。在編程中我們求余運算a % m得到的就是 a 在這個系中的代表元。理解剩余系的價值在于當我們處理模 m 下的所有可能情況時不需要考慮無窮多個整數只需要考察這 m 個代表元即可極大地簡化了問題。比如要判斷一個數模 m 是否為某個值或者要遍歷所有可能解時思維可以立刻聚焦到這個有限的集合上。2.3 同余與整除的橋梁帶余除法同余和整除是同一枚硬幣的兩面。表達式 a ≡ b (mod m) 等價于 m | (a - b)。這個轉換在證明和解題中極其有用。實操心得當你遇到一個關于整除性的證明題時嘗試將其轉化為同余式往往能打開思路。反之一個復雜的同余式通過移項變成整除形式有時也能利用數論中的已知定理如歐幾里得引理來破解。例如證明若 a ≡ b (mod m)則 a^n ≡ b^n (mod m)。利用整除觀點即證明 m | (a-b) 時有 m | (a^n - b^n)。而 a^n - b^n 含有因式 (a-b)結論顯然。這種視角切換是基本功。3. 一次同余方程 ax ≡ b (mod m) 的求解全攻略這是同余理論中最經典、也最常考的問題形式求解滿足方程的整數 x。它的解法流程清晰但細節中充滿陷阱。3.1 解的存在性判定裴蜀定理的登場方程 ax ≡ b (mod m) 有解嗎這完全由 a, b, m 的最大公約數決定。設 d gcd(a, m)。方程 ax ≡ b (mod m) 有解的充要條件是d | bd 能整除 b。為什么將同余方程改寫為 ax - my b。這是一個關于 x 和 y 的二元一次不定方程。根據裴蜀定理該方程有整數解當且僅當 d gcd(a, m) 能整除 b。這個判定是解題的第一步絕不能跳過。示例判斷 6x ≡ 3 (mod 9) 是否有解。gcd(6, 9) 3。檢查 3 是否能整除 3可以。因此方程有解。再判斷 6x ≡ 4 (mod 9) 是否有解。gcd(6, 9) 3。檢查 3 是否能整除 4不可以。因此方程無解。3.2 標準化方程與求解步驟當判定有解后我們可以按以下標準化步驟求解化簡模數設 d gcd(a, m)。因為 d | b方程兩邊及模數可以同時除以 d得到一個新的、系數與模數互質的方程 (a/d)x ≡ (b/d) (mod m/d)。記 a a/d, b b/d, m m/d。此時 gcd(a, m) 1。求乘法逆元對于方程 ax ≡ b (mod m)由于 a 與 m 互質a 在模 m 下存在唯一的乘法逆元。即存在整數 a^{-1}使得 a * a^{-1} ≡ 1 (mod m)。求解這個逆元是核心步驟。得到特解方程兩邊同時乘以逆元 a^{-1}得到特解x0 ≡ a^{-1} * b (mod m)。寫出通解原方程 ax ≡ b (mod m) 的通解為x ≡ x0 k * m (mod m)其中 k 0, 1, 2, ..., d-1。換句話說在模 m 的意義下方程有 d 個不同的解它們構成一個等差數列公差為 m。示例詳解求解 6x ≡ 3 (mod 9)。判定gcd(6,9)33|3有解。化簡兩邊及模數同除以3得 2x ≡ 1 (mod 3)。此時 a2, b1, m3gcd(2,3)1。求逆元尋找一個數乘以2再模3等于1。經嘗試2*24≡1(mod 3)所以2在模3下的逆元是2。得特解x0 ≡ 2 * 1 ≡ 2 (mod 3)。寫通解原模數 m9d3m3。所以通解為 x ≡ 2 k3 (mod 9)k0,1,2。即 x ≡ 2, 5, 8 (mod 9)。你可以驗證6212≡3(mod9)6530≡3(mod9)6848≡3(mod9)完全正確。3.3 乘法逆元的求法擴展歐幾里得算法如何求 a^{-1} (mod m)最系統、可編程的方法是擴展歐幾里得算法。它不僅能求出最大公約數 dgcd(a, m)還能找到一組整數 (x, y) 使得 ax my d。當 a 與 m 互質時d1方程變為 ax my 1。將這個等式對模 m 取余my 項被消去就得到 ax ≡ 1 (mod m)。此時求出的 x 就是 a 模 m 的逆元。手算步驟以求 2^{-1} mod 7 為例我們要找整數 x, y 使得 2x 7y 1。用歐幾里得算法求 gcd(2,7) 并記錄過程7 2 * 3 1 - 余數 12 1 * 2 0 - 余數 0結束。gcd1。反向代入用余數表示1從第一步1 7 - 2 * 3。檢查1 7 - 23。這已經是 2(-3) 7*1 1 的形式。所以x -3 是方程 2x 7y 1 的一個解。那么 -3 模 7 下的正數同余值就是 -3 7 4。驗證2 * 4 8 ≡ 1 (mod 7)。正確。所以 2 模 7 的逆元是 4。編程實現Pythondef ext_gcd(a, b): 擴展歐幾里得算法返回 (gcd, x, y) 使得 ax by gcd(a,b) if b 0: return a, 1, 0 else: gcd, x1, y1 ext_gcd(b, a % b) x y1 y x1 - (a // b) * y1 return gcd, x, y def mod_inverse(a, m): 求 a 模 m 的乘法逆元假設 gcd(a,m)1 gcd, x, y ext_gcd(a, m) if gcd ! 1: return None # 逆元不存在 else: return x % m # 返回最小非負剩余 # 示例求 2 模 7 的逆元 print(mod_inverse(2, 7)) # 輸出 4注意事項當模數較小比如是個質數時有時可以通過枚舉或費馬小定理a^{p-1} ≡ 1 mod p則 a^{-1} ≡ a^{p-2} mod p快速求逆元。但擴展歐幾里得算法是通用且高效的必須掌握。4. 同余方程組的解法中國剩余定理及其應用現實問題中我們常常遇到多個同余方程同時成立的情況這就是同余方程組。最經典的形式是 x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ ak (mod mk)其中 m1, m2, ..., mk 兩兩互質。解決這個問題的利器就是中國剩余定理。4.1 中國剩余定理的陳述與理解定理設 m1, m2, ..., mk 是兩兩互質的正整數記 M m1 * m2 * ... * mk。則對于任意整數 a1, a2, ..., ak同余方程組在模 M 下有唯一解。這個解可以通過以下構造性方法得到計算 M m1 * m2 * ... * mk。對每個 i計算 Mi M / mi。對每個 i求 Mi 模 mi 的乘法逆元 ti即 Mi * ti ≡ 1 (mod mi)。因為 mi 兩兩互質所以 Mi 與 mi 互質逆元存在方程組的解為 x ≡ a1M1t1 a2M2t2 ... akMktk (mod M)。為什么這樣構造可行觀察這個和式。對于某個特定的模 mi除了第 i 項 Mi * ti 模 mi 為 1因為 Mi*ti ≡ 1 mod mi其他項 Mj (j≠i) 都含有因子 mi因此模 mi 為 0。所以整個和式模 mi 就等于 ai * 1 ≡ ai (mod mi)完美滿足所有方程。4.2 實戰演練解“物不知數”問題《孫子算經》中的經典問題“今有物不知其數三三數之剩二五五數之剩三七七數之剩二問物幾何” 翻譯成同余方程組就是 x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7)m13, m25, m37兩兩互質。M 357 105。計算 MiM1 M/m1 105/3 35M2 M/m2 105/5 21M3 M/m3 105/7 15求逆元 ti求 35 mod 3 的逆元35 ≡ 2 (mod 3)2*24≡1(mod3)所以 t12。求 21 mod 5 的逆元21 ≡ 1 (mod 5)1*11所以 t21。求 15 mod 7 的逆元15 ≡ 1 (mod 7)1*11所以 t31。構造解x ≡ 2352 3211 2151 (mod 105) 140 63 30 233。取最小正整數解233 mod 105 233 - 2*105 23。所以滿足條件的最小正整數是 23。驗證23除以3余2除以5余3除以7余2。4.3 模數不互質情況的處理策略中國剩余定理要求模數兩兩互質。如果模數不互質怎么辦方程組可能無解也可能有解需要先處理。通用解法思路合并法 從兩個方程開始x ≡ a1 (mod m1), x ≡ a2 (mod m2)。 設解的形式為 x a1 m1 * k代入第二個方程a1 m1k ≡ a2 (mod m2) m1k ≡ (a2 - a1) (mod m2)。 這就轉化成了一個關于 k 的一次同余方程設 d gcd(m1, m2)。若 d 不能整除 (a2 - a1)則整個方程組無解。若 d 能整除 (a2 - a1)則按3.2節方法求解 k ≡ k0 (mod m2)其中 m2 m2/d。于是 k k0 t * m2。代回 x a1 m1k得到 x ≡ a1 m1k0 (mod lcm(m1, m2))。這里 lcm(m1, m2) m1*m2/d 就是新的模數。這樣兩個方程合并為了一個方程。重復此過程依次與第三個、第四個...方程合并最終要么發現無解要么得到一個形如 x ≡ A (mod M) 的解其中 M 是所有原模數的最小公倍數。示例解方程組 x ≡ 2 (mod 4) x ≡ 1 (mod 6)設 x 2 4k代入第二式2 4k ≡ 1 (mod 6) 4k ≡ -1 ≡ 5 (mod 6)。判定gcd(4,6)22不能整除5所以方程 4k ≡ 5 (mod 6) 無解。因此原方程組無解。實操心得在編程解決此類問題時合并法是普適的算法。先寫好求解 ax ≡ b (mod m) 的函數然后循環合并各個方程。每次合并后解的形式 x ≡ A (mod M) 中的 A 和 M 都會更新。如果中途某次求解 k 失敗即 ax≡b mod m 無解則整個方程組無解。5. 同余理論在計算機科學中的核心應用同余絕非純粹的數學理論它在計算機的世界里扮演著至關重要的角色是許多核心技術的數學基石。5.1 校驗碼保障數據完整性的衛士最常見的應用是各種校驗碼用于檢測數據傳輸或存儲過程中是否發生錯誤。奇偶校驗最簡單的模2同余。通過設置一個校驗位使得整個數據塊中1的個數為奇數奇校驗或偶數偶校驗。接收方重新計算并檢查同余關系是否被破壞。ISBN 號國際標準書號最后一位是校驗碼。以ISBN-10為例計算規則是加權和模11同余于0。具體地對于號碼 a1-a2...a10滿足 Σ(i1 to 10) i * ai ≡ 0 (mod 11)。如果得到余數10則用‘X’表示。這個同余關系可以自動檢測出單個數位錯誤或常見的相鄰數字換位錯誤。銀行卡號Luhn算法廣泛應用于信用卡、儲蓄卡號校驗。算法涉及“乘2后數字求和”以及模10同余。最終所有數位經過特定規則計算后的總和必須能被10整除即模10同余于0。這是一個高效且能檢測多種錯誤的校驗方案。背后的思想在原始數據上附加一個由數據本身通過同余運算得到的“校驗和”。任何微小的數據變動高概率會導致校驗和不符合預設的同余關系從而被系統發現。5.2 散列函數與哈希表快速查找的引擎哈希表是現代編程語言的基石如Python的dictJava的HashMap。它的核心思想是將一個可能很大的鍵key通過散列函數映射到一個較小范圍的整數索引桶的編號這個索引通常就是hash(key) % table_size。這里的取模運算%正是同余運算。它確保了無論輸入數據多大輸出總落在固定的有限區間內0 到 table_size-1。設計良好的散列函數和模運算能使數據均勻分布在不同桶中從而實現接近O(1)的查找、插入性能。注意事項選擇模數哈希表大小有講究。通常選擇一個質數這能減少不同鍵經過散列函數和取模后發生沖突映射到同一個桶的概率。因為如果模數與數據的規律有公因子更容易導致分布不均。5.3 偽隨機數生成確定性的“隨機”計算機生成的隨機數通常是“偽隨機”的由一個確定的算法產生。最經典的算法之一是線性同余生成器X_{n1} (a * X_n c) % m其中X0是種子a是乘數c是增量m是模數。序列的下一個數由當前數通過一個線性同余關系確定。雖然序列是確定的但只要參數a, c, m選擇得當需要滿足一定的數論條件如Hull-Dobell定理產生的序列在統計上可以表現出很好的隨機性并且周期很長最多為m。這是許多編程語言內置隨機函數的基礎原理。5.4 現代密碼學的基石RSA算法淺析這是同余理論皇冠上的明珠。RSA公鑰加密算法的安全性建立在大數分解的困難性和歐拉定理、同余運算之上。簡化版原理密鑰生成選擇兩個大質數p和q計算 n p * q以及歐拉函數 φ(n) (p-1)*(q-1)。選擇一個整數e滿足 1 e φ(n) 且 gcd(e, φ(n)) 1。e 就是公鑰指數。計算私鑰指數 d使得 e * d ≡ 1 (mod φ(n))。這正是在模 φ(n) 下求 e 的乘法逆元使用擴展歐幾里得算法。公鑰是 (n, e)私鑰是 (n, d)。加密與解密加密消息 m需轉換為小于n的整數c ≡ m^e (mod n)。c 是密文。解密密文 cm ≡ c^d (mod n)。為什么能恢復根據歐拉定理當 m 與 n 互質時有 m^{φ(n)} ≡ 1 (mod n)。因為 ed ≡ 1 (mod φ(n))所以 ed 1 kφ(n)。那么解密時 c^d ≡ (m^e)^d ≡ m^{ed} ≡ m^{1 k*φ(n)} ≡ m * (m^{φ(n)})^k ≡ m * 1^k ≡ m (mod n)。 即使 m 與 n 不互質利用中國剩余定理也能證明解密過程依然成立。整個流程的核心操作——大指數冪的模運算、乘法逆元的求解——都深深依賴于同余理論。攻擊者知道公鑰 (n, e) 和密文 c但想從 c ≡ m^e (mod n) 中求出 m或者想從 e*d ≡ 1 (mod φ(n)) 的關系中求出 d都等價于進行大數分解求p, q或求解離散對數在計算上是極其困難的。這就是RSA安全性的來源。6. 同余問題實戰典型例題與深度剖析理解了原理還需要在實戰中錘煉。下面通過幾個典型例題展示如何綜合運用上述知識。6.1 例題一尋找滿足特定余數條件的數問題求最小的正整數使它除以3余2除以5余3除以7余4。分析與解答 這是一個標準的中國剩余定理問題但模數3,5,7兩兩互質可以直接套用公式。 方程組x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 4 (mod 7)。M 357105。M1105/335, M2105/521, M3105/715。求逆元解 35t1 ≡ 1 (mod 3)。35≡2 mod 3即2t1≡1 mod 3得 t12。解 21*t2 ≡ 1 (mod 5)。21≡1 mod 5得 t21。解 15*t3 ≡ 1 (mod 7)。15≡1 mod 7得 t31。x ≡ 2352 3211 4151 (mod 105) 140 63 60 263。最小正整數解263 mod 105 263 - 2*105 53。驗證53÷317余253÷510余353÷77余4。正確。技巧對于模數較小且互質的情況可以不用完全套公式嘗試“逐步滿足法”。從最大的模數開始考慮尋找同時滿足條件的數。找除以7余4的數4, 11, 18, 25, 32, 39, 46, 53...從中找除以5余3的數檢查4 mod 54不符11 mod 51不符18 mod 53符合但18 mod 30不符。由于要同時滿足模7和模5這樣的數每次增加 LCM(7,5)35。所以從18開始加3553, 88...檢查53 mod 32符合。所以最小解是53。這種方法更直觀適合心算或快速驗證。6.2 例題二指數模運算與費馬-歐拉定理的應用問題求 3^2024 除以 17 的余數。分析與解答 直接計算3的2024次方不現實。這里需要用到歐拉定理費馬小定理的推廣若 a 與 n 互質則 a^{φ(n)} ≡ 1 (mod n)其中 φ(n) 是歐拉函數表示小于 n 且與 n 互質的正整數的個數。對于模數17它是一個質數所以 φ(17) 16。因為3和17互質根據歐拉定理有 3^16 ≡ 1 (mod 17)。現在我們將指數2024對16取余這就是同余的威力指數可以在模 φ(n) 的意義下化簡 2024 ÷ 16 126 ... 8。即 2024 16 * 126 8。因此 3^2024 3^{16*126 8} (3^16)^{126} * 3^8 ≡ 1^{126} * 3^8 ≡ 3^8 (mod 17)。現在只需要計算 3^8 mod 17。我們可以逐步平方 3^2 9 3^4 (3^2)^2 9^2 81 ≡ 81 - 417 81 - 68 13 (mod 17) 3^8 (3^4)^2 ≡ 13^2 169 ≡ 169 - 917 169 - 153 16 (mod 17)所以3^2024 mod 17 16。核心思想對于求大指數冪的模余數首先檢查底數與模數是否互質。如果互質利用歐拉定理模數為質數時用費馬小定理大幅降低指數。指數化簡的模數是 φ(n)。這是解決此類問題的標準流程。6.3 例題三解一個需要技巧性變形的同余方程問題解同余方程 5x ≡ 2 (mod 13)。分析與解答 這是一個簡單的一次方程gcd(5,13)1有唯一解。我們演示如何靈活求解。方法一求逆元法標準求5模13的逆元。5*? ≡ 1 mod 13。嘗試5840≡1 mod 13 (因為13339)。所以逆元是8。 方程兩邊乘以8x ≡ 2 * 8 ≡ 16 ≡ 3 (mod 13)。解為 x ≡ 3 (mod 13)。方法二系數化簡法觀察方程 5x ≡ 2 (mod 13)。因為5比較小我們可以嘗試給2加上13的倍數使其能被5整除。 2 mod 13 2。我們看2, 15, 28, 41, 54... 哪個能被5整除15可以。所以 5x ≡ 15 (mod 13)。 由于5和13互質兩邊可以消去5得到 x ≡ 3 (mod 13)。方法三枚舉法模數小的時候有效因為模13解x就在0到12之間。代入檢查 x0 - 0≠2; x1-5≠2; x2-10≠2; x3-15≡2 (mod 13)。找到解x3。對比與選擇方法一最通用、可編程。方法二需要一點觀察但有時很快。方法三僅適用于模數非常小的情況。掌握方法一是根本。7. 常見陷阱、疑難排查與編程實現要點在實際應用和解題中以下幾個坑點需要特別警惕。7.1 除法消去律的誤用這是最常見的錯誤。牢記準則在同余式 ac ≡ bc (mod m) 中不能直接消去c。正確做法計算 d gcd(c, m)。如果 d1即c與m互質則可以消去c得到 a ≡ b (mod m)。如果 d1則消去c后模數需要除以d。即 a ≡ b (mod m/d)。示例糾錯解 6x ≡ 18 (mod 20)。錯誤兩邊除以6得 x ≡ 3 (mod 20)。正確gcd(6,20)2。兩邊及模數同除以2得 3x ≡ 9 (mod 10)。此時gcd(3,10)1可以消去3得到 x ≡ 3 (mod 10)。所以原方程的解是 x ≡ 3, 13 (mod 20)。在模20下有兩個解。7.2 負數取模的處理在編程中不同語言對負數取模的結果定義可能不同。在數學的同余理論中我們通常使用最小非負剩余系余數在0到m-1之間。例如-17 mod 5 在數學上等于多少 -17 (-4)*5 3所以余數是3。即 -17 ≡ 3 (mod 5)。但在一些編程語言如C/C, Java中-17 % 5的結果可能是 -2。這會導致基于同余的算法出錯。編程避坑指南 在實現同余相關算法時務必自己實現一個取模函數確保結果是非負的。def mod(a, m): 返回 a mod m 的最小非負剩余 return ((a % m) m) % m # 示例 print(mod(-17, 5)) # 輸出 3 print(mod(17, 5)) # 輸出 27.3 大數運算與溢出問題在計算乘法逆元、中國剩余定理的構造解或者模冪運算時中間結果可能非常大超出編程語言中整數類型的范圍如32位或64位整數溢出。解決方案使用大整數庫Python的整數天生支持大數無需擔心。在Java中使用BigInteger在C中可以考慮__int128或第三方庫。及時取模在計算過程中充分利用模運算的性質(a*b) mod m [(a mod m) * (b mod m)] mod m及時對中間結果取模防止數值膨脹。快速模冪算法計算 a^b mod m 時不要先算a^b再取模。使用快速冪算法在乘法的每一步都進行取模。def fast_pow_mod(base, exp, mod): result 1 while exp 0: if exp 1: # 如果指數是奇數 result (result * base) % mod base (base * base) % mod exp 1 # 指數右移一位除以2 return result這個算法的時間復雜度是O(log exp)能高效計算巨大的指數模運算。7.4 中國剩余定理模數不互質的處理流程當模數不互質時合并法是通用解法。這里給出一個清晰的算法步驟總結便于編程實現初始化當前解為 x ≡ a1 (mod m1)。對于 i 從 2 到 k a. 設當前解為 x ≡ A (mod M)下一個方程為 x ≡ ai (mod mi)。 b. 聯立得x A M * t代入下式A Mt ≡ ai (mod mi) Mt ≡ (ai - A) (mod mi)。 c. 令 d gcd(M, mi)。解此關于 t 的同余方程。 d. 若 d 不能整除 (ai - A)則整個方程組無解返回。 e. 否則解得 t ≡ t0 (mod mi)其中 mi mi / d。 f. 更新解新的 A A M * t0新的 M lcm(M, mi) M * mi / d M * mi。 g. 新的同余式為 x ≡ A (mod M)。循環結束最終解為 x ≡ A (mod M)。這個流程可以穩妥地處理任意模數的同余方程組無論是否互質。同余的魅力在于它將無限的整數世界映射到了一個有限的、結構清晰的循環系統上。從檢查銀行卡號是否正確到讓哈希表飛起來再到守護我們網絡通信的安全這套古老的“時鐘算術”始終在幕后高效運轉。掌握它不僅是解開一道數學題更是獲得了一把理解計算機世界中許多核心機制的鑰匙。當你再看到%這個符號時希望你能想起這背后連接著一個豐富、深刻且極其有用的數學天地。