同余初步性质

未分类
5.8k 词

前言

在小学中，我们接触到了整数除法，其中会有一个概念名为余数。当然，这个概念在小学五年级学小数的时候就被抛弃了，但是在数论的知识中，它再次卷土重来，折磨众生。

整除概念

对于一个整数 $a$ 和 $m$，我们取 $a\div m$ 下的余数，记为 $\color{Blue} a \bmod m$
易得，整除的概念为除以 $m$ 的意义下余数为 $0$，即$a \bmod m=0$：
一般的，对于整数 $a$ 和 $m$，$\color{Blue} 若 a \bmod m=0，我们记为 \color{Blue} m \mid a$，此时 $m$ 为 $a$ 的因子，$a$ 为 $m$ 的倍数。

根据 $\mid$ 的意义可得，若 $a \mid m$，则定有一个整数 $k$，使得 $a=km$

接下来我们来考虑整除有什么特殊的性质。

  • $\boxed{若 a \mid b，c \mid d，则有 ac \mid bd}$
    证明：
    $\because a \mid b,c \mid d\\\therefore \exist k,m\in \Z,b=ka,d=mc\\\therefore ac \mid bd\Rightarrow ac\mid \left(ka\cdot mc\right)\Rightarrow ac \mid km \cdot ac\\\therefore 结论显然成立$

  • $\boxed{\color{Red} 若 c \mid a,c \mid b，则有 \forall m,n\in \Z,c \mid (ma+nb)}$
    证明：
    $\because c \mid a,c \mid b\\\therefore \exist k,l \in \Z,a=kc,b=lc\\\therefore c\mid (ma+nb)\Rightarrow c \mid (m\cdot kc+n\cdot lc)\Rightarrow c \mid (mk+nl)c\\\therefore 结论显然成立$

同余概念

对于整数 $a$ 和 $b$ 和 $m$，若 $a \bmod m=b \bmod m$，$\color{Blue} 则称 a 与 b 在 \bmod~m的意义下同余，记为 \color{Blue} a \equiv b \pmod m$
由概念易得：

  • $\boxed{若 a \equiv b \pmod m ，则定有 \exist k,l,c \in \Z,a=km+c,b=lm+c}$
  • $\boxed{\color{Red} 若 a \equiv b \pmod m ，当且仅当 m \mid (a-b)}\\证明:$
    $\because a \equiv b \pmod m\\\therefore \exist k,l,c \in \Z ,a=km+c,b=lm+c\\\therefore m \mid (a-b)\Rightarrow m \mid (km+c-lm-c)\Rightarrow m \mid (km-lm)\Rightarrow m \mid (k-l)m\\\therefore 结论显然成立$

同余性质

证明：
$\because a \equiv b \pmod m\\\therefore \exist k,l,\alpha\in \Z，a=km+\alpha,b=lm+\alpha\\\therefore a+c \equiv b+c\pmod m\ \Rightarrow km+\alpha+c \equiv lm+\alpha+c \pmod m\\\Rightarrow km+(\alpha+c)\equiv lm+(\alpha+c)\pmod m\\\therefore 结论显然成立$

证明：
$\because a \equiv b \pmod m\\\therefore \exist k,l,\alpha\in \Z，a=km+\alpha,b=lm+\alpha\\\therefore ac\equiv bc \pmod m\\\Rightarrow (km+\alpha)c\equiv (lm+\alpha)c \pmod m\\\Rightarrow kcm+\alpha c\equiv lcm+\alpha c \pmod m\\\therefore 结论显然成立$

证明：
$\because a \equiv b\pmod m\\\therefore \exist k,l,c \in \Z ,a=km+c,b=lm+c\\\because c \equiv d \pmod m\\\therefore \exist \alpha,\beta,\gamma \in \Z,c=\alpha m+\gamma,d=\beta m+\gamma\\\therefore ac \equiv bd \pmod m \\\Leftrightarrow (km+c)(\alpha m+\gamma)\equiv(lm+c)(\beta m+\gamma)\pmod m\\\Leftrightarrow k\alpha m^2+\gamma km+c\alpha m+c\gamma\equiv l\beta m^2+l\gamma m+c\beta m+c\gamma\pmod m\\\therefore 结论显然成立$

证明$\mathbf{1}$：
$\because a^n \equiv b^n \pmod m \Leftrightarrow \begin{matrix}a^n\\\overbrace{a\cdot a\cdot a\cdots a}\end{matrix}\equiv \begin{matrix}b^n\\\overbrace{b\cdot b\cdot b\cdots b}\end{matrix} \pmod m\\\because a \equiv b \pmod m，a \equiv b \pmod m\\\therefore a \cdot a \equiv b \cdot b \pmod m \qquad(结论6)\\\because a \cdot a\equiv b\cdot b\pmod m，a \equiv b \pmod m\\\therefore (a \cdot a)\cdot a \equiv (b\cdot b)\cdot b \pmod m\qquad(结论6)\\\cdots\\\therefore 上述结论只需多次使用结论6即可得到$
证明$\mathbf{2}$：
$\because \exist k,l,c \in \Z，a=km+c,b=lm+c\\\therefore 当n=2时，有(km+c)^2 \Leftrightarrow (km)^2+2kmc+c^2,(lm+c)^2\Leftrightarrow (lm)^2+2lmc+c^2\\\quad当n=3时,有(km+c)^3\Leftrightarrow (km)^3+3(km)^2c+3kmc^2+c^3，(lm+c)^3\Leftrightarrow (lm)^3+3(lm)^2c+3lmc^2+c^3\\\quad\cdots\\\therefore 根据二项式定理，系数展开后常数项的为c^n,即(a^n)\bmod m=(a \bmod m)^n，(b^n)\bmod m=(b \bmod m)^n\\\because a \equiv b \pmod m\\\therefore a^n \equiv b^n \pmod m$

