有界整數同餘資訊的精確碼距、錯誤及擦除恢復臨界界：香港數學資優教育的可驗證數論延伸

摘要

在數學競賽與資優數論延伸中，中國剩餘定理常用於由多條同餘恢復未知整數。然而，如果其中一條餘數被誤抄，原整數能否唯一恢復，須先限定可能的整數範圍。本文研究整數 $0\le x<N$ 在一組兩兩互素模數下的冗餘同餘碼。對遞增模數 $m_1<\cdots<m_k$，定義前綴乘積 $P_j=\prod_{i=1}^j m_i$。我們推導最小 Hamming 距離 $d_{\min}=k-\max\{j:P_j<N\}$ 的直接有限整數證書，給出至多 $t$ 條錯誤與 $e$ 條已知位置擦除下唯一恢復的精確充要界 $N\le P_{k-2t-e}$，並構造剛越過界線時的不可辨識反例。從模數子集直接套用中國剩餘定理，可得到有成功及失敗判據的有限解碼演算法。兩套數學結構不同的碼距核驗、基礎 CRT 解碼與聯合錯誤擦除 CRT 解碼均通過；測試例均屬人工設計，沒有香港學生數據。已存在冗餘剩餘數系及中國剩餘定理糾錯研究，故本文僅定位為具有完整端點證書的教學特化及研究工作論文，不宣稱創立新型糾錯碼或具有實證教學效益。

Abstract

The Chinese remainder theorem reconstructs an integer from modular residues, but recovery from erroneous residues requires a bounded message domain. For pairwise coprime ordered moduli $m_1<\cdots<m_k$ and messages $0\le x<N$, we derive an elementary exact certificate for the minimum Hamming distance of the residue code. Writing $P_j$ for the product of the $j$ smallest moduli, the distance equals $k-\max\{j:P_j<N\}$. Consequently, uniform unique recovery under at most $t$ arbitrary wrong residues and $e$ known-position erasures holds precisely when $N\le P_{k-2t-e}$, provided $2t+e<k$. We give boundary counterexamples and a constructive subset-CRT decoder, with independently implemented finite-instance checks. Prior work in redundant residue systems and error-correcting CRT codes is acknowledged; the contribution is a transparent, sharp bounded-domain specialization and proof-oriented enrichment proposal for Hong Kong gifted mathematics. No global novelty or measured learning benefits are claimed.

**中文關鍵詞：**香港數學資優教育；中國剩餘定理；冗餘同餘；碼距；錯誤更正；擦除；精確端點；可重現數學驗證

English keywords: Hong Kong gifted mathematics; Chinese remainder theorem; redundant residues; Hamming distance; error correction; erasures; sharp threshold; reproducible proof

1. 引言

從數學奧林匹克的數論解題觀點來看，知道整數除以數個互素整數後的餘數，可以反過來求出其在乘積週期內的唯一值。這一結論的關鍵條件是：所有餘數都正確、模數兩兩互素，以及未知數已限定於不超過總模數乘積的範圍。若誤把某一個餘數抄寫成另一個合法餘數，直接套用中國剩餘定理通常會得到另一個同樣滿足所抄資料、卻可能錯誤的整數。因此解題前先回答「最多能容許幾條抄寫錯誤」是一個比直接計算餘數更高階的問題。

香港教育局設有香港數學奧林匹克官方資訊頁及學校資優教育網絡。本文使用這項制度背景說明資優數論增潤的可能場景；不能據此推論香港數學奧林匹克正式試卷必有相關題型，更不代表 HKDSE 必修範圍。數論編碼與錯誤恢復均屬延伸研究。若要聲稱這種延伸促進學習，還需香港學生或教師資料、測量工具及研究倫理審批。

研究問題分成四層：第一，哪些模數組合在給定範圍下保證兩個不同整數產生足夠多個不同餘數？第二，這項保證如何隨整數上界 $N$ 改變，尤其在乘積的整數端點？第三，已知位置的資料遺漏與未知位置的錯誤能否合併給出精確界線？第四，如何把證明轉化為不需要搜尋所有可能整數的可查核解碼步驟？

本文完全使用構造的有限整數，不提出虛構的競賽表現或學生成績。所謂「最小」「最大」「精確」，只針對明確寫出的代數模型；文獻是否已有相同形式必須另作全文查新。

2. 文獻綜述與新穎性界線

