物理

整理预备轮数论知识点（2）

性质三：$a\equiv b\pmod{m},c\equiv d\pmod{m}\Rightarrow a+b\equiv c+d\pmod{m}$

设 $\begin{cases}a=Am+r_1\\b=Bm+r_2\end{cases},\begin{cases}a=Am+r_1\\b=Bm+r_2\end{cases}$

则 $a+c=m\left(A+C\right)+\left(r_1+r_2\right),b+d=m\left(B+D\right)+\left(r_1+r_2\right)$

$\therefore a+c\equiv b+d\equiv r_1+r_2\pmod{m}$

推论：$a\equiv b\pmod{m},k\in\mathbb{Z}\Rightarrow ak\equiv bk\pmod{m}$

连续使用性质三即可证明

性质四：$a\equiv b\pmod{m},c\equiv d\pmod{m}\Rightarrow ab\equiv cd\pmod{m}$

$\because a\equiv b\pmod{m},c\equiv d\pmod{m}$

$\therefore m\mid a-b,m\mid c-d$

$\therefore m\mid c\left(a-b\right)=ac-bc,m\mid b\left(c-d\right)=bc-bd$

$\therefore m\mid ac-bd$

$\therefore ab\equiv cd\pmod{m}$

推论：$a\equiv b\pmod{m},k\in\mathbb{N}\Rightarrow a^k\equiv b^k\pmod{m}$

连续使用性质四即可证明

性质五：$ak\equiv bk\pmod{m},k\in\mathbb{Z}\Leftrightarrow a\equiv b\pmod{\frac{m}{\left(k,m\right)}}$

①充分性

$\because m\mid k\left(a-b\right)$

设 $\left(k,m\right)=d,m=m_1d,k=k_1d,\left(k_1,m_1\right)=1$

$\therefore m_1d\mid k_1d\left(a-b\right)$

$\therefore m_1\mid k_1\left(a-b\right)$

$\therefore m_1\mid a-b$

即 $\frac{m}{\left(k,m\right)}\mid a-b$

即 $a\equiv b\pmod{\frac{m}{\left(k,m\right)}}$

②必要性

使用性质四即可证明

八：剩余类与完全剩余系

剩余类定义：

按余数分类，把整数分成有限个类别，每一类是一个剩余类。例如按照除以 $m$ 的余数分类，除以 $m$ 余 $k$ 的整数是一个剩余类。

剩余类性质：

性质一：对于正整数 $m$，有 $m$ 个剩余类。

性质二：定存在 $m$ 个数，模 $m$ 两两不同余。

性质三：任意 $m+1$ 个数，定有两数模 $m$ 同余。

完全剩余系定义：

每一个剩余类中挑出一个数，这一组数称为完全剩余系，简称完系。

例如模 $5$ 时，$0,1,2,3,4$ 是一组完系，且这一组被称为最小非负剩余；$-2,-1,0,1,2$ 也是一组完系，且这一组被称为绝对最小剩余。

完全剩余系性质：

性质一：$m$ 个整数，模 $m$ 两两不同余，构成一个完系。

性质二：若 $\left\{x_1,x_2,\dots,x_m\right\}$ 为模 $m$ 的一组完系，则对于整数 $a,b$ 且 $\left(a,m\right)=1$，$\left\{ax_1+b,ax_2+b,\dots,ax_m+b\right\}$ 也为模 $m$ 的一组完系。

①当 $a=0$ 时

$\because x_i\not\equiv x_j\pmod{m}$

若 $x_i+b\equiv x_j+b$

则 $x_i\equiv x_j\pmod{m}$，矛盾

$\therefore ax_i\not\equiv ax_j\pmod{m}$

②当 $b=0$ 时

$\because x_i\not\equiv x_j\pmod{m}$

若 $ax_i\equiv ax_j$

则 $ax_i\equiv ax_j\pmod{\frac{m}{\left(a,m\right)}}$，矛盾

$\therefore ax_i\not\equiv ax_j\pmod{m}$

③当 $ab\neq0$ 时

$\because \left\{x_1,x_2,\dots,x_m\right\}$ 为完系

$\therefore \left\{x_1+b,x_2+b,\dots,x_m+b\right\}$ 为完系

$\therefore \left\{ax_1+b,ax_2+b,\dots,ax_m+b\right\}$ 为完系

性质三：对于模 $m$ 的一个完系 $\left\{x_1,x_2,\dots,x_m\right\}$，当 $m$ 是奇数时，$x_1+x_2+\dots+x_m\equiv0\pmod{m}$

证明略