初等数论

· · 个人记录

luogu

看样子要写很久。

第〇章 注意

本帖的题目、性质会省略显然的条件。

证明，解析会省略部分容易的过程。

因为我数学是垃圾，所以表述有问题……那就是我的问题。

第一章 整除

一、概念

若 ak=b(a,b,k\in \mathbb{Z},a\not=0)，则记为 a\mid b，表示 a 能整除 b 或 b 能被 a 整除。

二、性质

①

若 a\mid b，b\mid c，则 a\mid c。

证：

b=k_1a,c=k_2b(k1,k2\in \mathbb{Z}) \therefore c=k_1k_2a \because k_1k_2\in \mathbb{Z} \therefore a \mid c

②

若 a\mid b，a\mid c，则 \forall x,y(x,y\in \mathbb{Z})，a\mid bx+cy。

证：

b=k_1a,c=k_2a(k_1,k_2\in \mathbb{Z}) \therefore bx+cy=ak_1x+ak_2y=a(k_1x+k_2y) \therefore a\mid bx+cy

③

简单不证。 ### ④ 若 $a\mid n$，$b\mid n$，$ax+by=1(x,y\in \mathbb{Z})$，则 $ab\mid n$。 试证 $\dfrac{n}{ab}\in \mathbb{Z}$，尝试构造 $\dfrac{1}{ab}$。 对等式做手脚。 证： >$$\therefore \frac{x}{b}+\frac{y}{a}=\frac{1}{ab}$$ >$$n=k_1a=k_2b$$ >$$\therefore n(\frac{x}{b}+\frac{y}{a})=\frac{n}{ab}$$ >$$\therefore k_2x+k_1y=\frac{n}{ab}$$ >$$\therefore ab(k_2x+k_1y)=n$$ >$$\therefore ab\mid n$$ ### ⑤ $b=qd+c$，则 $d\mid b$ 的充要条件是 $d\mid c$。 充要条件指的是对于性质 $\text{A}$ 和 $\text{B}$，**若 $\text{A}$ 能推出 $\text{B}$，则 $\text{B}$ 也能推出 $\text{A}$**。意思是，**要分别证明两个**。 简单不证。 ### ⑥ 若 $(a,b)=1$，则 $\nexists$ $k_1<b(a,b,k_1\in \mathbb Z^+)$，使 $b\mid k_1a$。 证明中，$f(n)$ 表示 $n$ 的所有质因子的集合。 证明： > $$\because (a,b)=1$$ > $$\therefore f(a)\cap f(b)=\emptyset$$ > $$\therefore f(b)\in f(k_1)$$ > $$\therefore k_1\ge b,b\mid k_1$$ ## 三、习题 [部分](https://www.luogu.com.cn/blog/487539/shuo-lun-xi-ti)。 ### ① 若 $2\mid n \bmod10$，则 $2\mid n$。 证明： > $$n=10k+r(r<10,k,r\in \mathbb Z)$$ > $$\therefore n\bmod 10=(10k+r)\bmod 10=r$$ > $$\therefore r=2p$$ > $$\therefore n=10k+2p=2(5k+p)$$ > $$\therefore 2\mid n$$ ### ② 由①可以推出被 $4,8,16...$ 整除的数 $n$ 的性质。 若 $4\mid n \bmod 100$，则 $4\mid n$。 若 $8\mid n \bmod 1000$，则 $8\mid n$。 …… 若 $2^m\mid n \bmod 10^m$，则 $2^m\mid n$。 证明： > $$10^m=(2\times5)^m=2^m\times5^m$$ > $$n=k10^m+r=k2^m5^m+r(r<10^m)$$ > $$\therefore n\bmod 10^m=r$$ > $$\therefore 2^m\mid r$$ > $$\therefore 2^m\mid n$$ ### ③ 令 $n=\overline{k_mk_{m-1}...k_2k_1}$，若 $$3\mid \sum_{i=1}^{m}k_i$$ 则 $3\mid n$。 也可以把 $3$ 换成 $9$。 证明： >$$n=\sum_{i=1}^m 10^{i-1}k_i=\sum_{i=1}^m (k_i+999...999 k_i)(\text{The number of 9 is }i-1)$$ >$$\therefore n=\sum_{i=1}^{m}k_i+ 9S(S=?)$$ > $$\because 3\mid \sum_{i=1}^{m}k_i$$ > $$\therefore 3\mid n$$ ### ④ 令 $n=\overline{k_mk_{m-1}...k_2k_1}$，若 $$11\mid (\sum_{i=2,2\mid i}^n k_i-\sum_{i=1,2\nmid i}^n k_i)$$ 则 $11\mid n$。 证明： 鸽鸽鸽。 ### ⑤ 若 $1001\mid (\lfloor \dfrac{n}{1000} \rfloor-(n\bmod 1000))$，则 $1001\mid n$。 证明： > $$n=1000k_1+r_1$$ > $$\therefore \lfloor \dfrac{n}{1000} \rfloor=k_1,n\bmod 1000=r_1$$ > $$\therefore 1001\mid k_1-r_1$$ > $$\therefore k_1\equiv r_1\pmod {1001}$$ > $$\therefore k_1=1001k_2+r_2,r_1=1001k_3+r_2$$ > $$\therefore n=1000\times 1001(k_2+k_3)+1001r_2=1001(1000k_2+1000k_3+r_2)$$ > $$\therefore 1001\mid n$$ ------- # 第二章 模运算 ## 一、概念 > gm：我们是OI的，$\bmod$ 可以用 $\%$ 代替。 但我觉得还是规范一点好，数学写 $\%$ 就无了。 求 $a\div b(a,b\in \mathbb{Z},b\not=0)$ 的余数的运算，记为 $a$ $\bmod$ $b$ ，表示 $a$ 模 $b$。 ## 二、性质 ### 1.分配律 对于 $+,-,\times$ 都适用，**对 $\div$ 不适用**。 #### ① $(a+b)\bmod c=(a\bmod c+b\bmod c)\bmod c$。 本题没有证明，因为如今所有的证明都要用到结论本身。在正解出来之前，我们只能默认它为公理。 提供伪证。 证明： >$$a=k_1c+r_1,b=k_2c+r_2$$ >$$\therefore (a+b)\bmod c=[c(k_1+k_2)+(r_1+r_2)]\bmod c=(r_1+r_2)\bmod c$$ 此处变形就用了待证的，接着往下。 >$$\therefore a\bmod c=r_1,b\bmod c=r_2$$ >$$\therefore (a\bmod c+b\bmod c)\bmod c=(r_1+r_2)\bmod c$$ >$$\therefore (a+b)\bmod c=(a\bmod c+b\bmod c)\bmod c=(r_1+r_2)\bmod c$$ #### ② $(a-b)\bmod c=(a\bmod c-b\bmod c)\bmod c