Goldreich、Ron 與 Sudan（2000）已直接研究 Chinese remaindering with errors，將多餘模數的同餘表示當作可更正錯誤的編碼，並研究更有效的解碼演算法。其 ECCC 技術報告可追溯至 1998 年，會議版本則於 1999 年發表。Xiao 等（2016）亦研究冗餘剩餘數系的錯誤控制演算法，Xiao、Huang、Ye 與 Xiao（2017）則研究中國剩餘定理的穩健恢復與動態範圍取捨。故本文不可能把「CRT 有糾錯能力」「最小距離決定更正容量」「使用多餘模數」當作學術首次。實際可識別的研究產出是針對任意整數上界 $N$（未必等於預先指定 $k$ 個模數乘積），寫出能用模數前綴乘積逐段核對的精確距離及錯誤、擦除門檻，配對一個不依賴外部程式庫的手算友善重建例子。這仍可能是既有碼距理論的直接推論。

表 1　既有研究與本稿工作之區別

英文檢索詞：Chinese remaindering with errors, redundant residue number systems minimum Hamming distance, robust Chinese remainder theorem dynamic range, residue error erasure decoding。中文檢索詞：中國剩餘定理 容錯 恢復, 冗餘剩餘數系 纠錯 模數, 香港 數學奧林匹克 同餘。檢索日為 2026-10-15；公開出版頁、機構書目及部分開放預印本可取得；未完成所有先例定理的全文優先權比較，也未系統覆蓋中文數學期刊。詳細候選選題紀錄見 Research_Cycle_012.md。

3. 理論框架與定義

取整數 $k\ge3$，並令 $2\le m_1<m_2<\cdots<m_k$ 為兩兩互素正整數（$\gcd(m_i,m_j)=1$，$i\ne j$）。對 $j=0,\ldots,k$，設 $P_0=1$、$P_j=\prod_{i=1}^{j}m_i$。選擇整數訊息上界 $2\le N\le P_k$，而 $X_N=\{0,\ldots,N-1\}$。定義同餘編碼

碼字不同坐標數的 Hamming 距離定義為

因 $N\le P_k$，對兩個不同訊息 $x,y$，差值 $0<|x-y|<P_k$ 不可能同時被全部模數整除，所以編碼 $R$ 單射且 $d_{\min}\ge1$。「錯誤」指某個坐標的合法餘數被完全替換為另一個值，位置未知；「擦除」指該坐標遺漏、遺漏位置已知。兩者合用 Hamming 模型，而非連續噪聲模型。

4. 研究方法及核驗安排

對任意兩不同訊息，研究其差 $h=|x-y|\in[1,N-1]$ 的可整除模數數量。互素性使任何 $j$ 個同時整除 $h$ 的模數之乘積必整除 $h$。按模數大小排序之後，當 $P_j\ge N$，不存在可以被 $j$ 個模數整除的非零容許差；反過來，只要 $P_j<N$，選 $h=P_j$ 就明確實現最少 $j$ 個相同坐標。這把看似須檢查所有碼字對的問題，化為前綴乘積的有限比較。

證明包括最小距離的雙方向論證、經典 Hamming 球不相交判準、錯誤和擦除的差異座標分配反例。計算核驗採四條方式：完整逐對比較碼字；不先形成碼字而枚舉非零差 $h$ 的整除性；對合法和單條錯誤的每個人工觀察向量，使用子集 CRT 實際求解；另以獨立求和式 CRT 程式全面檢查小型錯誤、擦除組合。所有檢查都採整數算術，輸出可重現 JSON；它們不是統計抽樣和教學效果檢驗。

5. 數學推導與分析

5.1 定理一：最小距離的精確前綴乘積表達式

令

**定理 1。**在第 3 節條件下，碼 $C_N$ 的最小 Hamming 距離精確等於

**證明。**先證明對所有不同的 $x,y\in X_N$，兩碼字至多有 $j_*$ 個相同坐標。令 $h=|x-y|\in[1,N-1]$。若兩碼字在指標集合 $S$ 的 $j$ 個坐標相同，則 $m_i\mid h$ 對每個 $i\in S$ 成立。由兩兩互素，$\prod_{i\in S}m_i\mid h$，故 $P_j\le\prod_{i\in S}m_i\le h<N$，必有 $j\le j_*$。因而 $d_H\ge k-j_*$。

