说在开头。

出于对欧几里得的尊重，先简单介(cou)绍(ge)一(zi)下(shu).。

欧几里得，古希腊人，数学家。他活跃于托勒密一世时期的亚历山大里亚，被称为“几何之父”。

他最著名的著作《几何原本》是欧洲数学的基础，提出五大公设，欧几里得几何，被广泛的认为是历史上最成功的教科书。

欧几里得也写了一些关于透视、圆锥曲线、球面几何学及数论的作品。（https://baike.baidu.com/item/欧几里得/182343?fr=aladdin）

----------------------------------华丽的分割线-------------------------------------

以下都是自己在看书的时候自己想的一些思路，总结。

如有雷同纯属意外，如有异议可以py（仅限妹纸）。

欧几里得算法，也就是所谓的辗转相除法。人话就是，用来求最大公约数的方法。

证明：gcd（a,b）= gcd(b,a%b)    

（gcd（a，b），ab的最大公约数；a%b，求模运算，也就是求余数运算。比如7%2=1。）

证明过程：

设正整数a,b(a>b)。

设：gcd（a，b）= c　　（我就要设c）

则有：c|a ，c|b　　（|，表示可以整除）

设：　a = bx + a%b　　（x为整数，因为这是求余运算，emmm，这样说应该够平易近人了吧）

则有：a%b = a - bx　　（别说恒等变换不知道。233333）

因为：c|b　　则 c|bx　　（因为c|b=k（k为整数），则kx为整数，这样说够清楚了吧。emmmm）

则：（a%b）/c = （a - bx）/ c    ====》  （a%b）/c = a/c - bx/c 

因为：c|a ， c|bx

故：a/c，bx/c都为整数，所以a/c - bx/c 也是整数。所以（a%b）也可以被c整数。

即：c |（a%b）

又因为：c|b

故：gcd（b，a%b）= c
则：gcd（a,b）= gcd(b,a%b) 得证。（这证明过程，我就不信全网还有比这写的更清楚的。）

证明完这个我们就可以通过迭代，反复相除（辗转相除）来求ab的最大公约数了。

emmm，为什么就可以了呢。因为gcd（a,b）= gcd(b,a%b)  就是一个反复的过程。

比如我可以继续写：gcd（a,b）= gcd(b,a%b) = gcd（a%b，b%（a%b））=gcd（r₁，r₂）=·······=gcd（r_n-1，r_n）（r_n=r_n-2%r_n-1）

这样是不是可以更清楚点了。。

代码实现（递归实现）

1、递归操作：辗转相除

2、递归结束操作：余数为0

"""

这只是一个简单版本。

比如，对没有最大公约数的情况并没有做判断。

"""

def gcd(a,b):
    if a < b:
        a, b = b, a
    if a % b != 0:
        return gcd(b,a%b)
    return b

------------------------------分割线-------------------------------------
回家睡觉。明天再说。困死了。
先给出扩展欧几里得扩展算法实现。有空再说。

"""
欧几里得扩展
求ax+by=z通解
"""
# def eucild_ex(a,b):
#     if b == 0:
#         x = 1
#         y = 0
#         return x,y,a
#     (x,y,r) = eucild_ex(b,a % b)
#     tmp = x
#     x = y
#     y = tmp - int(a/b)*y
#     return (x,y,r)