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