物理

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

$\color{blue}{\boxed{\color{red}{\text{请{}先{}阅{}读{}《{}整{}理{}预{}备{}轮{}数{}论{}知{}识{}点{}》{}再{}看{}本{}帖{}。}}}}$

性质三：$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}c=Cm+r_1\\d=Dm+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}$

证明略

九：数论常用定理

费马小定理：

$p$ 为素数，$a$ 与 $p$ 互素，则 $a^{p-1}\equiv1\pmod{p}$。

对于 $p$ 的一个“完系”$\left\{1,2,\dots p-1\right\}$

它的每一个元素乘以 $a$ 后也是一个“完系”$\left\{a,2a,\dots a\left(p-1\right)\right\}$

显然它们模 $p$ 后是一一对应的，所以分别求积后模 $p$ 相等

$\therefore\left(p-1\right)!\equiv a^{p-1}\left(p-1\right)!\pmod{p}$

又 $\because\left(\left(p-1\right)!,m\right)=1$

$\therefore a^{p-1}\equiv1\pmod{p}$

缩系定义：对模 $n$ 的一个完系中，与 $n$ 互质的数构成的集合称为缩系。

欧拉函数定义：欧拉函数 $\phi\left(n\right)$ 为缩系元素个数。

缩系性质：若 $\left\{x_1,x_2,\dots,x_{\phi\left(n\right)}\right\}$ 为模 $n$ 的一个缩系且 $\left(a,n\right)=1$，则 $\left\{ax_1,ax_2,\dots,ax_{\phi\left(n\right)}\right\}$ 也为缩系。

欧拉函数性质：

性质一：若 $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$，则 $\phi\left(n\right)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\dots\left(1-\frac{1}{p_k}\right)$

性质二：若 $m$ 和 $n$ 互质，则 $\phi\left(mn\right)=\phi\left(m\right)\phi\left(n\right)$

欧拉定理：若 $a$ 与 $m$ 互质，则 $a^{\phi\left(m\right)}\equiv1\pmod{m}$。

对于 $p$ 的一个缩系 $\left\{x_1,x_2,\dots x_{\phi\left(m\right)}\right\}$

它的每一个元素乘以 $a$ 后也是一个完系 $\left\{ax_1,ax_2,\dots ax_{\phi\left(m\right)}\right\}$

显然它们模 $p$ 后是一一对应的，所以分别求积后模 $p$ 相等

$\therefore\left(\phi\left(m\right)\right)!\equiv a^{\phi\left(m\right)}\left(\phi\left(m\right)\right)!\pmod{m}$

又 $\because\left(\left(\phi\left(m\right)\right)!,m\right)=1$

$\therefore a^{\phi\left(m\right)}\equiv1\pmod{m}$

中国剩余定理：

若 $m_1,m_2,\dots,m_k$ 两两互质，对任意整数 $a_1,a_2,\dots,a_k$，

同余方程组 $\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\dots\\x\equiv a_k\pmod{m_k}\end{cases}$ 的解存在且唯一，

且解是 $x\equiv M_1M_1^{-1}a_1+M_2M_2^{-1}a_2+\dots+M_1M_1^{-1}a_1\pmod{m}$。

其中 $m=m_1m_2\dots m_k$，且 $m=m_jM_j$，以及 $M_j^{-1}$ 是满足 $M_jM_j^{-1}\equiv1\pmod{m_j}$ 的一个整数。

十：一次不定方程

一次不定方程性质：

性质一：一次不定方程 $ax+by=c$ 有整数解的充分必要条件是 $\left(a,b\right)\mid c$。

①充分性

设 $\left(a,b\right)=k,a=ka_1,b=kb_1$

$\therefore ka_1x+kb_1y=c$

即 $k\left(a_1x+b_1y\right)$

又 $a_1x+b_1y\in\mathbb{Z}$

$\therefore k\mid c$

②必要性

设 $ax_0+by_0=\left(a,b\right)$

又 $\left(a,b\right)\mid c$

设 $c=\left(a,b\right)c_1$

$\therefore ax_0c_1+by_0c_1=\left(a,b\right)c_1$

$\therefore a\left(x_0c_1\right)+\left(by_0c_1\right)=\left(a,b\right)c_1$

解为 $\begin{cases}x=x_0c_1\\y=y_0c_1\end{cases}$

性质二：一次不定方程 $ax+by=c$ 的解为 $\begin{cases}x=x_0+\frac{b}{\left(a,b\right)}\\y=y_0+\frac{a}{\left(a,b\right)}\end{cases}$，其中 $\begin{cases}x=x_0\\y=y_0\end{cases}$ 是一组特解。

