?? ??? ?歐幾里得算法，也叫做輾轉相除法，gcd(a, b) = gcd (b, a%b)，即a和b最大公約數等于b和a%b的最大公約數。相信大家都會用，但是很多人不知道為什么，我也看了很多文章，寫的都不太相同，這里我說說我自己的證明過程：
?? ??? ?這里的證明我分為兩步求證：
?? ??? ?1.求證：a和b的公約數等于b和a%b的公約數；
?? ??? ?2.求證：b和a%b的公約數是最大公約數。
?? ??? ?
?? ??? ?求證1：a和b公約數等于b和a%b的公約數
?? ??? ?為了方便大家看，我先把下面用到的變量注一下：
?? ??? ??? ?n：公約數?? ??? ?m：a%b?? ??? ??? ?k、k'、k''：都是常數
?? ??? ?（先不看，跟著我的思路走，過程中忘了哪個變量是干什么的再回來看一下）
?? ??? ?這里設一個n，n是a和b的一個公約數，所以有?
?? ??? ??? ??? ??? ?a/n = k' , b/n = k'' (k'和k''都是常量) ? ? --------------①
?? ??? ?這里既然證明a和b最大公約數等于b和a%b的最大公約數，那么這里你還需要有這三個數，a和b是已知的，那么這里我們設m = a % b ? ?(m ≠ 0 ，若m=0，b一定是a和b的最大公約數)，那么
?? ??? ??? ??? ??? ?a = kb + m ?(k是一個常量) ? --------------------------②
?? ??? ?②變形得：
?? ??? ??? ??? ??? ?m = a - kb ? -----------------------------------------------③
?? ??? ?③等式兩邊同時除以n得：
?? ??? ??? ??? ??? ?m/n = a/n - k(b/n) ? ?-------------------------------------④
?? ??? ?①④結合，得：
?? ??? ??? ??? ??? ?m/n = k' - kk'' ?--------------------------------------------⑤
?? ??? ?看⑤式中，k、k'、k''都是常數，所以m/n是一個常數，所以n也是m的約數，所以說n是a、b、m三個的公約數，那么可以得到n也是b和a%b的公約數。
?? ??? ?看到這我們已經得出了結論一：a和b公約數等于b和a%b的公約數。
? ? ? ??
? ? ? ? 下面只需證明結論一中的公約數是他們的最大公約數即可：
? ? ? ? 求證2：公約數是最大公約數
?? ??? ?首先，根據結論一，我們可以找出多組數據，使得他們都有一個共同的約數n
?? ??? ?例如：(a, b)?? ??? ?(b, a%b)?? ??? ?(a%b, b%(a%b)) ? ?... ? ? ? 他們每組都有一個公約數n
?? ??? ?如此一直向下，這里我們可以設（A， B）的公約數為n，每組數據都用（A， B）來更新
?? ??? ?（每次A都變為原來的B，B變成原來的A%B）
?? ??? ?因為A%B總是小于B，如果一直更新下去，A%B總有變成0的時候，也就是A % B = 0
?? ??? ?設當前組合為(A，B)，且滿足條件(A % B = 0)，這時我們可以得到組合(A，B)的最大公約數為B
?? ??? ?現在我們將上面那一行數據延伸：(a, b)?? ??? ?(b, a%b)?? ??? ?(a%b, b%(a%b)) ? ?...?? ?(kA + B, A)?? ?(A, B)?? ??? ?
?? ??? ?上面這一組數據都有一個公約數n，那么我們只需證明(A, B)的最大公約數與(kA + B, A)的最大公約數相等
?? ??? ?現在已知B是(A, B)的最大公約數，又已知(kA + B, A)?? ?(A, B)有相同的約數n
?? ??? ?我們此時假設(A, B)的這個約數n就是最大公約數B，那么只需證明B也是(kA + B, A)的最大公約數即可得出結論這里的公約數n是最大公約數。
?? ??? ?那么也就是求證：B是(kA + B, A)的最大公約數
?? ??? ??? ??? ?已知A % B = 0得：
?? ??? ??? ??? ??? ??? ??? ?A = ?k'B ? ----------------------------------⑥
?? ??? ??? ??? ?結合⑥得：
?? ??? ??? ??? ??? ??? ??? ?kA + B = (kk'+1)B ? ---------------------⑦
?? ??? ??? ??? ?根據⑥⑦我們可以得出(kA + B, A)的公約數為：B以及B的約數
?? ??? ??? ??? ?所以(kA + B, A)的最大公約數為B
?? ??? ?得出結論：a和b最大公約數等于b和a%b的最大公約數，也就是歐幾里得算法gcd(a, b) = gcd (b, a%b)。
?? ??? ?
?? ??? ?
?? ??? ?
?? ??? ??? ??? ??? ?

總結

以上是生活随笔為你收集整理的欧几里得算法证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。