第 69 題：模反元素

原題與已知條件

整數a與模數n大於等於2的exact Euclidean arithmetic。操作=modinv-normalized-inverse；資料={"a":2,"n":45}。請依 [a,n,inverse,product_mod_n,valid,uniqueness] 欄序回答。

• G001 — 整數a與模數n大於等於2的exact Euclidean arithmetic。操作=modinv-normalized-inverse；資料={"a":2,"n":45}。請依 [a,n,inverse,product_mod_n,valid,uniqueness] 欄序回答。

定義與適用範圍

整數模數 n≥2 且 gcd(a,n)=1；唯一性指模類及指定區間的代表元。

• mko-modular-inverse

逐步推導

a=2, modulus=45

n=45≥2; seek u with 2u≡1 (mod 45)

divide 2 by 45

2=0·45+2

divide 45 by 2

45=22·2+1

divide 2 by 1

2=2·1+0

last nonzero Euclidean remainder

gcd(2,45)=1; 2·(-22)+45·(1)=1

2·(-22)+45·(1)=1

-22 mod 45=23; 0≤23<45

a·u := mul(2, 23)

a·u = 46

a·u=46

46=1·45+1 ⇒ a·u mod n=1

a·v≡a·u≡1 (mod n), gcd(a,n)=1

n divides v−u; if 0≤u,v<n then u=v

逐步反向核對

• S009 · premise_and_result_audit — 唯一的是模類及指定區間的代表；u+kn 仍是其他整數代表。
• S008 · premise_and_result_audit — 商數為整數，且餘數確實為 1。
• S007 · premise_and_result_audit — 以精確有理數重算 a·u，不以小數近似替代。
• S006 · premise_and_result_audit — 只正規化逆元代表，不要求 Bézout 的兩個係數都在該區間。
• S005 · premise_and_result_audit — 直接乘開等式兩邊核對，不只相信 gcd 標記。
• S004 · premise_and_result_audit — 除法等式與 0≤餘數<除數都須成立。
• S003 · premise_and_result_audit — 除法等式與 0≤餘數<除數都須成立。
• S002 · premise_and_result_audit — 除法等式與 0≤餘數<除數都須成立。
• S001 · premise_and_result_audit — 必須先確認 gcd(a,n)=1，才有此模反元素。

結論

(2, 45, 23, 1, 是, unique_modulo_n)

逆元代表是 23，唯一性以模 45 解讀。

本題覆核與來源綁定

覆核日期：2026-10-24

原題、答案、步驟表達式、數值 AST 與既有歷史保持原樣；原來的候選狀態屬於來源歷史，不覆寫為形式化證明。