# 第 66 題：模反元素 [返回所在分頁 1](https://ocme.evemisslab.com/zh-Hant/questions/) [← 逐題詳解目錄](https://ocme.evemisslab.com/zh-Hant/questions/) · [原題批次](https://ocme.evemisslab.com/zh-Hant/practice/batch-20261014-advance-20261103-r07-modular-inverse-foundations/#q-20261014-advance-20261103-r07-modular-inverse-0066) 本頁是已完成第二對話 AI 數理與中英語義覆核的教學詳解，只支持本題明示的模型與前提。沒有人工審查或新 Lean 證明，也不提升原題或 MKO 的 Canonical 真值狀態。 P250-0066 · q-20261014-advance-20261103-r07-modular-inverse-0066 ## 原題與已知條件 整數a與模數n大於等於2的exact Euclidean arithmetic。操作=modinv-normalized-inverse；資料={"a":5,"n":42}。請依 [a,n,inverse,product_mod_n,valid,uniqueness] 欄序回答。 - G001 — 整數a與模數n大於等於2的exact Euclidean arithmetic。操作=modinv-normalized-inverse；資料={"a":5,"n":42}。請依 [a,n,inverse,product_mod_n,valid,uniqueness] 欄序回答。 ## 定義與適用範圍 整數模數 n≥2 且 gcd(a,n)=1；唯一性指模類及指定區間的代表元。 - [mko-modular-inverse](https://ocme.evemisslab.com/zh-Hant/mko/mko-modular-inverse/) ## 逐步推導 S001 · implies操作前 a=5, modulus=42 操作後 n=42≥2; seek u with 5u≡1 (mod 42) 條件：無 先固定模數與逆元條件，目標不是整數乘積恰等於 1。 步驟識別與依賴規則：inverse_definition · 依賴：G001 S002 · implies操作前 divide 5 by 42 操作後 5=0·42+5 條件：0≤5<42 商為 0、餘數為 5；每次用前一除數與餘數繼續。 步驟識別與依賴規則：euclidean_division · 依賴：G001, S001 S003 · implies操作前 divide 42 by 5 操作後 42=8·5+2 條件：0≤2<5 商為 8、餘數為 2；每次用前一除數與餘數繼續。 步驟識別與依賴規則：euclidean_division · 依賴：G001, S002 S004 · implies操作前 divide 5 by 2 操作後 5=2·2+1 條件：0≤1<2 商為 2、餘數為 1；每次用前一除數與餘數繼續。 步驟識別與依賴規則：euclidean_division · 依賴：G001, S003 S005 · implies操作前 divide 2 by 1 操作後 2=2·1+0 條件：0≤0<1 商為 2、餘數為 0；每次用前一除數與餘數繼續。 步驟識別與依賴規則：euclidean_division · 依賴：G001, S004 S006 · implies操作前 last nonzero Euclidean remainder 操作後 gcd(5,42)=1; 5·(17)+42·(-2)=1 條件：無 沿除法鏈保留整數線性組合，得到實際的 Bézout 等式。 步驟識別與依賴規則：bezout_identity · 依賴：G001, S005 S007 · implies操作前 5·(17)+42·(-2)=1 操作後 17 mod 42=17; 0≤17<42 條件：無 Bézout 的 a 係數已代表逆元類，再取指定區間內的代表元。 步驟識別與依賴規則：normalize_residue · 依賴：G001, S006 S008 · calculation操作前 a·u := mul(5, 17) 操作後 a·u = 85 條件：無 將原 a 與正規化逆元相乘。 步驟識別與依賴規則：exact_rational_arithmetic · 依賴：G001, S007 S009 · implies操作前 a·u=85 操作後 85=2·42+1 ⇒ a·u mod n=1 條件：無 乘積與 1 的差是模數的整數倍，故逆元條件成立。 步驟識別與依賴規則：congruence_check · 依賴：G001, S008 S010 · implies操作前 a·v≡a·u≡1 (mod n), gcd(a,n)=1 操作後 n divides v−u; if 0≤u,v