物理

整理预备轮数论知识点

一：整除理论

整除式定义：

对于 $a,b\in\mathbb{Z},a\neq0$，若存在 $q\in\mathbb{Z}$，使 $b=aq$，则称 $a$ 整除 $b$，也称 $b$ 被 $a$ 整除，$b$ 是 $a$ 的倍数，$a$ 是 $b$ 的因数。记作 $a\mid b$。

整除式性质：

性质一：$a\mid b\Leftrightarrow-a\mid b\Leftrightarrow a\mid-b\Leftrightarrow\left|a\right|\mid\left|b\right|$

设 $b=aq$，可以得到 $-b=a\left(-q\right)$，所以 $a\mid-b$；也可以得到 $b=\left(-a\right)\left(-q\right)$，所以 $-a\mid b$；也可以得到 $\left|a\right|=\left|a\right|\left|q\right|$，所以 $\left|a\right|\mid\left|b\right|$

性质二：若 $a\mid b,b\mid c$，则 $a\mid c$。

设 $b=k_1a,c=k_2b$，所以 $c=k_1k_2a$，所以 $a\mid c$

性质三：$a\mid b,a\mid c\Leftrightarrow\forall x,y\in\mathbb{Z},a\mid bx+cy$

①充分性

$\because a\mid b,a\mid c$

$\therefore b=k_1a,c=k_2a$

$\therefore bx+cy=k_1ax+k_2ay=a(k_1x+k_2y)$

$\therefore a\mid bx+cy$

②必要性

$\because\forall x,y\in\mathbb{Z},a\mid bx+cy$

令 $x=1,y=0$ 和 $x=0,y=1$，可以分别得到 $a\mid b,a\mid c$

性质四：$m\neq0,a\mid b\Leftrightarrow am\mid bm$

①充分性

$\because a\mid b$

$\therefore b=aq$

$\therefore bm=aqm$

$\therefore bm\mid am$

②必要性

$\because am\mid bm$

$\therefore bm=amq$

又 $\because m\neq0$

$\therefore b=aq$

$\therefore a\mid b$

性质五：$a\mid b,b\mid a\Leftrightarrow a=\pm b\Leftrightarrow\left|a\right|=\left|b\right|$

由性质六，可得 $\left|a\right|\le\left|b\right|,\left|b\right|\le\left|a\right|$

所以 $\left|a\right|=\left|b\right|$，即 $a=\pm b$

性质六：$b\neq0,a\mid b\Rightarrow\left|a\right|\le\left|b\right|$

$\because a\mid b$

$\therefore b=aq$

$\therefore \left|b\right|=\left|a\right|\left|q\right|$

又 $\because b\neq0$

$\therefore q\neq0$

又 $\because q\in\mathbb{Z}$

$\therefore \left|q\right|\ge1$

$\therefore\left|a\right|\le\left|b\right|$

二：质数合数

自然数的性质：

最小自然数原理：若有一个组成元素均为自然数的集合，其中必有一个最小的元素。

若 $n$ 为自然数，则 $n+1$ 也为自然数。

质数定义：

若 $p\neq0,\pm1$，且 $p$ 只有 $\pm1$ 和 $\pm p$ 四个约数，则称 $p$ 为质数/素数。一般默认正质数。这四个约数称为显然约数。

合数定义：

若存在 $1\lt d\le e\lt a$ 使 $de=a$，则 $a$ 为合数。

合数性质：

性质一：合数一定有质数因数。

假设合数 $a$ 的因数有 $2\lt d_1\lt d_2\lt\dots\lt d_k$，如 $d_1$ 不是合数，设 $d_1=mn$。

显然 $m,n$ 是 $a$ 的因数，且 $m,n\lt d_1$。这与 $d_1$ 是最小的因数矛盾。

所以 $d_1$ 是质数，$a$ 有质数因数。

质数性质：

性质一：质数无穷

如质数有有限个，为 $p_1,p_2,\dots,p_n$

设 $a=p_1p_2\dots p_n+1$，显然这些质数都不是 $a$ 的因数。所以 $a$ 也是质数

性质二：只有一个偶质数 $2$

若 $a\gt2,2\mid a$，则 $a=2k$，为合数

性质三：若质数 $p\mid ab$，则 $p\mid a$ 或 $p\mid b$

见评论区

三：奇数偶数

奇数偶数定义：

如果一个数能被 $2$ 整除，称为偶数，否则是奇数。

奇数偶数性质：

性质一：奇数 $\neq$ 偶数

性质二：奇数的因数均为奇数

性质三：奇数个奇数之和为奇数，偶数个奇数之和为偶数