证明$\mathbf{1}$：
$\because a \bmod q=x,a \bmod p=x\\\therefore \exist k,l \in \Z ,a=kq+x=lp+x\\\therefore q \mid (a-x),p \mid (a-x)\\\therefore (a-x)是 q与p 的公倍数\\\therefore \exist \alpha \in \Z,(a-x)=\alpha pq\\\therefore a=\alpha pq+x\\\therefore a \bmod pq=x$
证明$\mathbf{2}$：
$\because a\bmod q=x,a\bmod p=x\\\therefore \exist k,l\in\Z,a=kq+x=lp+x\\\therefore kq+x=lp+x\\\quad kq=lp\\\because \gcd(q,p)=1\\\therefore \exist r\in\Z,k=rp\\\therefore a=rpq+x\\\therefore a\bmod pq=x$

基础定理

$\boxed{模M剩余类}:$将整数按照对于M的余数分为M类，使得每一类中的数对于模M同余，我们称这样的一个集合为在模M意义下的一个剩余类。
$\boxed{模M完全剩余系}：$在每一个摸M得剩余类下选择一个数作为这一个剩余类得代表，最后组成的M个数集合成为模M完全剩余系。

证明：
$试考虑ai\equiv aj\pmod p\\\because ai\equiv aj\pmod p\\\therefore p \mid a(i-j)\\\because \gcd(p,a)=1\\\therefore \exist r\in\Z,(i-j)=rp\\\therefore p\mid (i-j)\\\therefore i\equiv j\pmod p\\与条件不符，故结论不成立，原结论成立$

证明：
$考虑建立一个模p意义下的完全剩余系P=\{0,1,2,3,\cdots ,p-1\},将P中的元素分别乘a得Q=\{0,a,2a,3a,\cdots,(p-1)a\}\\\because \gcd(a,p)=1,P中元素两两不同余\\\therefore Q也是一个完全剩余系\\\therefore \exist pi\in P,qi\in Q,pi\equiv qi\pmod p\\\therefore P中元素之积与Q中元素之积同余（结论6）\\\therefore a^{p-1}(p-1)!\equiv(p-1)!\pmod p\\\therefore (a^{p-1}-1)(p-1)!\equiv 0\pmod p\\\because p为质数\\\therefore p\nmid (p-1)!\\\therefore \exist r\in\Z,(a^{p-1}-1)=rp\\\therefore p\mid (a^{p-1}-1)\\\therefore a^{p-1}-1\equiv 0\pmod p\\\therefore a^{p-1}\equiv 1\pmod p\\\therefore a^p\equiv a\pmod p$

证明：
$考虑一个模m的互质剩余系\{x_1,x_2,x_3\cdots x_{\varphi(m)}\}，其中x小于m，且都与m互质。\\\because \gcd(x_k,m)=1，\gcd(a,m)=1\\\therefore \gcd(a\cdot x_k,m)=1，且ax_i两两互质，即\{ax_1,ax_2,ax_3\cdots ax_{\varphi(m)}\}也是模m意义下的互质剩余系\~\\根据同模数同余式合并的性质，可以得到$

证毕

附加

$\bmod$性质

  1. $(a+b)\bmod m=(a\bmod m+b\bmod m)\bmod m$
  2. $(a\cdot b)\bmod m=(a\bmod m\cdot b\bmod m)\bmod m$
  3. $\dfrac{a}{b}\bmod m=(a\bmod m)\cdot b^{-1}~~~b^{-1}b\equiv1\pmod m$

$\boxed{a+c\equiv b+d\pmod m\Leftrightarrow (a\bmod m)+c\equiv (b\bmod m)+d}$
这个性质实际上就是把取余的步骤提前了一步，然后利用$\bmod$的性质就可得到。
有了这个性质，我们对于大数就可以在快读中提前取模，这样也是不影响最终的余数的。
https://www.luogu.com.cn/problem/P2613

将负数余数转为正数余数
$若a,m\in\Z,a<0,则a\bmod m\Leftrightarrow (a\bmod m+m)\bmod m$
两式余数等价，负数变为正数，可以由取余的性质得到。

总结

课后练习：
http://www.51nod.com/Challenge/Problem.html#problemId=1103
http://www.51nod.com/Challenge/Problem.html#problemId=3038