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

欧几里德算法怎么使用
我是自学初等数论的,看书上使用欧里几德算法算(a,b),书上例题将其转化为(a-b,b)或(a-Kb,b)K为常数,请问这是性质吗,还是题目恰好这样允许
mym0040311 1年前 已收到1个回答 举报

广州安妮 幼苗

共回答了18个问题采纳率:94.4% 举报

若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的公约数集合相同.
最大公约数作为其中最大者自然也是相等的.

1年前

9
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.060 s. - webmaster@yulucn.com