本節書摘來自華章計算機《算法基礎》一書中的第2章，第2.2節，作者：（美）羅德·斯蒂芬斯（rod stephens）著，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視
兩個整數的最大公約數（greatest common divisor，gcd）是指兩個整數共有約數中最大的一個。例如，gcd(60，24)為12，因為12是60和24共有約數中最大的。（最大公約數也許看起來像一個深奧的功能，但是它實際上在加密程式中十分有用，這些加密程式被廣泛用于金融通信安全等領域。）
注 如果gcd(a，b)＝1，那麼a和b被稱作互質（relatively prime或coprime）。
一個找到最大公約數的方法是将兩個因數分解并且找到它們共有的因數。但是希臘數學家歐幾裡得在他著于公元前300年的論述《幾何原本》中記錄了一個更快捷的方法。以下僞代碼展示了這個算法的現代版。因為它是基于歐幾裡得的著作，這個算法被叫做歐幾裡得算法（euclidian algorithm或euclid抯 algorithm）：
例如，計算gcd(4831，3003)。表2-2展示了a、b和每一步b除以a的餘數m的值。
當b為0時，變量a即為最大公約數，本例中最大公約數為231。驗證一下結果，考慮到4851＝231×21，而3003＝231×13，是以231是兩數的公約數。21和13除1之外沒有共同的因數，是以231是4851和3003的最大公約數。
最大公約數
如果你願意的話，這是另一個可以跳過的數學解釋。
歐幾裡得算法的關鍵是這個事實：gcd(a, b)＝gcd(b, a mod b)。
要了解為什麼這是正确的，可以考慮取模運算符的定義。如果餘數r＝a mod b，那麼對于整數m，a＝m×b＋r。如果g是a和b的最大公約數，g是b的約數，是以g也必定是m×b的約數。因為g是a的約數并且a＝m×b＋r，g必定是m×b＋r的約數。因為g是m×b的約數，它也一定是r的約數。
這證明了g是b和r的約數。g＝gcd(b，r)的意思是g是能夠約分b和r的最大整數。
假設g是一個比g大的整數，并且g 是b和r的約數，那麼g也是m×b的約數。但是a＝m×b＋r，是以g也是a的約數。這就意味着g不是a和b的最大公約數。這與g是a和b最大公約數的條件沖突，因為這與g＞g的假定産生了沖突，是以不存在這樣的g，故g為a和b的最大公約數。
這個算法是較為快捷的，每兩次while循環中，b值被一個因數至少減少為其1/2。因為b值在每兩次疊代中被一個因數減少至少1/2，是以這個算法的運作時間複雜度至多為o(log b)。
對速度的需求
歐幾裡得算法中的b值在每兩次while循環中被一個因數至少減少為其1/2。為了一探究竟，令ak、bk和rk為第k次疊代中a、b和r的值，并且認為對于任意整數m，a1＝ m1×b1＋r1。在第二次疊代中，a2＝b1而b2＝a1。
如果r1≤b1/2，那麼可知b2≤b1。
假設r1＞b1，在第三次疊代中，a3＝b2＝r1并且b3＝r2。根據定義，r2＝a2 mod b2，且與b1 mod r1相等。由于我們假設r1＞b1/2，是以r1能夠除b1一次并且留下餘數(b1-r1)。
由于我們假設r1＞b1/2，故可知(b1-r1)≤b1/2。
回到最初的方程式：(b1-r1)＝(b1 mod r1)＝(a2 mod r2)＝r2＝b3。是以b3≤b1/2，這是我們要證明的。