# 概念推導導讀

299 份概念教學導讀；另有 36,000 題逐題詳解，兩者分開查找。

[搜尋全部題目與詳解 →](/zh-Hant/explore/)

1共 1 項 · 第 1／1 頁



概念導讀



## [最大公因數與互質：以整除刻畫驗證歐幾里得算法](/zh-Hant/derivations/derivation-mko-gcd-coprime-01/?from=%2Fzh-Hant%2Fderivations%2F%3Fq%3Dmko-gcd-coprime)

依 MKO 的整除刻畫（d∣a、d∣b，且每個公因數 c 都整除 d）：(1) 證明滿足刻畫的 d 至多一個；(2) 證明歐幾里得算法每一步保持公因數集合且必會停止，並以它算出 gcd(84,36)=12，再直接驗證 12 滿足刻畫；(3) 說明公因數 6 不是 gcd；(4) 算出 gcd(8,15)=1，說明 8 與 15 互質但都不是質數；(5) 處理含 0 的情形 gcd(0,1)=1、gcd(0,6)=6、gcd(0,0)=0。

最大公因數與互質

derivation-mko-gcd-coprime-01





1共 1 項 · 第 1／1 頁