要證明此下界真的可達，選 $x=0$ 和 $y=P_{j_*}$。由定義 $1\le P_{j_*}<N$，二者都是合法訊息。對 $i\le j_*$，$m_i\mid y$，因此至少 $j_*$ 條餘數相同，從而 $d_H(R(0),R(y))\le k-j_*$。兩側結合，式 (4) 成立。若 $j_*=0$，構造改為 $y=P_0=1$，且因所有 $m_i\ge2$，每個坐標都不同。證畢。

**邊界含意。**公式採 $P_j<N$，故在 $N=P_j$ 時差值 $h=P_j$ 仍未被容許；到 $N=P_j+1$ 才新增該差值。每經過一個前綴乘積端點，最小碼距便精確減少一。若把 $<$ 寫成 $\le$，便會在這些整數端點上得到錯誤結論。假定的 $N\le P_k$ 防止兩不同訊息具有完全相同的碼字。

5.2 定理二：至多 $t$ 條任意錯誤的充要門檻

定理 2。令 $t\ge0$ 是整數且 $2t<k$。對每一個訊息 $x\in X_N$ 和每一個由其碼字作至多 $t$ 條坐標替換所得的觀察向量，要保證原整數唯一可辨，必要且充分條件是

**證明。**若兩碼字最小距離 $d_{\min}\ge2t+1$，假設一個觀察向量同時與兩碼字相距至多 $t$，由 Hamming 三角不等式得兩碼字相距至多 $2t$，與下界矛盾。因此所有半徑 $t$ 的球兩兩不交，保證唯一恢復。

反過來，若某兩碼字相距 $d\le2t$，只在其差異坐標中，為觀察向量選取第一碼字在其中至多 $t$ 個位置的值，另餘位置選第二碼字的值；若 $d<2t$ 只需調整分配。由此可構造分別距兩碼字都不超過 $t$ 的觀察向量，唯一恢復失敗。故保證的充要條件為 $d_{\min}\ge2t+1$。代入定理 1，$k-j_*\ge2t+1$ 等價於 $j_*\le k-2t-1$，亦即 $P_{k-2t}\ge N$。證畢。

**精確性。**若 $N=P_{k-2t}+1\le P_k$，可直接取 $x=0$ 與 $y=P_{k-2t}$，其碼字在至少 $k-2t$ 個坐標相同，距離至多 $2t$。因此式 (5) 的 $N$ 端點在目前模型下不能無代價提高。若 $t=0$，條件退化為 $N\le P_k$，即 CRT 單射範圍；若 $N=1$，只有一個碼字，應另外處理，不適用最小兩不同碼字距離定義。

5.3 定理三：錯誤與已知擦除的聯合極限

定理 3。若有至多 $e$ 條擦除且知道其坐標位置，另外最多 $t$ 條剩餘坐標被替換為任意餘數，並有 $2t+e<k$，則對所有合法訊息及所有這類資料損壞均能唯一恢復的充要條件是

**證明。**一般碼的充要距離條件為 $d_{\min}\ge2t+e+1$。充分性：擦除至多 $e$ 個坐標後，兩原碼字剩下的距離仍至少 $d_{\min}-e\ge2t+1$；再更改各自至多 $t$ 條坐標，不會使同一個觀察資料同時符合兩個不同碼字。必要性：若存在碼字對之距離 $d\le2t+e$，擦除至多 $e$ 條這對碼字相異的位置，餘下至多 $2t$ 個不同位置可一分為二，由各自最多 $t$ 條替換造成同一個觀察資料，故不能保證唯一。代定理 1，即得 $j_*\le k-2t-e-1$，等價於式 (6)。證畢。

式 (6) 是傳統錯誤及擦除 Hamming 距離準則的模型特化，不能將其論述為新創的編碼一般原理。若 $2t+e\ge k$，在非單碼字的模型下不可能達到所需距離 $2t+e+1$；除非另外加入先驗資訊，不能保證該錯誤容量。模數非互素時，須將集合整除條件重新改用最小公倍數，式 (4) 至 (6) 並不照搬。

5.4 命題四：有限子集 CRT 解碼器與可檢查失敗證書