基本同上。

③

ab\bmod c=(a\bmod c\times b\bmod c)\bmod c

证明：与 ① 同设。

\therefore ab\bmod c=[(k_1c+r_1)(k_2c+r_2)]\bmod c=(k_1k_2c+k_1r_2c+k_2r_1c+r_1r_2)\bmod c=[c(k_1k_2+k_1r_2+k_2r_1)+r_1r_2]\bmod c=r_1r_2\bmod c \therefore a\bmod c=r_1,b\bmod c=r_2 \therefore ab\bmod c=(a\bmod c\times b\bmod c)\bmod c=r_1r_2\bmod c

④

a^b \bmod c=(a\bmod c)^b\bmod c

证明：大致同 ③。

\therefore (a\bmod c)^b\bmod c=[(kc+r)\bmod c]^b \bmod c=(r\bmod c)^b \bmod c \because r<c \therefore (a\bmod c)^b\bmod c = r^b\bmod c \therefore a^b\bmod c=(kc+r)^b\bmod c \therefore (kc+r)^b=cS+r^b(S=?) \therefore a^b\bmod c=(cS+r^b)\bmod c=r^b\bmod c \therefore a^b \bmod c=(a\bmod c)^b\bmod c=r^b\bmod c

2.自己想到的

若 a \bmod b=c，则 d\mid c(d\mid a,d\mid b)。

证明：

a=k_1b+c=k_2d,b=k_3d \therefore k_2d=k_1k_3d+c \therefore c=d(k_2-k_1k_3) \therefore d\mid c

3.放缩性

①

若 a\bmod b=c，则 ad\bmod bd=cd(d\in \mathbb{Z},d\not=0)。

简单不证。

②

若 a\bmod b=c，则 \dfrac{a}{d}\bmod \dfrac{b}{d}=\dfrac{c}{d}(d\mid a,d\mid b)。

证明：用到 2

d\mid c a=k_1d,b=k_2d, c=k_3d

由①得

\because k_1d \bmod k_2d=k_3d \therefore k_1 \bmod k_2=k_3 \because a=k_1d,b=k_2d, c=k_3d \therefore k_1=\dfrac{a}{d},k_2=\dfrac{b}{d},k_3=\dfrac{c}{d} \therefore \dfrac{a}{d}\bmod \dfrac{b}{d}=\dfrac{c}{d}

4.

若 (a,b)=1，则 0 \bmod b,a \bmod b,2a \bmod b,...,(b-1)a \bmod b 都不相等。

还可以写成，若 (a,b)=1，则对于 \forall k \in[0,n-1]，都有 x\in [0,b-1] 满足 ak\bmod b=x。

