第 368 題：模反元素

原題與已知條件

整數a與模數n大於等於2的exact Euclidean arithmetic。操作=modinv-extended-euclid；資料={"a":3,"n":44}。請依 [a,n,gcd,x,y,bezout_value,classification] 欄序回答。

• G001 — 整數a與模數n大於等於2的exact Euclidean arithmetic。操作=modinv-extended-euclid；資料={"a":3,"n":44}。請依 [a,n,gcd,x,y,bezout_value,classification] 欄序回答。

定義與適用範圍

在 |a| 與 n 上執行擴展歐幾里得並還原 a 的符號；係數只是 Bezout 證書，不唯一。

• mko-modular-inverse

逐步推導

a=3; n=44≥2

compute gcd and a Bezout certificate before inversion

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

a·x := mul(3, 15)

a·x = 45

n·y := mul(44, -1)

n·y = -44

Bezout value := sum(45, -44)

Bezout value = 1

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

inverse representative=15; 3·15≡1 (mod 44)

逐步反向核對

• S009 · premise_and_result_audit — 核對整數等式、餘數範圍與 gcd 條件，不把同餘當整數相等。
• S008 · premise_and_result_audit — 以精確有理數重算 Bezout value，不以小數近似替代。
• S007 · premise_and_result_audit — 以精確有理數重算 n·y，不以小數近似替代。
• S006 · premise_and_result_audit — 以精確有理數重算 a·x，不以小數近似替代。
• S005 · premise_and_result_audit — 核對整數等式、餘數範圍與 gcd 條件，不把同餘當整數相等。
• S004 · premise_and_result_audit — 核對整數等式、餘數範圍與 gcd 條件，不把同餘當整數相等。
• S003 · premise_and_result_audit — 核對整數等式、餘數範圍與 gcd 條件，不把同餘當整數相等。
• S002 · premise_and_result_audit — 核對整數等式、餘數範圍與 gcd 條件，不把同餘當整數相等。
• S001 · premise_and_result_audit — 核對整數等式、餘數範圍與 gcd 條件，不把同餘當整數相等。

結論

(3, 44, 1, 15, -1, 1, Bezout_equals_one)

上述完整代值與條件核對得到原題答案；欄位次序及真假標記保持原始合約。

本題覆核與來源綁定

覆核日期：2026-10-26

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