欧几里德算法及其扩展.pdf

欧几里德与扩展欧几里德算法 欧几里德算法 欧几里德算法又称辗转相除法用于计算两个整数 a,b 的最大公约数 基本算法设 a=qb+r其中 abqr 都是整数则 gcd(a,b)=gcd(b,r)即 gcd(a,b)=gcd(b,a%b) 第一种证明 a 可以表示成 a = kb + r则 r = a mod b 假设 d 是 a,b 的一个公约数则有 d|a, d|b而 r = a - kb因此