第 71 題：模反元素

原題與已知條件

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

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

定義與適用範圍

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

• mko-modular-inverse

逐步推導

a=2, modulus=47

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

divide 2 by 47

2=0·47+2

divide 47 by 2

47=23·2+1

divide 2 by 1

2=2·1+0

last nonzero Euclidean remainder

gcd(2,47)=1; 2·(-23)+47·(1)=1

2·(-23)+47·(1)=1

-23 mod 47=24; 0≤24<47

a·u := mul(2, 24)

a·u = 48

a·u=48

48=1·47+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, 47, 24, 1, 是, unique_modulo_n)

逆元代表是 24，唯一性以模 47 解讀。

本題覆核與來源綁定

覆核日期：2026-10-24

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