數論/唯一分解和積性函式
給定兩個不互質的數，求其最大公約數。
該演算法基於以下兩個觀察結果
1. If b|a then gcd(a, b) = b.
事實確實如此，因為任何數（特別是 b）的除數都不能大於該數本身（我在這裡談論非負整數）。
2. If a = bt + r, for integers t and r, then gcd(a, b) = gcd(b, r).
實際上，a 和 b 的任何公約數也除以 r。因此 gcd(a, b) 除以 r。但是，當然，gcd(a, b)|b。因此，gcd(a, b) 是 b 和 r 的公約數，因此 gcd(a, b)=gcd(b, r)。反之亦然，因為 b 和 r 的任何除數也除以 a。
例子
Let a = 2322, b = 654. 2322 = 654*3 + 360 gcd(2322, 654) = gcd(654, 360) 654 = 360*1 + 294 gcd(654, 360) = gcd(360, 294) 360 = 294*1 + 66 gcd(360, 294) = gcd(294, 66) 294 = 66*4 + 30 gcd(294, 66) = gcd(66, 30) 66 = 30*2 + 6 gcd(66, 30) = gcd(30, 6) 30 = 6*5 gcd(30, 6) = 6 Therefore, gcd(2322,654) = 6.
對於任何一對 a 和 b，該演算法一定會終止，因為每一步都會生成一個類似的問題（即求 gcd）對於一對較小的整數。令 Eulen(a,b) 表示一對 a,b 的歐幾里得演算法的長度。Eulen(2322, 654) = 6，Eulen(30, 6) = 1。我將在以下演算法的重要結果的證明中使用此符號：推論對於每對整數 a 和 b，都存在兩個整數 s 和 t，使得 as + bt = gcd(a, b)。例子
2322×20 + 654×(-71) = 6。證明
設 a > b。證明是透過對 Eulen(a, b) 進行歸納。如果 Eulen(a, b) = 1，即如果 b|a，那麼 a = bu 對於某個整數 u。因此，a + (1 - u)b = b = gcd(a, b)。我們可以取 s = 1 和 t = 1 - u。
假設對於所有 Eulen 小於 n 的數字對，推論已經成立。設 Eulen(a, b) = n。執行一步演算法：a = bu + r。Eulen(b, r) = n - 1。根據歸納假設，存在 x 和 y 使得 bx + ry = gcd(b,r) = gcd(a,b)。將 r 表示為 r = a - bu。因此，ry = ay - buy；bx + (ay - buy) = gcd(a, b)。最後，b(x - uy) + ay = gcd(a, b)，我們可以取 s = x - uy 和 t = y。
還有一個利用鴿巢原理的簡單證明。備註
注意，任何線性組合 as + bt 都可以被 a 和 b 的任何公因子整除。特別是，a 和 b 的任何公因子也整除 gcd(a, b)。在“逆”應用中，任何線性組合 as + bt 都可以被 gcd(a, b) 整除。由此得出，gcd(a, b) 是可以表示為 as + bt 形式的最小正整數。所有其他數都是 gcd(a, b) 的倍數。推論在任意域上的推廣被稱為貝祖恆等式或貝祖引理，以法國數學家埃蒂安·貝祖 (1730-1783) 的名字命名，因此在推論中陳述的結果通常也稱為貝祖恆等式或貝祖引理。
對於互質數，我們得到存在 s 和 t 使得 as + bt = 1。這個推論是一個強大的工具。它出現在 3 個玻璃杯和沙漏問題中。例如，讓我們證明歐幾里得命題 VII.30 如果兩個數相乘得到一個數，並且任何素數除以該乘積，那麼它也除以其中一個原始數。
設素數 p 除以乘積 ab。假設 pa。那麼 gcd(a, p) = 1。根據推論，對於某些 x 和 y，ax + py = 1。乘以 b：abx + pby = b。現在，p|ab 且 p|pb。因此，p|b。
實際上，這證明了命題 VII.30 的一個推廣，我在這些頁面上多次使用：設 m|ab 且 gcd(a, m) = 1。那麼 m|b。
命題 VII.30 直接蘊含算術基本定理，儘管歐幾里得從未明確地陳述過它。它第一次是在 1801 年由高斯在他的《算術研究》中提出的。算術基本定理任何整數 N 都可以表示為素數的乘積。這種表示對於素因子的順序來說是唯一的。
因為，根據定義，如果一個數除了 1 和它本身之外還有其他因子，則它是合數，而這些因子必然小於該數，我們可以不斷提取因子，直到只剩下素因子。這表明表示的存在：N = pqr...，其中所有 p、q、r... 都是素數。為了證明唯一性，假設有兩個表示：N = pqr... = uvw... 我們看到 p 除以 uvw... 根據推論，它除以其中一個因子 u、v、w... 將它們消去。我們可以繼續將左右兩側剩餘的因子消去，直到沒有因子剩餘。
將一個數表示為素數的乘積稱為素數分解。算術基本定理斷言，每個整數都有唯一的素數分解。