egcd算法证明
斜体文本
算法 证明 代码

预备知识:

$$a=kp+r,0 \le r<p \\ a \in N^+$$
$$S={{am+bn;m,n \in Z \ and \ am+bn>0}}$$
集合S必有下界。
设其中 $$d=ar+bs = S _{min}$$
则 $$d=gcd(a,b)$$ 证明如下：
$$a=qd+r^1, \ 0\le r<d$$ 如果
$$r^1>0$$
$$r^1=a-qd=a-(ar+bs)q=a(1-rq)+b(-sq)$$
显然 $$r^1 \in S,r^1<d$$ 与题意矛盾，故
$$r^1\not\in S\Rightarrow r^1=0.$$
同理b可证。
因此，存在性证明完毕。可得 $$a,b均可被d整除$$
假设存在另一个 $$d_1$$ 使得
$$a=d_1h,b=d_1k \ (h,k\in N^+)$$
$$d=ar+bs=d_1hr+d_1ks=d_1(hr+ks)$$ 显然
$$(hr+ks)\in N^+,(hr+ks)>0$$
综上可得 $$d=gcd(a,b)$$
GCD算法简介：
$$gcd(a,b) \ a,b\in N^+$$
$$a=gcd(a,0)$$
不如假设 $$b<a$$ 则
$$gcd(a,b)=gcd(b,a\%b)$$
$$a=qb+r_1 \Rightarrow r_1=a-qb$$ 显然
$$d也是r的最大公因数$$ 因此从gcd算法可推出如下公式(利用迭代或者递归使b==0)
$$a=q_1b+r_1$$ $$b=q_2r_1+r_2$$ $$r_1=q_3r_2+r_3$$ $$......$$ $$r_i=q_{i+2}r_{i+1}+r_{i+2}$$ $$....$$ $$r_{n-1}=q_{n+1}r_n+0$$ $$r_n=gcd(a,b)$$ 又因为
$$r_1=ax_1+by_1$$ $$r_2=ax_2+by_2$$ $$.....$$ $$r_i=ax_i+by_i$$ $$....$$ $$r_n=ax_n+by_n$$
由GCD算法公式可得：
$$1.r_i=r_{i-2}-r_{i-1}q_i$$
又因为 $$2.\ r_{i-2}=ax_{i-2}+by_{i-2}$$ $$3.\ r_{i-1}=ax_{i-1}+by_{i-1}$$ 将上述2 3 公式代入1式子
$$4. \ r_i=(ax_{i-2}+b_{i-2})-(ax_{i-1}+by_{i-1})q_i=a(x_{i-2}-q_ix_{i-1})+b(y_{i-2}-q _iy_{i-1})==ax_i+by_i$$
$$r_i\in S$$ 另
$$r_{-1}=1a+b0 \in S$$ $$r_0=a0+b1 \in S$$ 显然要得到
$$x_i,y_i$$ 可以由 $$x_{i-1},x_{i-2},y_{i-1},y_{i-2}$$ 得到 $$q_i$$ 进而得到 $$x_i和y_i$$