证明：反证法

先设有相等。要用到 第一章 二、⑥。

x,y(0\le y < x < b) \therefore xa\equiv ya \pmod b \therefore b\mid a(x-y) \because (a,b)=1 \therefore x-y\ge b \because 0\le y<x<b \therefore 1\le x-y<b

矛盾。

第三章 同余

一、概念

若 a \bmod m=b\bmod m，即 a,b 模 m 的值相等，则称 a,b 模 m 同余。

记为 a\equiv b \pmod m。

二、性质

① 自反性

a\equiv a \pmod m

只有用显然证。

② 对称性

若 a\equiv b \pmod m，则 b\equiv a \pmod m。

简单不证。

③ 传递性

若 a\equiv b \pmod m,b\equiv c\pmod m，则 a\equiv c\pmod m。

简单不证。

④ 推论1

若 a\equiv b\pmod m，则 m\mid a-b。

另一说法：则存在 a=b+km(k\in \mathbb Z)

证明：

a=k_1m+r,b=k_2m+r \therefore a-b=m(k_1-k_2) \therefore m\mid a-b,a=m(k_1-k_2)+b \therefore k=k_1-k_2

这个比较重要。

⑤ 同运算性

以下所有都有条件 a\equiv b\pmod m。

a+c\equiv b+c \pmod m a-c\equiv b-c \pmod m ac\equiv bc \pmod m

以上三个简单不证。

证明： 用到 **第一章 二、⑥**。 > $$a=k_1m+r,b=k_2m+r$$ > $$\because c\mid a,c\mid b$$ > $$\therefore c\mid a-b=m(k_1-k_2)$$ > $$\because (c,m)=1$$ > $$\therefore c\mid k_1-k_2$$ > $$\therefore \dfrac{a}{c}-\dfrac{b}{c}=\dfrac{a-b}{c}=\dfrac{m(k_1-k_2)}{c}=m\dfrac{k_1-k_2}{c}$$ > $$\therefore m\mid \dfrac{a}{c}-\dfrac{b}{c}$$ > $$\therefore \dfrac{a}{c}\equiv \dfrac{b}{c} \pmod m$$ ### ⑥ 若 $a\equiv b\ \pmod m,c\equiv d\ \pmod m$，则 $a+c\equiv b+d\ \pmod m

证明：

\therefore m\mid a-b,m\mid c-d \therefore m\mid(a-b)+(c-d)=(a+c)-(b+d) \therefore a+c\equiv b+d\pmod m

⑦

若 a\equiv b\ \pmod m,c\equiv d\ \pmod m，则 ac\equiv bd\ \pmod m。

证明：

a=k_1m+r_1,b=k_2m+r_1,c=k_3m+r_2,d=k_4m+r_2 ac-bd=(k_1m+r_1)(k_3m+r_2)-(k_2m+r_1)(k_4m+r_2)=m(k_1k_3m+k_1r_2+k_3r_1-k_2k_4m-k_2r_2-k_4r_1)+r_1r_2-r_1r_2=m(k_1k_3m+k_1r_2+k_3r_1-k_2k_4m-k_2r_2-k_4r_1) \therefore m\mid ac-bd \therefore ac\equiv bd \pmod m

第四章 排列组合

一、排列

在 n 个元素中，选出 m 个元素，在意顺序。

最终的方案数记为 A_n^m。

对于每个要选的位置，除了之前选过的个数 x，则还有 n-x 个可选，直到 m 个。

A_n^m=\prod_{i=n-m+1}^n i=\dfrac{n!}{(n-m)!}

二、组合

与排列的唯一区别是，不在意顺序。记为 C_n^m

对于选定的长度为 m 的答案数组，有 m! 种全排列，即 m! 种排列方式。现在，视之为 1 种。所以，

C_n^m=\dfrac{A_n^m}{m!}=\dfrac{n!}{m!(n-m)!}

特殊性质： C_n^m=C_n^{n-m}

数学上，把 n-m 和 m 替换，结果算出来一样。

意思上，因为不在意顺序，则长度为 m 数组确定后，剩下的长度为 n-m 的剩余数组也确定，两者都不在意顺序的话，就不会受长度的影响，所以相等。

三、盒子与球

此类题的主要思想是利用相同和不同的性质。

1.盒不同 球相同 无空盒

球相同，那就忽略球的顺序。容易想到 隔板法，即在 n 个球之间的 n-1 个空隙处插入 m-1 个分界线使之分为 m 块，答案为 C_{n-1}^{m-1}。

2.盒不同 球相同 可空盒

在 1 中，我们插的位置不会重复，这就保证了没有空盒。可以利用这一性质，增加 m 个虚球。

可得每个盒子里至少有 1 个球。

