a,b互质 a mod b与b互质吗为什么?

来源:学生作业帮助网 编辑:六六作业网 时间:2024/05/24 06:50:38
a,b互质amodb与b互质吗为什么?a,b互质amodb与b互质吗为什么?a,b互质amodb与b互质吗为什么?是的,证明:设c=amodb假设c与b不互质,则存在d不等于1和m,n使得c=md,b

a,b互质 a mod b与b互质吗为什么?
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互质