摸鱼第一,干活第二

It's time for BOOM!(ノ≧∀≦)ノ

【数学】同余

OI中可以说是比较恶心的数论。

什么是同余

给定一个正整数m,如果两个整数a和b满足(a-b)能够被m整除,即m|(a-b),那么就称整数a与b对模m同余,记作:

\(a\equiv b(mod\;m)\)

其实可以把它看做另一种比较易于理解的形式:

\(a\div m=n\cdots\cdots b(n=1,2,3\cdots)\)

你必须了解的同余性质(很长警告)

反身性

\(a\equiv a(mod\;m)\)

虽然不知道有什么卵用。证明为:

\((a-a)=0\;and\;m\mid0\Rightarrow m\mid(a-a)\)

\(\Leftrightarrow a\equiv a(mod\;m)\)


对称性

\(if\;a\equiv b(mod\;m),then\;b\equiv a(mod\;m)\)

证明为:(使用了整除的性质)

\(a\equiv b(mod\;m)\Leftrightarrow m\mid(a-b)\)

\(\Leftrightarrow m\mid(b-a)\)

\(\Leftrightarrow b\equiv a(mod\;m)\)


传递性

\(if\;a\equiv b(mod\;m)\;and\;b\equiv c(mod\;m),then\;a\equiv c(mod\;m)\)

证明为:(使用了整除的性质)

\(a\equiv b(mod\;m),b\equiv c(mod\;m)\Leftrightarrow m\mid(a-b),m\mid(b-c)\)

\(\Rightarrow m\mid(a-b+b-c)\)

\(\Rightarrow m\mid(a-c)\)

\(\Leftrightarrow a\equiv c(mod\;m)\)


相加减

\(if\;a\equiv b(mod\;m)\;and\;c\equiv d(mod\;m),then\;a\pm c\equiv b\pm d(mod\;m)\)

证明为:(原理与证明传递性相仿)

\(a\equiv b(mod\;m),c\equiv d(mod\;m)\Leftrightarrow m\mid(a-b),m\mid(c-d)\)

\(\Rightarrow m\mid(a-b+c-d),m\mid(a-b-c+d)\)

\(\Rightarrow m\mid[(a+c)-(b+d)],m\mid[(a-c)-(b-d)]\)

\(\Leftrightarrow a\pm c\equiv b\pm d(mod\;m)\)


乘法

\(if\;a\equiv b(mod\;m)\;and\;c\equiv d(mod\;m),then\;ac\equiv bd(mod\;m)\)

证明为:(过于复杂,以下省略)


除法

\(if\;bc\equiv cd(mod\;m)\;and\;c\neq 0,then\;a\equiv b(mod\;m\div gcd(c,m))\)

证明为:(过于复杂,以下省略)


同余方程

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code