欧几里得算法
文章目录
欧几里得算法描述
设
$$ a = kb + r $$
得
$$ \gcd(a,b) = \gcd(a,r) = \gcd(a, a\pmod b) $$
证明
设 d = gcd(a,b), 也就是 d|a, d|b
有 r = a - kb
两边都除 d, r/d = a/d - kb/d = m, 由于m为正整数,所以 d|r
得到 d|a, d|b, d|r
gcd(a,b) = gcd(a,r)
欧几里得算法描述
设
$$ a = kb + r $$
得
$$ \gcd(a,b) = \gcd(a,r) = \gcd(a, a\pmod b) $$
证明
设 d = gcd(a,b), 也就是 d|a, d|b
有 r = a - kb
两边都除 d, r/d = a/d - kb/d = m, 由于m为正整数,所以 d|r
得到 d|a, d|b, d|r
gcd(a,b) = gcd(a,r)
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论