欧几里德算法

出处：按学科分类—自然科学总论 山东人民出版社《方法大辞典》第215页（871字）

也叫辗转相除法。

这是数论和代数学中的重要方法。从整数的除法可知：对任给二整数a，b＞0，必有二整数q及r存在，使得a=qb+r，0≤r

a=bq₁+r₁， 01

b=r₁q₂+r₂， 021，

r₁=r₂q₃+r₃， 032，

……… ………

r_n－₂=r_n－1q_n+r_n， 0nn－1，

r_n－1=r_nq_n+1+r_n+1， r_n+₁=0

因为每进行一次除法，余数就至少减一，而b是有限的正整数，所以最多进行b次，总可以得到一个余数是零的等式，即r_n+1=0。上面的方法叫做欧几里德算法。也叫长除法。

我国古代数学家早在欧几里德之前数百年就创造了这一方法，在我国常称为辗转相除法。利用欧几里德除法，就很容易证明两个正整数a，b的最大公约数(a，b)就是r_n，这是一个求最大公约数的有效方法。利用它，可以求出任意两个非零整数的最大公约数。例如，求(123，18)，利用欧几里德算法，有123=6·18+15，18=1·15+3，15=5·3，所以(123，18)=3，利用欧几里德算法还可得到最大公约数的两个重要性质。

设a，b是两个正整数，则(1)(am，bm)=(a，b)m；其中m是任意正整数；(2)若d是a，b的任一公因数，则(a／d，b／d)=(a，b)／d，特别有(a／(a，b)，b／(a，b))=1。在此基础上，就可以进一步得出初等数论中最重要的定理，即算术基本定理：任一大于1的整数能唯一地写成，其中p₁2<…s为素数。这个式子叫做a的标准分解式。它是整个初等数论的基础。

欧几里德算法在代数学中也有重要应用，特别是关于多项式环的因子分解理论，建立这一理论的基础就是多项式环上的欧几里德除法。