第 68 題：模反元素

原題與已知條件

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

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

定義與適用範圍

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

• mko-modular-inverse

逐步推導

a=3, modulus=44

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

divide 3 by 44

3=0·44+3

divide 44 by 3

44=14·3+2

divide 3 by 2

3=1·2+1

divide 2 by 1

2=2·1+0

last nonzero Euclidean remainder

gcd(3,44)=1; 3·(15)+44·(-1)=1

3·(15)+44·(-1)=1

15 mod 44=15; 0≤15<44

a·u := mul(3, 15)

a·u = 45

a·u=45

45=1·44+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

逐步反向核對

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

結論

(3, 44, 15, 1, 是, unique_modulo_n)

逆元代表是 15，唯一性以模 44 解讀。

本題覆核與來源綁定

覆核日期：2026-10-24

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