2025年同余详解入门

同余详解入门同余关系 同余 如果 a 和 b 除以 c 的余数相同 就说 a 和 b 关于模 c 同余 记作 a b mod c 如果两个数 a 和 b 的差能够被 m 整除 那么就说 a 和 b 对模数 m 同余 关于 m 同余 比如 28 13 15 除以 5 正好除尽

大家好,我是讯享网,很高兴认识大家。

同余关系:


同余:如果a和b除以c的余数相同,就说a和b关于模c同余,记作a≡b(mod c)。

     如果两个数a和b的差能够被m整除,那么就说a和b对模数m同余(关于m同余)。

比如,28-13=15除以5正好除尽,我们就说28和13对于模数5同于,因为15是5的整

数倍。它的另外一层含义就是说:28和13除以5的余数相同。a和b对m同余,我们记

作a≡b(mod m)。比如,28与13对5同余可以写作28≡13(mod 5)。


同余关系是一种等价关系。

1.自反性:一个数永远和自己本身同余

2.对称性:a和b同余,b和a也就同余

3.传递性:a和b同余,b和c也同余,可以推出a和c也是同余的


同余运算中还有一些稍微复杂的性质。比如,同于运算和整数加减法一样满足“等量+等

量,其和不变”。


性质1.如果a≡b(mod m),x≡y(mod m),则有a+x≡b+y(mod m)。

证明:对于a≡b(mod m),总可以找到p,q,使得 a-mp=b-mq //等式1

同理对于x≡y(mod m),总可以找到r,s,使得x-mr=y-mq//等式2

等式1+等式2,有(a+x)-m(p+r)=(b+y)-m(q+s)  //可以看出余数相等

则有    (a+x)≡(b+y)(mod m) //得证

同样的方法可以证明另外一条性质


性质2:如果a≡b(mod m),x≡y(mod m),则有ax≡by(mod m)。

证明:依旧先得到等式1与等式2,等式1*等式2,得到:

(a-mp)(x-mr)=(b-mq)(y-ms)

化简,得  ax+m(mpr-ar-xp)=by+m(mqs-bs-yq)


讯享网

即有ax≡by(mod m)  //得证


性质3:如果ac≡bc(mod m),且c和m互质,则有a≡b(mod m)(就是说同余式两边可

以同时除以一个和模数互质的数)。

证明:对于ac≡bc(mod m),我们总可以找到p,q使得

ac-mp=bc-mq

移项有ac-bc=mp-mq

即有       c(a-b)=m(p-q)

这说明c(a-b)/m=(p-q) c(a-b)可以被m整除

又因为 c与m互质  所以(a-b)可以被m整除

得到a≡b(mod m)


性质4:若ac≡bd,c≡d(mod m),且(c,m)=1(c和m的最大公约数是1),得到a≡b(mod m)。

证明:因为(c,m)=1,且c≡d(mod m)所以(d.m)=1

 因为c≡d(mod m)所以总可以找到p,q,使得c-mp=d-mq

两边同乘a,有ca-mpa=da-mqa

因为ac≡bd所以有 ba-mpa=da-mqa

所以有 bd≡da(mod m)

又因为(d.m)=1所以有b≡a(mod m)。


除此之外还有其他的同余性质关系等式...


在ACM做题目的过程中经常会遇到mod xxxxxxx... ,这是因为为了避免高精度的运

算。因为我们可以看得出在运算过程中算完再mod还是一遍算一边mod,最后得到的结

果是一样的,就是因为同余 的关系。因为同余关系只是关心余数,不用去在乎除的时候

整数的部分。所以,在整个运算过程中每一步最大都不会超过m,从而避免了高精度的

运算。

小讯
上一篇 2025-02-19 09:09
下一篇 2025-01-19 23:17

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/131464.html