最小公約數和最大公約數定義?這是一系列關于數論的介紹性文章，目的在于推廣數學知識，拓展讀者的數學思維至于為什麼用圖文而不是視頻？圖文有三個優越性：一是圖文數據量小，節省學習時間；二是有助于個人主動思考；三是文字裡的關鍵字，可以方便讀者查閱相關資料，接下來我們就來聊聊關于最小公約數和最大公約數定義?以下内容大家不妨參考一二希望能幫到您!

最小公約數和最大公約數定義

這是一系列關于數論的介紹性文章，目的在于推廣數學知識，拓展讀者的數學思維。至于為什麼用圖文而不是視頻？圖文有三個優越性：一是圖文數據量小，節省學習時間；二是有助于個人主動思考；三是文字裡的關鍵字，可以方便讀者查閱相關資料。

我們在勾股數組的研究中已經看到，整除性與因數分解的概念是數論的重要工具。在本章中我們來更進一步地考察這些想法。

假設m與n是整數，。 m整除n指n是m的倍數，即存在整數k使得n=mk。如果m整除n，我們記為m I n。類似地，如果m不整除n，則記為。

例如,由于，，所以, 。 6的因數是1，2，3。另一方面，由于沒有5的倍數等于7，所以。

整除n的數稱為n的因數。

如果已知兩個整數，我們可以求其公因數，即整除它們兩個的數。例如,由于且，所以4是12與20的公因數。注意4是12與20的最大公因數。類似地，3是18與30的公因數，但不是最大的，因為6也是公因數。兩個數的最大公因數經常出現在我們的數論讨論中，是個極其重要的量。

兩個數a與b(不全為零)的最大公因數是整除它們兩個的最大數，記為gcd(a, b)。如果gcd(a, b) =1，我們稱a與6互素。

在前述的兩個例子中,

gcd(12,20) = 4 且 gcd (18,30) = 6.

另一個例子是

gcd(225, 120) = 15.

通過分解因數與，可驗證答案是正确的，但是一般地，要計算a與b的最大公因數，分解a與b不是有效的方法。

求兩個數最大公因數的最有效方法是歐幾裡得算法，這是由直到餘數為零的一系列帶餘除法組成的。在叙述一般方法前，我們用兩個例子來說明。

作為第一個例子，我們計算gcd(36, 132)。第一步是132除以36得商3與餘數24。我們将此記作

132 = 3 x 36 24.

第二步是取36，用前一步的餘數24除36得

36 = 1 x 24 12.

下一步,用12除24求得餘數0,

24 = 2 x 12 0.

歐幾裡得算法說明當得到餘數0時，則前一步的餘數就是最初兩個數的最大公因數。所以在這種情況我們求得gcd(132, 36) =12。

下面做一個更大的例子，計算

gcd(1160718174,316258250)。

做這種大數例子是為了說明計算最大公因數的歐幾裡得算法遠比因數分解法更有效。由1160718174除以316258250開始，得商3和餘數211943424，接下來取316258250，用211943424去除它，繼續進行這個過程直到得到餘數0為止。具體計算見下表:

1160718174 = 3 x 316258250 211943424

316258250 = 1 x 211943424 104314826

211943424 = 2 x 104314826 3313772

104314826 = 31 x 3313772 1587894

3313772 = 2 x 1587894 137984

1587894 = 11 x 137984 70070

137984 = 1 x 70070 67914

70070 = 1 x 67914 2156

67914 = '31 x 2156 |1078|最大公因數

2156 = 2 x 1078 0

注意如何在每一步用A除以B得到商Q和餘數R。換句話說，

A= Q x B R.

然後在下一步用數B與R代替原來的A與B，繼續此過程直到得到餘數0為止。此時，前一步的餘數R就是最初兩個數的最大公因數。所以，上述計算表明

gcd(1160718174,316258250) = 1078.

通過驗證1078确實是公因數可部分地檢驗我們的計算(一種好想法)。事實上，

1160718174 = 1078 x 1076733, 316258250 = 1078 x 293375.

下面我們分析歐幾裡得算法。對于一般情形，有

如果令且，則每行形如

.

為什麼最後的非零餘數r，是a與b的公因數呢?我們從最底行開始向上分析。最後一行，表明整除。則前一行

表明整除，因為它整除與。現在觀察再前面一行，我們已知道整除與，所以也得知整除。逐行上移，當到達第二行時，我們就已經知道整除與。于是第二行表明整除b。最後到達頂行，利用整除與b可得到整除a的結論。這就完成了最後非零餘數是a與b公因數的證明。

但是，為什麼是a與b的最大公因數呢？假設d是a與b的任意公因數，讓我們回到等式表。從第一個等式和d整除a與b，可得d也整除。則第二個等式表明d一定整除。逐行繼續下去，在每一步我們得到d整除前兩個餘數與，則前行可知d也整除下一個餘數。最終到達倒數第二行，至此就得到d整除的結論。因此我們已證明如果d是a和b的任意公因數， 則d整除。于是， 一定是a與b的最大公因數。

綜上所述，我們驗證了歐幾裡得算法的确算出了最大公因數，它的重要性使得有必要把它形成一個定理。

定理5.1(歐幾裡得算法) 要計算兩個整數a與b的最大公因數，先令且，然後計算相繼的商和餘數

直到某餘數為0。最後的非零餘數就是a與b的最大公因數。

為什麼歐幾裡得算法總能完成任務呢？換句話說，我們知道最後的非零餘數就是所希望的最大公因數，但是為什麼一定會得到确實等于0的餘數呢？這并不是一個無聊的問題，因為容易給出不終止的算法；甚至存在着很簡單的算法，使得人們不知道它是否會終止。幸運的是，容易看出歐幾裡得算法總會終止，理由很簡單，每次計算商和餘數，

A= Q x B R，

餘數在0與B-1之間。這是顯然的，因為如果，則可以再加1到商Q，并從R減去B。所以，歐幾裡得算法中的餘數不斷減小：

但是，所有餘數大于等于0，因此得到非負整數的嚴格遞減序列。最後必然達到等于0的餘數；事實上，顯然至多經過6步就會得到餘數0。幸運的是，歐幾裡得算法遠比這更有效。歐幾裡得算法的步數至多是b的位數的7倍。所以，在計算機上當a與b有幾百位甚至幾千位時，很容易計算 gcd(a, b)。

總結，在歐幾裡得算法裡，有幾個概念需要我們理解：

1. 證明最大公約數時，分了兩步，先證明是公約數，再證明是最大的公約數。這裡利用了一個包含的概念，最大公約數首先是公約數。
2. 歐幾裡得算法的可停止性，如果算法不能停止，或不能快速停止，也不是一個好的算法。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!