數(shù)學(xué)背景：

整除的定義：

任給兩個(gè)整數(shù)a,b,其中b≠0，如果存在一個(gè)整數(shù)q使得等式

a = bq

成立，我們就說是b整除a,記做b|a.

性質(zhì)1：如果c|a,c|b,且對(duì)于任意的整數(shù)m,n,則有c|ma + nb

證明： 利用上述定義進(jìn)行證明

因?yàn)閏|a ,c|b，所以有a = c*q1,b = c*q2,

對(duì)于任意m,n有，ma+nb = m(c*q1) + n(c*q2) = c(m*q1 + n*q2),

因?yàn)閙*q1 +n*q2為整數(shù)，很顯然有 c|ma + nb .

帶余除法： 設(shè)a,b 是兩個(gè)整數(shù)，其中b > 0 ,則存在兩個(gè)唯一的整數(shù)q和r，使得

a = b*q + r, ? ? ? ? ?0≤ r < b

成立.

公因數(shù)和最大公因數(shù)的定義：

設(shè)a1,a2,a3,......,an是n個(gè)不全為0的整數(shù)，若整數(shù)d是它們之中每一個(gè)數(shù)的因數(shù)，那么d就叫做a1,a2,a3,......,an的一個(gè)公因數(shù).這時(shí)它們的公因數(shù)只有有限個(gè)，整數(shù)a1,a2,a3,......,an的公因數(shù)中最大的一個(gè)叫做最大公因數(shù)，記做(a1,a2,a3,......,an),若(a1,a2,a3,......,an)=1，我們說a1,a2,a3,......,an互素.

定理1：設(shè)a,b,c是任意三個(gè)不全為零的整數(shù)，且 a = bq + c,其中q是整數(shù)，則(a,b) = (b,c).也就是說，a和b的最大公因數(shù)等于b和c的最大公因數(shù).

證明： 因?yàn)?a,b)是a和b的最大公因數(shù)，所以(a,b)|a,且(a,b)|b,由于c = a - bq,所以由性質(zhì)1可以知道(a,b)|c，所以可以看到，(a,b)是b,c的一個(gè)公因數(shù),而由公因數(shù)的定義可以知道 (b,c)是b,c的最大公因數(shù)，任何公因數(shù)都是小于最大公因數(shù)的，所以(a,b) ≤ (b,c).

同樣的道理可以證明 (b,c) ≤(a,b).

因此有(a,b) = (b,c)

輾轉(zhuǎn)相除法：給任意整數(shù) a > 0,b >0, 由帶余除法，有以下等式

a = b*q1 + r1, ? ? 0 < r1 < b,

b = r1*q2 + r2, ? ?0 < r2 < r1,

r1 = r2*q3 + r3, ? 0 < r3 < r2,

......

rn-2 = ?rn-1*qn+ rn , 0

rn-1=?rn*qn+1+?rn+1 ?,rn+1= 0

因?yàn)?b> r1 > r2 > r3 >....，故經(jīng)過有限次帶余除法以后，總可以得到一個(gè)余數(shù)為0，上面rn+1= 0

由上面的定理1可以知道，(a,b) = (b,r1) =?(r2,r1) = ....= (rn-2,rn-1) = (rn-1,rn) = (rn,0) =?rn

所以要想求a,b得最大公因數(shù)，就需要不斷的使用帶余除法，直到余數(shù)為0，就可以得到a,b的最大公因數(shù).

舉例：

使用輾轉(zhuǎn)相除法求 288 和 158 的最大公因數(shù)

288 ?= 158 * 1 + 130

158 ?= 130 * 1 + 28

130 = ?28 * 4 + 18

28 =18 * 1 + 10

18 = 10 * 1 + 8

10 = 8 * 1 + 2

8 = 2 * 4

所以(288,158) = (158,130) = (130,28) = (28,18)=(18,10)=(10,8)=(8,2)=(2,0)=2

python 實(shí)現(xiàn)：

遞歸

defgcd(a,b):if b == 0 : returnareturn gcd(b,a % b)

迭代

defgcd(a,b):while b !=0:

a,b= b,a%breturn a

總結(jié)

以上是生活随笔為你收集整理的python辗转相除_使用辗转相除法求两个数的最大公因数（python实现）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。