命題 4。當式 (5) 成立時，對觀察向量 $a=(a_1,\ldots,a_k)$，枚舉所有大小 $k-t$ 的指標子集 $S$，由子集餘數經 CRT 得唯一代表元 $y_S\in[0,M_S)$，$M_S=\prod_{i\in S}m_i$。只接受 $y_S<N$ 且 $d_H(R(y_S),a)\le t$ 的候選。若觀察真由合法碼字經至多 $t$ 條錯誤形成，這個方法存在且只有一個輸出，並等於原訊息。

**證明。**正確觀察坐標至少有 $k-t$ 條，所以存在一個枚舉子集 $S$ 只包含正確坐標。由模數排序，$M_S\ge P_{k-t}\ge P_{k-2t}\ge N$。原訊息 $x<N\le M_S$，且 $x$ 滿足 $S$ 中的每條同餘，故 CRT 的最小非負代表元 $y_S=x$，並通過全坐標距離檢查。唯一性由定理 2 已證：若另有 $y\ne x$ 通過相同距離測試，觀察向量與兩合法碼字各距至多 $t$，不可能。證畢。

此法的子集數量是 $\binom{k}{t}$；每組另需 CRT 同餘計算與全坐標核查。這可作數論增潤的手算流程，但沒有宣稱在大型參數下優於現存的 CRT 糾錯演算法。若輸入損壞超過容許限額，候選可能為零或多個；此時須報告資料不符保證，不可擅自選一個值。

已知擦除的解碼延伸。若擦除集合為 $E$ 且 $|E|\le e$，可在未擦除的 $k-|E|$ 個坐標中枚舉所有大小 $k-|E|-t$ 的子集；對每個子集求 CRT 代表元，僅保留落在 $X_N$ 並且在所有未擦除坐標中與觀察資料相異不超過 $t$ 處的候選。在式 (6) 成立時，至少有一個完全正確的枚舉子集，其模數乘積不少於 $P_{k-e-t}\ge P_{k-2t-e}\ge N$，故必定重建真實整數；由定理 3，通過檢查的候選只能有一個。這是定理 3 的構造性推論，其枚舉時間隨 $k,t$ 可能快速增長。

6. 研究結果：人工整數案例與雙門檻

選 $m=(3,5,7,11,13)$，全部兩兩互素；有 $P_0=1$、$P_1=3$、$P_2=15$、$P_3=105$、$P_4=1155$、$P_5=15015$。

表 2　人工模數組的精確整數範圍與碼距

在 $N=105$ 時，定理 2 保證可糾正一條錯誤。例如 $x=42$ 的碼字為 $(0,2,0,9,3)$；若誤將第 3 條餘數抄成 4，觀察向量變成 $(0,2,4,9,3)$，唯一符合至多一條錯誤且 $0\le x<105$ 的整數仍是 42。此處不需要假設哪一條抄錯，而是在所有合法訊息間判斷唯一性。

當 $N=106$，新增訊息 $x=105$，其碼字為 $(0,0,0,6,1)$，而 $x=0$ 的碼字為 $(0,0,0,0,0)$。兩者只在模數 11 與 13 的餘數不同。觀察向量 $(0,0,0,6,0)$ 與兩碼字各相距一，因此一條錯誤模型下已有兩個候選值。這個 $105\to106$ 的整數端點差異就是式 (5) 的尖銳性反例。

表 3　錯誤數 $t$、擦除數 $e$ 與最大安全訊息上界（人工例）

第二條見解是：能處理一條錯誤和能處理一條擦除的動態範圍不同。擦除位置已知，代價是只減少一個有效距離坐標；未知錯誤可同時改變兩個候選碼字在觀察資料中的可能分配，所以需要兩個距離餘量。這一區別是一般編碼理論已有性質，但可以藉此引導資優學習者由同餘式推導資訊冗餘。

**聯合門檻反例。**當 $t=e=1$ 時，$N=15$ 保證唯一恢復，但 $N=16$ 可取 $x=0,y=15$：其碼字分別為 $(0,0,0,0,0)$ 與 $(0,0,1,4,2)$。刪去模數 7 的坐標（位置已知），並保留觀察 $(0,0,\text{擦除},4,0)$，則該觀察在未擦除坐標中與兩碼字各只相異一處，故不能唯一恢復。這一反例亦由求和式 CRT 解碼器獨立核對。

表 4　可重現的四條人工數學核驗路徑

這些測試使用完全整數的人工資料；沒有 p 值、信賴區間或學生樣本，亦不能把測試 PASS 當作外部同行審查。通過只是對已列舉的小型模數和上界重新支持推導；對任意參數的一般結論仍依賴第 5 節數學證明。

