【密码学】欧几里得算法扩展形式的证明

by 狐狐的鹿鹿

定理：如果 d=GCD(a,b), 那么存在整数s 和 t 使得 d=as + bt, 并且d是能被这样表示的最小正整数。

证明：

假设 S为 a,b线性组合的集合。S={s=k1a+k2b | k1,k2为整数,s>0},显然a,b本身属于S，且S不为空集

下面用反证法：

假设 d̸ | a， 则a可以容易的表示为：

a = dq + r, 0 < r < d

由于a,d都是a，b的线性组合，则r = a − dq 也是a，b的线性组合，则r属于集合S且比d小，与d是集合S中最小的元素矛盾。故可以证明 d|a。

同理可证d|b。

上面已经证明了d是a,b的公因数，下面证明d是最大的公因数。

对所有正整数c ，如果 c|a 且 c|b 则c能整除a，b的所有线性组合，所以c|d。

所以d是a，b的最大公因数。即 ：

d=GCD(a,b)

用以上方法，可以简单证明以下定理：

对E上的b1,b2,…,bn，若bi不全为0，则存在k1,k2,…kn∈E，使得gcd(b1,b2,…,bn)=k1b1+…+knbn

思路: 定义集合S={k1b1+…knbn|ki∈E}，则gcd=d，d∈S,且g(d) 为最小。然后证明(1)d是公因子，(2)d是最大公因子

ref https://www.math.fsu.edu/~pkirby/mad2104/SlideShow/s5_2.pdf