作业帮 > 数学 > 作业

a,b互质 a mod b与b互质吗

来源:学生作业帮 编辑:搜搜考试网作业帮 分类:数学作业 时间:2024/05/02 11:18:10
a,b互质 a mod b与b互质吗
为什么?
a,b互质 a mod b与b互质吗
是的,证明:
设c=a mod b
假设c与b不互质,则存在d不等于1和m,n使得
c=md,b=nd
由于c=a mod b,则存在k使得a=kb+c
于是a=knd+md=(kn+m)d
即d是a的因数
由于b=nd,故d也是b的因数
而d不等于1,这与a,b互质矛盾
综上,b与c互质