作业帮 > 数学 > 作业

数论有关同余的性质:求证若a≡b(mod m),则(a,m)=(b,m)

来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/11/10 12:37:49
数论有关同余的性质:求证若a≡b(mod m),则(a,m)=(b,m)
解释a≡b(mod m)表示a,b两整数都被整数m相除所得余数相同.
(a,m)=(b,m)表示a和m的最大公约数等于b和m的最大公约数
数论有关同余的性质:求证若a≡b(mod m),则(a,m)=(b,m)
可以证明a和m的公约数集合与b和m的公约数集合相同:
若d为a和m的公约数,即有d | a且d | m.
由a ≡ b (mod m),有m | b-a,故d | b-a.
于是有d | b,又d | m,即d也为b和m的公约数.
反之,若d为b和m的公约数,可同样推知d也为a和m的公约数.
公约数集合相同,最大公约数自然相等.