7. 討論：可操作的香港數學資優增潤設計

本研究可設計為一條由初等數論通往資訊理論的四階問題序列。先要求學生在限定區間解標準同餘組，再加入額外模數並詢問是否所有餘數都必須正確；其後以兩個不同整數的差 $h$ 解釋何以同時同餘意味著乘積整除；最後分析 $N$ 越過前綴乘積門檻時，碼距為何突然下降。這些步驟的教學目的可以透過可觀察的評分題目定義，例如要求提供「能保證唯一恢復」的形式證明，以及「不能保證」時的具體兩個整數與觀察向量。

從課程層次而言，互素、最小公倍數、帶餘除法可作先修知識；Hamming 距離和錯誤擦除是高階增潤概念。若教師要移植至香港資優班，需檢查學習者是否已熟悉 CRT，以及具體班級是否適合以小型編碼問題建立數論模型。文中資料和例子均由研究者構造，絕不能據此說本方法比現有學法有效，或對某個年級有經證實的優勢。

為避免只考機械計算，建議理論上區分三種答卷：只給出經 CRT 得到的整數；能證明這個整數在指定錯誤容量內唯一；能構造超出容量時的不可辨反例。只有第二、三類能測到本文的核心「全稱保證」與「尖銳端點」推理。這只是未經學生評核驗證的研究設計提案，並非實驗發現。

8. 限制與待決問題

模型假設模數兩兩互素、可傳送整數從 0 開始且形成連續區間，錯誤按整個餘數坐標的任意值替換計算，擦除位置可識別。在非互素模數、模數本身亦可能錯、模數間相依、可用訊息為不連續子集、或存在實值近似殘差時，都必須重新推導；不能直接套用公式 (4) 至 (6)。四程式只有有限例驗證，未知能否揭露所有建模錯誤。子集枚舉解碼在 $k$ 或 $t$ 增加時可能昂貴，沒有大型效能比較。對學術新穎性的初步搜尋已識別經典直接先例，尚欠完整的最小距離公式優先權查核及中文期刊系統檢索。本文沒有真實香港競賽題、學習者數據或外部審稿。

9. 結論與後續研究

對訊息 $0\le x<N$ 和兩兩互素遞增模數，最小碼距完全由前綴乘積 $P_j$ 與整數端點 $N$ 的比較控制；至多 $t$ 條錯誤及 $e$ 條已知擦除的保證界精確是 $N\le P_{k-2t-e}$。這兩項屬可直接證明、可構造失敗證人的有界模型特化。它可連結香港數學資優延伸中的中國剩餘定理與資訊冗餘觀念，但並未確立全球首創性或香港教學成效。後續須實施系統性文獻優先權比對、擴展至非互素模數及非連續訊息集合，再於倫理合規條件下檢驗具體教學可行性。

參考文獻

Education Bureau. (n.d.). Mathematics education: Bulletin board [Official mathematics competitions information]. Government of the Hong Kong Special Administrative Region. Retrieved October 15, 2026, from https://www.edb.gov.hk/en/curriculum-development/kla/ma/bulletin/index.html

Education Bureau. (n.d.). Gifted education [Official school-based enrichment resources]. Government of the Hong Kong Special Administrative Region. Retrieved October 15, 2026, from https://www.edb.gov.hk/en/curriculum-development/curriculum-area/gifted/index.html

Education Bureau. (n.d.). Hong Kong Mathematics Olympiad [Official competition information]. Government of the Hong Kong Special Administrative Region. Retrieved October 15, 2026, from https://www.edb.gov.hk/en/curriculum-development/kla/ma/res/sa/hkmo-index.html

Goldreich, O., Ron, D., & Sudan, M. (2000). Chinese remaindering with errors. IEEE Transactions on Information Theory, 46(4), 1330–1338. https://doi.org/10.1109/18.850672

Xiao, H., Garg, H. K., Hu, J., & Xiao, G. (2016). New error control algorithms for residue number system codes. ETRI Journal, 38(2), 326–336. https://doi.org/10.4218/etrij.16.0115.0575

Xiao, H., Huang, Y., Ye, Y., & Xiao, G. (2017). Robustness in Chinese remainder theorem. arXiv preprint, arXiv:1708.04089. https://arxiv.org/abs/1708.04089