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

4 {5 4 { 5 int r = b; 欧几里德算法 欧几里德算法又称辗转相除法用于计算两个整数 a,b 的最大公约数 基本算法设a=qb+r,其中a, b, q, r都是整数则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