证明略

同余方程性质：

性质一：$ax+b\equiv 0\pmod{m}$ 有解的充要条件为 $\left(a,m\right)\mid b$。

①充分性

$\because\exists c\in\mathbb{Z},ac\equiv b\pmod{m}$

$\therefore ac-b=km,k\in\mathbb{Z}$

$\therefore b=km-ac$

令 $d=\left(a,m\right),d\mid m,d\mid a$

$\therefore d\mid km-ac=b$

②必要性

设 $d=\left(a,m\right),d\mid b$

设 $b=kd$

$\therefore d=au+mv$

$\therefore b=kd=kau+kmv$

令 $c=-ku$

$\therefore ac+b\equiv0\pmod{m}$

性质二：$\left(a,m\right)=1$ 时，方程 $ax+b\equiv0\pmod{m}$ 对于 $\forall b\in\mathbb{Z}$ 有解且唯一。

若 $ax_1+b\equiv0\pmod{m},ax_2+b\equiv0\pmod{m}$

$\therefore a\left(x_1-x_2\right)\equiv0\pmod{m}$

$\therefore m\mid a\left(x_1-x_2\right)$

又 $\left(a,m\right)=1$

$\therefore m\mid x_1-x_2$

$\therefore x_1\equiv x_2\pmod{m}$

性质三：若 $m\mid\left(a,m\right)$，方程$ax+b\equiv0\pmod{m}$ 的解有 $\left(a,m\right)=d$ 个。

设 $d=\left(a,m\right)$

显然 $\left(\frac{a}{d},\frac{m}{d}\right)=1$

则方程 $\frac{a}{d}x+\frac{b}{d}\equiv0\pmod{\frac{m}{d}}$ 只有一个解，设为 $x\equiv c\pmod{\frac{m}{d}}$

即 $x=c+k\frac{m}{d},k\in\mathbb{Z}$

设 $k=qd+r,0\le r\lt d$

则 $x=c+qm+r\frac{m}{d}\equiv c+r\frac{m}{d}\pmod{m}$

若有 $0\le i\lt j\le d$ 使 $c+i\frac{m}{d}\equiv c+j\frac{m}{d}\pmod{m}$

$\therefore\frac{im}{d}\equiv\frac{jm}{d}\pmod{m}$

$\therefore\frac{im}{d}-\frac{jm}{d}=tm,t\in\mathbf{Z}$

$\therefore j-i=kd$

$\therefore d\mid j-i$

$\therefore i=j$

所以 $x=c,x=c+\frac{m}{d},x=c+2\frac{m}{d},\dots,x=c+\left(d-1\right)\frac{m}{d}$ 模 $m$ 两两不同余，它们为原方程的 $d$ 个解

十一：高次方程

勾股方程的定义：方程 $x^2+y^2=z^2$。这个方程的整数解也称为勾股数。其中三个数两两互质的解是本原解，也称本原勾股数组。

勾股方程的解：若 $\begin{cases}\left(n,m\right)=1\\n\gt m\\2\nmid n+m\end{cases},k\in\mathbb{Z}$，则 $\begin{cases}x=2kmn\\y=k\left(n^2-m^2\right)\\z=k\left(n^2+m^2\right)\end{cases}$

设 $\left(a,b,c\right)$ 是一组本原勾股数组

若 $a\equiv b\equiv 1\pmod{2}$

则 $c^2\equiv2\pmod{4}$，矛盾

则 $a,b$ 中定有一偶数，设为 $a$，则 $b,c$ 为奇数

$a^2=c^2-b^2=\left(c+b\right)\left(c-b\right)\equiv0\pmod{4}$

又 $c-b\equiv c+b\pmod{2}$

$\therefore c-b\equiv c+b\equiv0\pmod{2}$

则 $\left(\frac{a}{2}\right)=\left(\frac{c+b}{2}\right)\left(\frac{c-b}{2}\right)$

$\because\left(c,b\right)=1,b\equiv c\equiv1\pmod{2}$

$\therefore\left(\frac{c+b}{2},\frac{c-b}{2}\right)=\left(\frac{c+b}{2},\frac{c+b+c-b}{2}\right)=\left(\frac{c+b}{2},c\right)=\left(c+b,c\right)=\left(b,c\right)=1$

设 $\frac{c+b}{2}=m,\frac{c+b}{2}=n,\left(m,n\right)=1,n\gt m,2\nmid n+m$

$\therefore\begin{cases}a=2mn\\b=m^2-n^2\\c=m^2+n^2\end{cases}$

（全文完）