作业帮 > 数学 > 作业

辗转相除法和更相减损术的原理?

来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/03/29 14:59:53
辗转相除法和更相减损术的原理?
算法那一块涉及到的,书上没讲原理,我想了解一下原理是咋推出来的?
辗转相除法和更相减损术的原理?
辗转相除法又叫欧几里得辗转相除法,最早出现在公元前300年古希腊著名数学家欧几里得的《几何原本》》(第VII卷,命题i和ii)中.而在中国则可以追溯至东汉出现的《九章算术》.而在现代数学中,这应该是属于数论的部分的.
要想解释辗转相除法的原理,需要先知道以下两点:
一、一个一般定理:
如果a是任一整数而b是任一大于零的整数,则我们总能找到一整数q,使
a=bq+r
这里r是满足不等式0