性质四：一个数加奇数，奇偶性改变；加偶数，奇偶性不变

性质五：整数乘以奇数，奇偶性不变；乘以偶数，变为偶数

带余除法：

任意 $a,b\in\mathbb{Z}$，存在且唯一存在一组整数 $q$ 与 $r$，使 $a=bq+r$，其中 $0\le r\lt b$。

①存在性

存在 $bq\le a\lt b\left(q+1\right)$

即 $0\le a-bq\lt b$

令 $r=a-bq$

$\therefore a=bq+r,0\le r\lt b$

②唯一性

若存在另一组 $q',r'$ 使得 $a=bq'+r',0\le r'\lt b$

$\therefore bq+r=bq'+r'$

$\therefore b\left(q-q'\right)=r'-r$

$\therefore b\mid r'-r$

若 $r'-r\neq0$ 即 $r\neq r'$ 时

则 $\left|b\right|\le\left|r'-r\right|\lt\left|b-0\right|=\left|b\right|$，矛盾

$\therefore b=b',r=r'$

四：约数倍数

若 $a\mid b$，$a$ 是 $b$ 的因数（约数），$b$ 是 $a$ 的倍数。

最大公因数的定义：

若 $d\mid a_1,d\mid a_2,\dots,d\mid a_k$ 且 $a_1a_2\dots a_k\neq0$，则 $d$ 为 $a_1,a_2,\dots,a_k$ 的公因数。最大公因数就是最大的公因数。记作 $\left(a_1,a_2,\dots,a_k\right)$。

最大公因数的性质：

性质一：$\left(a_1,a_2,\dots,a_k\right)=\left(-a_1,a_2,\dots,a_k\right)=\left(a_1,-a_2,\dots,a_k\right)=\dots=\left(a_1,a_2,\dots,-a_k\right)$

设 $d=\left(a_1,a_2,\dots,a_k\right)$，设 $a_1=dq_1,a_2=dq_2,\dots,a_k=dq_k$

显然 $-a_1=d\left(-q_1\right),-a_2=d\left(-q_2\right),\dots,-a_k=d\left(-q_k\right)$

且 $\forall d'\gt d$，$d'$ 不是他们的公因数

所以 $d=\left(-a_1,a_2,\dots,a_k\right)=\left(a_1,-a_2,\dots,a_k\right)=\dots=\left(a_1,a_2,\dots,-a_k\right)$

性质二：若 $a_1\mid a_2$，则 $\left(a_1,a_2\right)=\left|a_1\right|$。

显然 $\left|a_1\right|\mid a_1,\left|a_1\right|\mid a_2$，所以 $\left(a_1,a_2\right)=\left|a_1\right|$

且 $\forall d\gt\left|a_1\right|,d\nmid a_1$

性质三：$\forall x\in\mathbb{Z},\left(a_1,a_2\right)=\left(a_1,a_2,a_1x\right)$

设 $d=\left(a_1,a_2\right)$，且 $a_1=kd$

显然 $d\mid kdx=a_1x$，

且 $\forall d'\gt d,d'\nmid a_1\lor d'\nmid a_2$

所以 $d=\left(a_1,a_2,a_1x\right)$

性质四：$\forall x\in\mathbb{Z},\left(a_1,a_2\right)=\left(a_1,a_2+a_1x\right)$

设 $d_1=\left(a_1,a_2\right),d_2=\left(a_1,a_2+a_1x\right)$

①$\because d_1=\left(a_1,a_2\right)$

$\therefore d_1\mid a_1,d_1\mid a_2$

$\therefore d_1\mid a_2+a_1x$

即 $d_1\mid a_1,d_1\mid a_2+a_1x$

又 $\because d_2=\left(a_1,a_2+a_1x\right)$

$\therefore d_1\le d_2$

②$\because d_2=\left(a_1,a_2+a_1x\right)$

$\therefore d_2\mid a_1,d_2\mid a_2+a_1x$

$\therefore d_2\mid a_2$

即 $d_2\mid a_2,d_2\mid a_1$

又 $\because d_1=\left(a_1,a_2\right)$

$\therefore d_1\lt d_2$

$\therefore d_1=d_2$

性质五：设 $m\mid\left(a_1,a_2\right)$，有 $\left(a_1,a_2\right)=m\left(\frac{a_1}{m},\frac{a_2}{m}\right)$。

证明留给读者

最小公倍数的定义：

若 $a_1\mid d,a_2\mid d,\dots,a_k\mid d$，则 $d$ 为 $a_1,a_2,\dots,a_k$ 的公因数。最小公倍数就是最小的正公倍数。记作 $\left[a_1,a_2,\dots,a_k\right]$。

最小公倍数的性质：

性质一：若 $m\lt0$，则有 $m\left[a_1,a_2\right]=\left[ma_1,ma_2\right]$

设 $L=\left[ma_1,ma_2\right],L'=\left[a_1,a_2\right]$

①有 $ma_1\mid L,ma_2\mid L$

$\therefore a_1\mid\frac{L}{m},a_2\mid\frac{L}{m}$

$\therefore\frac{L}{m}$ 为 $a_1,a_2$ 的公倍数

$\therefore\frac{L}{m}\ge L'$

即 $L\ge L'm$

②有 $a_1\mid L',a_2\mid L'$

$\therefore ma_1\mid mL',ma_2\mid mL'$

$\therefore mL'$ 为 $ma_1,ma_2$ 的公倍数

$\therefore L\le mL'$

$\therefore L=mL'$

共同性质：

性质一：公因数一定是最大公因数的因数，公倍数一定是最小公倍数的倍数

证明略

性质二：$ab=\left(a,b\right)\left[a,b\right]$

设 $d=\left(a,b\right),a=a_1d,b=b_1d$

显然 $\left(a_1,b_1\right)=1$

$\therefore\left[a,b\right]=\left(a_1d,b_1d\right)=d\left(a_1,b_1\right)=da_1b_1$

$\therefore\left(a,b\right)\left[a,b\right]=d\cdot da_1b_1=da_1\cdot da_2=ab$

求法：

更相减损

利用 $\left(a,b\right)=\left(a,a-b\right)$ 的性质。

e.g.$\left(35,120\right)=\left(35,95\right)=\left(35,60\right)=\left(35,25\right)=\left(10,25\right)=\left(10,15\right)=\left(10,5\right)=5$

辗转相除

若 $a=bq+r,0\le r\lt b$，则有 $\left(a,b\right)=\left(r,b\right)$。

e.g.$\left(1920,1680\right)=\left(240,1680\right)=240$

辗转相除比更相减损快一些。

短除法

e.g.$\left(100,60\right)=2\times2\times5=20$

$\begin{aligned}2|\underline{100~60}\\2|\underline{50~30}\\5|\underline{25~15}\\~~~5~~3\end{aligned}$

也可以得到 $\left[100,60\right]=2\times2\times5\times5\times3=300$

瞪眼法

略

$\sout{肥鼠}$斐蜀定理：

设 $a,b\in\mathbb{Z}$，且 $\left(a,b\right)=d$，则存在 $x,y\in\mathbb{Z}$，使得 $ax+by=d$。

证明略

斐蜀定理的推论：

推论一：$\left(a,b\right)=1\Leftrightarrow\exists x,y\in\mathbb{Z},ax+by=1$

略

推论二：若 $a\mid c,b\mid c,\left(a,b\right)=1$，则 $ab\mid c$

显然 $ab\mid bc,ab\mid ac$

根据裴蜀定理，存在 $x,y$ 使 $ax+by=1$

则 $ab\mid xac+ybc=c$

推论三：若 $a\mid bc,\left(a,b\right)=1$，则 $a\mid c$

略

推论四：若 $\left(a,b\right)=1$，则 $\left(a,bm\right)=\left(a,m\right)$

$\left(a,m\right)=\left(a,m\left(a,b\right)\right)=\left(a,\left(am,bm\right)\right)=\left(a,am,bm\right)=\left(a,bm\right)$

五：算术基本定理

算术基本定理：

若 $n$ 为大于 $1$ 的正整数，$n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ 的形式唯一。

假设 $a=p_1p_2\dots p_k$，且 $p_1\le p_2\le\dots\le p_k$

且 $a=m_1m_2\dots m_k$，且 $m_1\le m_2\le\dots\le m_l$

①有 $p_1\mid a=m_1m_2\dots m_l$

$\therefore p_1\mid m_i$

则 $p_1=m_i$

同理 $m_1\mid n=p_1p_2\dots p_k$

$\therefore m_1\mid p_j$

$\therefore m_1=p_j$

$\therefore m_1=p_j\ge p_1=m_j$

又 $\because m_j\ge m_1$

$\therefore m_1=m_j$

即 $m_1=p_1$

②设 $x_1=\frac{a}{p_1}=p_2p_3\dots p_k,y_1=\frac{a}{m_1}=m_2m_3\dots m_l$

可以得到 $m_2=p_2$

同理 $m_3=p_3,m_4=p_4,\dots$

③设 $l\ge k$

若 $l\gt k$

$\therefore m_{k+1}m_{k+2}\dots m_l=1$

矛盾，所以 $l=k$

$\therefore p_1=m_1,p_2=m_2,\dots,p_k=m_k$

推论：

推论一：因数个数 $\operatorname{d}{\left(n\right)}=\left(\alpha_1-1\right)\left(\alpha_2-1\right)\dots\left(\alpha_k-k\right)$

可根据乘法原理证明，具体证明略

推论一的推论：$\sqrt{n}\in\mathbb{Z}\Leftrightarrow2\nmid\operatorname{d}{\left(n\right)}$

①充分性

设 $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$

$\because\sqrt{n}\in\mathbb{Z}$

$\therefore2\mid\alpha_1,2\mid\alpha_2,\dots,2\mid\alpha_k$

$\therefore2\nmid\alpha_1-1,2\nmid\alpha_2-1,\dots,2\nmid\alpha_k-1$

$\therefore2\nmid\operatorname{d}{\left(n\right)}=\left(\alpha_1-1\right)\left(\alpha_2-1\right)\dots\left(\alpha_k-k\right)$

②必要性

$\because2\nmid\operatorname{d}{\left(n\right)}=\left(\alpha_1-1\right)\left(\alpha_2-1\right)\dots\left(\alpha_k-k\right)$

$\therefore2\nmid\alpha_1-1,2\nmid\alpha_2-1,\dots,2\nmid\alpha_k-1$

$\therefore2\mid\alpha_1,2\mid\alpha_2,\dots,2\mid\alpha_k$

$\therefore\sqrt{n}\in\mathbb{Z}$

推论二：约数和 $\delta\left(n\right)=\left(p_1^0+p_1^1+\dots+p_1^{\alpha_1}\right)\left(p_2^0+p_2^1+\dots+p_2^{\alpha_2}\right)\dots\left(p_k^0+p_k^1+\dots+p_k^{\alpha_k}\right)$

$\delta\left(x\right)=\left(\frac{p_1^{\alpha_1+1}}{p_1-1}\right)\left(\frac{p_2^{\alpha_2+1}}{p_2-1}\right)\dots\left(\frac{p_k^{\alpha_k+1}}{p_k-1}\right)$

证明略

六：高斯函数与阶乘

高斯函数的定义：

$\left[x\right]$ 表示不超过 $x$ 的最大整数。

$\left\{x\right\}=x-\left[x\right]$

高斯函数的性质：

性质一：$x=\left[x\right]+\left\{x\right\}$

性质二：$x-1\lt\left[x\right]\le x,0\le\left\{x\right\}\lt1,\left[x\right]\le x\lt\left[x\right]+1$

性质三：$\left[x\right]$ 是不减函数，即 $\frac{\sout{\mathrm{d}\left[x\right]}}{\sout{\mathrm{d}x}}\sout{\le0}$

性质四：若 $n\in\mathbb{Z}$，则 $\left[x+n\right]=\left[x\right]+n,\left\{x+n\right\}=\left\{x\right\}$

性质五：$\left[x\right]+\left[y\right]\le\left[x+y\right]\le\left[x\right]+\left[y\right]+1$

性质六：若 $x,y\le0$，则 $\left[x\right]\left[y\right]\le\left[xy\right]$

高斯函数的运用：

$n!$ 中 $p$ 的指数：$\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\dots+\left[\frac{n}{p^k}\right]$

（设 $p^k\le n\lt p^{k+1}$）

高斯函数方程：

分离 $\left[~\right]$，去除 $\left[~\right]$（利用性质列不等式确定 $x$ 的范围），分类讨论，检验。

e.g.解方程：$6x-3\left[x\right]+7=0$

$3\left[x\right]=6x+7\Rightarrow\left[x\right]=\frac{6x+7}{3}\Rightarrow x-1\lt\frac{6x+7}{3}\le x$

解不等式，得到 $-\frac{10}{3}\lt x\le-\frac{7}{3}$

①$\left[x\right]=-3$

代入，得 $6x-3\times3+7=0$，解得 $x=\frac{19}{6}$

②$\left[x\right]=-4$

代入，得 $6x-3\times4+7=0$，解得 $x=\frac{8}{3}$

经检验，$x=\frac{19}{6}$ 和 $x=\frac{8}{3}$ 都为方程的解

七：同余理论

同余定义：对于 $a,b\in\mathbb{Z}$，若 $a,b$ 除以 $m$ 余数相同，则 $a,b$ 在模 $m$ 意义下同余。

记作 $a\equiv b\pmod{m}$

同余性质：

性质一：自等性、自反性和传递性

性质二：$a\equiv b\pmod{m}\Leftrightarrow\begin{cases}a=mq_1+r_1\\b=mq_2+r_2\\r_1=r_2\end{cases}\Leftrightarrow m\mid a-b$