第 72 題：模反元素

原題與已知條件

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

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

定義與適用範圍

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

• mko-modular-inverse

逐步推導

a=5, modulus=48

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

divide 5 by 48

5=0·48+5

divide 48 by 5

48=9·5+3

divide 5 by 3

5=1·3+2

divide 3 by 2

3=1·2+1

divide 2 by 1

2=2·1+0

last nonzero Euclidean remainder

gcd(5,48)=1; 5·(-19)+48·(2)=1

5·(-19)+48·(2)=1

-19 mod 48=29; 0≤29<48

a·u := mul(5, 29)

a·u = 145

a·u=145

145=3·48+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

逐步反向核對

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

結論

(5, 48, 29, 1, 是, unique_modulo_n)

逆元代表是 29，唯一性以模 48 解讀。

本題覆核與來源綁定

覆核日期：2026-10-24

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