第 57 題：模反元素

原題與已知條件

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

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

定義與適用範圍

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

• mko-modular-inverse

逐步推導

a=2, modulus=33

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

divide 2 by 33

2=0·33+2

divide 33 by 2

33=16·2+1

divide 2 by 1

2=2·1+0

last nonzero Euclidean remainder

gcd(2,33)=1; 2·(-16)+33·(1)=1

2·(-16)+33·(1)=1

-16 mod 33=17; 0≤17<33

a·u := mul(2, 17)

a·u = 34

a·u=34

34=1·33+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, 33, 17, 1, 是, unique_modulo_n)

逆元代表是 17，唯一性以模 33 解讀。

本題覆核與來源綁定

覆核日期：2026-10-24

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