# Euclidean演算法

Euclidean演算法以精確帶餘除法、gcd invariant與嚴格餘數下降求最大公因數。

mko-euclidean-algorithm · algorithm · v0.10.0



## 數學敘述

逐步驗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值猜測。

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





## 已採用的推導導讀

[帶符號輸入的Euclid與回代](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-euclidean-algorithm-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [最大公因數與互質](https://ocme.evemisslab.com/zh-Hant/mko/mko-gcd-coprime/) — 目標gcd與互質判準。
- [自然數整除](https://ocme.evemisslab.com/zh-Hant/mko/mko-natural-divisibility/) — 帶餘除法與整除。
- [算法正確性](https://ocme.evemisslab.com/zh-Hant/mko/mko-algorithm-correctness/) — invariant與終止分離。





## 驗證界線

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

not_formalized

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





## 下一個義務

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





## 同源結構化資料

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

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/euclidean-algorithm.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-euclidean-algorithm/index.md)