輾轉相除法

　　利用帶餘數除法求兩個整數的最大公因數的一種演算法。最早岀現於歐幾裏得的《原本》，故又稱歐幾裏得演算法。具體過程如下：設u₀大於u₁是兩個正整數。用u_{1去除u0，若u1不能整除u0，則利用帶餘數除法可得u0=q1u1＋u2,0＜u2＜u1；進而再用u2去除u1，若u2仍不能整除u1，則同樣可得u1=q2u2＋u3,0＜u3＜u2；依次這樣做下去，一定存在正整數k，使得在作第k次帶餘數除法時得到uk－1=qkuk＋uk＋1,0＜uk＋1＜uk，以及uk＋1整除uk。由這樣的輾轉相除法所得到的uk＋1就是u0和u1的最大公因數，且有表示式uk＋1＝c0u0＋c1u1，式中的c0和c1可由以上的各次帶餘數除法中的部分商算出。同帶餘數除法一樣，輾轉相除法亦有各種形式的變形。}