歐幾裡德算法又稱輾轉相除法，主要是用于計算兩個整數a,b的最大公約數。
簡單點說一下算法原理：兩個整數的最大公約數等于其中小的那個數跟大除以小餘數的最大公約數。
即： gcd(a,b)=gcd(b,a mod b) 。
舉個簡單的例子：
比如求 10跟 24 的最大公約數：
a = gcd(10, 24):
1. 求10和24的最大公約數等于求10和4的最大公約數 ：
a = gcd(10, 24) = gcd(10, 4)
2. 求10跟4的最大公約數等于求4跟2的最大公約數，為2 ：
a = gcd(10, 24) = gcd(10, 4)
= gcd(4, 2) = 2
# python
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
print(gcd(10,24)) # 2
算法原理：若a和b為正整數，則存在整數x, y 使得gcd(a,b)=ax by;
通俗點說就是 gcd(a,b)可以表示為a,b的整數線性組合。
舉個簡單的例子：
gcd(10, 24) = 2
2 = 10*(-7) 24*3
主要應用有以下三方面：
1. 求解不定方程；
例題：求 435x 783y = 87 的一組整數解：
先通過歐幾裡得算法得：
783 = 1× 435 348
435 = 348×1 87
348 = 87 × 4 0
∴ 87 = 435 – 348
87 = 435 – (783 – 435)
87 = (–1)(783) 2(435)
∴ x = 2, y = −1是此不定方程的一組整數解。
2. 求解模的逆元(乘法逆元)，參考同餘方程、歐拉函數、乘法逆元、定義在Zm上的矩陣求逆
3. 求解模線性方程（線性同餘方程）；
1）. 求解同餘方程 ax ≡ b (mod m), x = ?
舉個極端代表性的例子: 15x = 1 mod 26
這道題轉化成15x - 26y = 1 既可以當做1求解不定方程 ,也可以當做2求乘法逆元
解法如下：
26 = 1× 15 11
15 = 11×1 4
11 = 4 × 2 3
4 = 1 × 3 1
3 = 1 × 3
∴ 1 = 4 – 3
= 4 – (11 – 4×2)
= 4×3 – 11
= (15-11) ×3 - 11
= 15×3 - 11×4
= (26-11)×3 - 11 ×4
= 26×3 - (26 - 15)×7
=26×(-4) 15×7
∴ x = 7, y = −4 為此不定方程的一組整數解，15關于模26的乘法逆元為7
2）. 求解同餘方程組 繼續往下看中國剩餘定理
中國剩餘定理在《孫子算經》中有這樣一個問題：“今有物不知其數，三三數之剩二（除以3 餘2），
五五數之剩三（除以5 餘3），七七數之剩二（除以7 餘2），問物幾何？”
宋朝數學家秦九韶于1247年《數書九章》卷一、二《大衍類》對“物不知數”問題做出了完整系統的解答。明朝數學家程大位将解法編成易于上口的《孫子歌訣》：
三人同行七十稀，
五樹梅花廿一支，
七子團圓正半月，
除百零五便得知。
意思是隻要是除以3餘了一個1，就加上一個70；
隻要是除以5餘了一個1，就加上一個21；
隻要是除以7餘了一個1，就加上一個15。然後累加。
最後計算這個總和除以105的餘數。
也就是 (2×70 3×21 15×2 ) mod 105 = 23
解法如下：
先從3和5、3和7、5和7的公倍數中相應地找出分别被7、5、3除均餘1的較小數15、21、70 ( 此步又稱為求"模逆"運算，參考乘法逆元解法)。即：
15÷7=2……餘1，
21÷5=4……餘1，
70÷3=23……餘1.
再用找到的三個較小數分别乘以所要求的數被7、5、3除所得的餘數的積連加，
15×2 21×3 70×2=233.
最後用和233除以3、5、7三個除數的最小公倍數.
233÷105=2……餘23，
這個餘數23就是合乎條件的最小數.
拓展到一般情況：
假設整數m1, m2, ... , mn兩兩互質，則對任意的整數：a1, a2, ... , an 方程組:
都存在整數解，且若X , Y 都滿足該方程組，則必有 X ≡ Y (mod N) 其中：
公式如下：
課本上的公式符号實在不想看，就拿作業來舉兩個例子吧。
作業1：求解同餘方程組：
x ≡ 12 (mod 25)
x ≡ 9 (mod 26)
x ≡ 23 (mod 27)
以上方程組等價于 x = 25a 12 = 26b 9 = 27c 23
移一下項 得：
① : 25a - 27c = 23-12 = 11
②: 26b - 25a = 12-9 = 3
首先對①式運用拓展歐幾裡得：
27 = 25×1 2
25 = 2×7 11
則：
11 = 25 - 2×7
= 25 - (27-25) ×7
= 25×8 - 27×7
所以a=8, c=7
代入x = 25a 12 = 27c 23 得：
x = 212
得到合并方程 x = 212 25 × 27t 即：x ≡ 212 (mod 675)
然後再跟x ≡ 9 (mod 26) 合并
x = 212 675t = 26b 9
26b - 675t = 203
675 = 26×25 25
25 = 25×1
所以：
203 = (26-25)×203
= (26 - (675-26*25))×203
= 26×5278 - 675×203
b=5278 , t=203
代入得x = 137237
得到合并方程 x = 137237 25 × 27×26t 即：x ≡ 137237 (mod 17550) , x=14387
x = 14387 17550n (n∈Z）
作業2：求解如下同餘方程組：
13x ≡ 4 (mod 99)
15x ≡ 56 (mod 101)
這類同餘方程組帶着系數讓人頭大，但是也不妨礙使用拓展歐幾裡德，
首先去掉系數：
x ≡ 46 (mod 99)
x ≡ 98 (mod 101)
# 求解方法很多，這裡列舉利用二元一次不定方程方法：
# 13x ≡ 4 (mod 99) 轉化為 13x-99y = 4
然後用拓展歐幾裡德：
13×46-99×6 = 4
x=46, y=6
所以不定方程13x-99y = 4 的所有解為
x=46 99t
y=6 13t
所以原同餘方程解為：x ≡ 46 (mod 99)
消去x得： 99a - 101b = 52
拓展歐幾裡德走你：x = 7471 (mod 9999)
x = 9999 n 7471 (n ∈ Z)
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
