欧几里得算法、贝祖定理和扩展欧几里得
安子
·
·
个人记录
初学数论，请多多指教！可能会有些显而易见的东西写在了里面。
只是自己看不懂而已
一、欧几里得算法
简介没啥用BB两句：
欧几里德算法(Euclidean algorithm)， 又名辗转相除法，是求两个正整数之最大公约数的算法。它是已知最古老的算法， 其可追溯至公元前300年前。欧几里得算法原先只用来处理自然数，但在19世纪，辗转相除法被推广至其他类型的数，如高斯整数和一元多项式。另外，还被用来解决丢番图方程（Diophantine equations）和构造连分数等。
描述：
对于任意正整数a,b(a>b)，gcd(a,b)=gcd(b,r)其中r=a(mod b) .
其中gcd(x,y)表示x和y的最大公约数.凡是个人都知道
证明如下：
有两种方法，其实本质都一样
方法一（比较好理解）
令c=gcd(a,b)则a=cm ,b=cn(m,n\in\mathbb{Z}).
同时令 k 为 a 除以 b 的商,及(a-r)\div b=k.
证明分两步
一、证明 c 是 r 的因数
\therefore r=a-bk=cm-cnk=c·(m-nk)
而$c$又是$b$的因数，则此步证明了$gcd(b,r) \geqslant gcd(a,b)
二、证明m-n·k与n互质
假设：
m-kn$不与$n$互质,即$\exists d>1 $且$d\in\mathbb{Z}$使得$m-kn=xd$且$n=yd$ $(x,y\in\mathbb{Z})
\therefore m=kn+xd=kyd+xd=(ky+x)·d
\therefore a=mc=(ky+x)·d·c$ 而 $b=nc=ydc
则a与b又存在公约数d，此时gcd(a,b)=cd与先前假设gcd(a,b)=c相悖
故假设不成立，证明成立。
即b与r不存在比c更大的最大公约数则gcd(b,r)\leqslant gcd(a,b)
从而与证明一合并得gcd(a,b)=gcd(b,r)
证毕
PS：以上证明，建立在r\neq0的基础上，亦即m与n互质
（方法一思路来自于360百科）但可以让你看得更舒服
方法二（比较快）
证明也分两步：
一、证明a与b的公约数也是b与r的公约数都有
设 d 为 a,b 的公约数
同方法一，得到 a=k·b+r
假设 d是 (a,b) 的一个公约数，即d∣a，d∣b .
\therefore$ $a=xd$，$b=yd$ $(x,y\in\mathbb{Z})
两边同时除以 $d$ 得： $\frac{r}{d}=x-yk
\because x,y,k\in\mathbb{Z}
$\therefore $ $r $ 能被 $d$ 整除
因此 $d∣r$ 也就是说 $d $ 也是 $r$ 的公约数。
算法实现（依赖与以上证明的结论）：
好吧实在是太简单了所以直接贴代码了~~实际是本人太懒~~
```cpp
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y)
{
if(y==0) return x;
else
return gcd(y,x%y);
}
int main()
{
int a,b;
cout<<gcd(a,b);
return 0;
}
```
功能：输入两个数，输出两个数的最大公约数
### 二、贝祖定理
### 三、扩展欧几里得