作业帮 > 数学 > 作业

欧几里德算法怎么使用我是自学初等数论的,看书上使用欧里几德算法算(a,b),书上例题将其转化为(a-b,b)或(a-Kb

来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/11/11 10:14:10
欧几里德算法怎么使用
我是自学初等数论的,看书上使用欧里几德算法算(a,b),书上例题将其转化为(a-b,b)或(a-Kb,b)K为常数,请问这是性质吗,还是题目恰好这样允许
欧几里德算法怎么使用我是自学初等数论的,看书上使用欧里几德算法算(a,b),书上例题将其转化为(a-b,b)或(a-Kb
若k为整数,则(a,b) = (a-kb,b).
这是最大公约数的性质,证明其实不难.
若m为a和b的公约数,即m | a,m | b.
有m | kb,于是m | a-kb.
m也是a-kb和b的公约数.
反之若m为a-kb和b的公约数,同样可得m也为a和b的公约数.
于是a,b的公约数集合和a-kb,b的公约数集合相同.
最大公约数作为其中最大者自然也是相等的.