gcd(最大公约数算法)数学证明(转)
本文转自:
常识:如果 a≥b 并且 b≤a,那么 a=b.
1)只在正数(原谅为非负整数)范围内讨论两个数 m 和 n 的最大公约数,即 m, n ∈ N.
2)不考虑0的情况.(原文为处理0的特殊情况)
引理:
假设 k|a(表示a能够被整除), k|b,则对任意的 x,y ∈ Z, k|(xa+yb)均成立.
k|a => a=pk, k|b => b==qk (其中 p,q ∈ Z)
于是有 xa+yb=xpk+y