# 第 62 題：模反元素 [返回所在分頁 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-0062) 本頁是已完成第二對話 AI 數理與中英語義覆核的教學詳解，只支持本題明示的模型與前提。沒有人工審查或新 Lean 證明，也不提升原題或 MKO 的 Canonical 真值狀態。 P250-0062 · q-20261014-advance-20261103-r07-modular-inverse-0062 ## 原題與已知條件 整數a與模數n大於等於2的exact Euclidean arithmetic。操作=modinv-normalized-inverse；資料={"a":3,"n":38}。請依 [a,n,inverse,product_mod_n,valid,uniqueness] 欄序回答。 - G001 — 整數a與模數n大於等於2的exact Euclidean arithmetic。操作=modinv-normalized-inverse；資料={"a":3,"n":38}。請依 [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=3, modulus=38 操作後 n=38≥2; seek u with 3u≡1 (mod 38) 條件：無 先固定模數與逆元條件，目標不是整數乘積恰等於 1。 步驟識別與依賴規則：inverse_definition · 依賴：G001 S002 · implies操作前 divide 3 by 38 操作後 3=0·38+3 條件：0≤3<38 商為 0、餘數為 3；每次用前一除數與餘數繼續。 步驟識別與依賴規則：euclidean_division · 依賴：G001, S001 S003 · implies操作前 divide 38 by 3 操作後 38=12·3+2 條件：0≤2<3 商為 12、餘數為 2；每次用前一除數與餘數繼續。 步驟識別與依賴規則：euclidean_division · 依賴：G001, S002 S004 · implies操作前 divide 3 by 2 操作後 3=1·2+1 條件：0≤1<2 商為 1、餘數為 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(3,38)=1; 3·(13)+38·(-1)=1 條件：無 沿除法鏈保留整數線性組合，得到實際的 Bézout 等式。 步驟識別與依賴規則：bezout_identity · 依賴：G001, S005 S007 · implies操作前 3·(13)+38·(-1)=1 操作後 13 mod 38=13; 0≤13<38 條件：無 Bézout 的 a 係數已代表逆元類，再取指定區間內的代表元。 步驟識別與依賴規則：normalize_residue · 依賴：G001, S006 S008 · calculation操作前 a·u := mul(3, 13) 操作後 a·u = 39 條件：無 將原 a 與正規化逆元相乘。 步驟識別與依賴規則：exact_rational_arithmetic · 依賴：G001, S007 S009 · implies操作前 a·u=39 操作後 39=1·38+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