gcd(a,b)=gcd(b,a%b)　求证明

(1) 设gcd(a,b) = k a = n1 * k b = n2 * k a%b = (n1%n2)*k b = n2 * k 现在只需证n2 和 n1%n2 没有公因子假设有公因子,为r n2 = num2 * r n1%n2 = num1 * r n1 = k*n2 + num1*r n1 = (k*num2+num1)*r n1和n2有公因子,这与设gcd(a,b) = k矛盾,...

文章标签：