这样，我们再将每个盒子内的球的个数减去 1，就搞出了空盒的情况。答案为 C_{n+m-1}^{m-1}。

3.盒相同 球不同 无空盒

盒相同，就忽略盒的顺序。考虑数学方法无果，想到 dp。

盒的顺序无影响，所以不作为 dp 的阶段。定义 dp_{i,j} 表示前 i 个球放入 j 个盒子的方案数。注意，不是前 j 个盒子。

考虑怎么放。

dp_{i,j}=dp_{i-1,j-1}+dp_{i-1,j}\times j

答案为 dp_{n,m}。

4.盒相同 球不同 可空盒

很巧的是，上述我们的 dp_{i,j} 表示的是 j 个盒子无空盒的情况。那么其余的 m-j 个盒子就自然是空盒了，答案为 \sum_{j=1}^m dp_{n,j}。

5.盒不同 球不同 无空盒

盒子的顺序对答案有了影响。在 3 当中，我们的 dp_{n,m} 是盒子不按照顺序的方案数。容易想到，此时相当于确定了球的摆放，把 m 个盒子进行排列去依次匹配。

所以答案为 dp_{n,m}\times m! 。

6.盒不同 球不同 可空盒

刚开始想用 5 推，发现想复杂了。

可以空盒，球和盒的顺序都对答案有影响。即 n 个球可以随机地放入 m 个盒中，答案为 m^n。

7.盒相同 球相同 可空盒

8.盒相同 球相同 无空盒

第五章 最小公约数与最大公倍数

一、概念

公约数：若 d\mid a_1,d\mid a_2,...,d\mid a_n，则称 d 为 a_1,a_2,a_k 的公约数。a,b 的最小公约数记为 (a,b)。OI 中一般用 \gcd。

公倍数：若 a_1\mid d,a_2\mid d,...,a_n\mid d，则称 d 为 a_1,a_2,a_k 的公倍数。a,b 的最大公倍数记为 [a,b]。OI 中一般用 \text{lcm}。

二、性质

①

(a,b)[a,b]=ab

证明：

a=\prod_{i=1}^m p_i^{e_i}(p_i \in \text{prime},e_i\in \mathbb Z),b=\prod_{i=1}^m p_i^{r_i}(p_i \in \text{prime},r_i\in \mathbb Z) \therefore (a,b)=\prod_{i=1}^m p_i^{\min\{e_i,r_i\}},[a,b]=\prod_{i=1}^m p_i^{\max\{e_i,r_i\}} \therefore ab=\prod_{i=1}^m p_i^{e_ir_i}=\prod_{i=1}^m p_i^{\max\{e_i,r_i\}\min\{e_i,r_i\}}=(a,b)[a,b]

② 辗转相除

(a,b)=(b,a\bmod b)

证明：

第六章 其它定理

一、裴蜀定理

若关于 x,y 的方程 ax+by=m 有整数解，则 (a,b)\mid m。

证明：

\because (a,b)\mid a,(a,b)\mid b \therefore (a,b)\mid ax+by=m

若 (a,b)\mid m，则关于 x,y 的方程 ax+by=m 有 \mathbb Z 解。

用到扩展欧几里得证明。

二、扩展欧几里得定理

已知 a,b\in \mathbb Z，求 ax+by=(a,b) 的 \mathbb Z 解。

通常 x 与 y 相反。

证明：

ax_1+by_1=(a,b),bx_2+(a\bmod b)y_2=(b,a\bmod b) \because (a,b)=(b,a\bmod b) \therefore ax_1+by_1=bx_2+(a\bmod b)y_2=bx_2+(a-\lfloor \dfrac{a}{b} \rfloor b)y_2=ay_2+b(x_2-\lfloor \dfrac{a}{b} \rfloor y_2) \because ax_1+by_1=ay_2+b(x_2-\lfloor \dfrac{a}{b} \rfloor y_2) \therefore \exists x_1,y_1 x_1=y_2,y_1=x_2-\lfloor \dfrac{a}{b} \rfloor y_2 \therefore (x_1,y_1)\Leftarrow (x_2,y_2),(x_{n-1},y_{n-1})\Leftarrow (x_n,y_n) \text{When i is n, } a=kb {n+1} \therefore \exists b,x_n,y_n b=y_n=0,x_n=1

这样一定能求到 (x_1,y_1)。

代码实现：

void exgcd(int a, int b) {
    if(b == 0) {
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b);
    int t = x;
    x = y, y = t - a / b * y;
}

三、费马小定理

若 p\in \text{prime},a\not=kp，则 a^{p-1}\bmod p=1。

证明：

a·2a·3a·...·(p-1)a \bmod p=a^{p-1}(p-1)!\bmod p \text{ (1)}