Euclidean演算法

數學敘述

逐步驗a=bq+r與0<=r<|b|，把gcd invariant、嚴格下降終止及最終非負gcd分開。extended版本回代並重驗ax+by=gcd；零輸入採gcd(0,0)=0且不執行除以零。

代表公式（精確 TeX）

a=b(q)+r

成立條件

• 輸入為安全範圍內整數，主鏈對絕對值執行。
• Bezout係數依原輸入符號回代並精確驗式。

符號作用域

• q — 商
• r — 餘數

直觀、定義與常見誤解

每一步保留gcd並嚴格降低非負餘數。

最後非零餘數給非負gcd。

Bezout係數需要extended回代證書，不能只由gcd值猜測。

只算出一個數便聲稱演算法正確，或在零除數上繼續做帶餘除法。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 最大公因數與互質 — 目標gcd與互質判準。
• 自然數整除 — 帶餘除法與整除。
• 算法正確性 — invariant與終止分離。

驗證界線

只處理exact整數演算法；不宣稱位元複雜度最佳性。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。

下一個義務

加入binary gcd與模反元素構造。

同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。