数论 初步

0x01 整除

概念： 设 $a,b\in \mathbb{Z}$ 且 $a\ne 0$，如果 $\exists q\in \mathbb{Z}$，使得 $a\times q=b$，则 $b$ 能被 $a$ 整除，记为 $a\mid b$。

---

性质：

1. 传递性：如果 $a\mid b$ 且 $b\mid c$，则 $a\mid c$。

2. 若$a\mid b$ 且 $a\mid c$ 则对于 $\forall a,b\in \mathbb{Z}$，有 $a\mid (bx+cy)$。

3. 设 $m$ 不为 $0$，则 $a\mid b$ 等价于 $ma\mid mb$。

4. 设 $x,y\in \mathbb{Z}$ 满足下式：$ax+by=1$，且 $a\mid n$，$b\mid n$，那么 $ab\mid n$

5. 若 $\exists b,q,d,c\in \mathbb{Z}$ 且 $b=q\times d+c$，那么 $d\mid b$ ，$d\mid c$ 可以互推。

---

证明：

1. 记 $b=a{k}_a(k_a\in \mathbb{Z})$，且 $c=b{k}_b(k_b\in \mathbb{Z})$

则有 $c=(a{k}_a)k_b$

即 $c=k_a{k}_{b}a$

其中 $k_a,k_b\in \mathbb{Z}$

$\therefore a\mid c$

---

2. 记 $b=a{k}_b(k_b\in \mathbb{Z})$，且 $c=a{k}_c(k_c\in \mathbb{Z})$

$\therefore bx+cy=(a{k}_b)x+(a{k}_c)y$

即 $bx+cy=a(k_{b}x+k_{c}y)$

其中 $k_b,k_c,x,y\in \mathbb{Z}$

$\therefore (k_{b}x+k_{c}y)\in \mathbb{Z}$

故 $a\mid (bx+cy)$

---

3. 记 $b=a{k}_b(k_b\in \mathbb{Z})$

$\therefore mb=ma{k}_b(k_b\in \mathbb{Z})$

且 $m\in \mathbb{Z},m\ne 0$

$\therefore ma\mid mb$

---

4. $\because ax+by=1$

$\therefore \frac{x}{b}+\frac{y}{a}=\frac{1}{ab}$

$\therefore \frac{n}{ab}=\frac{xn}{b}+\frac{ny}{a}$

又由题： $a{k}_a=n,b{k}_b=n(k_a,k_b\in \mathbb{Z})$

$\therefore \frac{n}{ab}=k_{a}y+k_{b}x$

即 $n=ab(k_{a}y+k_{b}x)$

$\because k_a,k_b,x,y\in \mathbb{Z}$

$\therefore ab\mid n$

---

5.1

记 $b=d\ast k_b(k_b\in \mathbb{Z})$

$\therefore d{k}_b=qd+c$

即 $d(k_b-q)=c$

$\because k_b,q\in \mathbb{Z}$

$\therefore (k_b-q)\in \mathbb{Z}$

故 $d\mid c$

---

5.2 记 $c=d\ast k_c(k_c\in \mathbb{Z})$

$\therefore b=qd+q{k}_c$

即 $d(k_c+q)=b$

$\because k_c,q\in \mathbb{Z}$

$\therefore (k_c+q)\in \mathbb{Z}$

故 $d\mid b$

---

0x02 mod

概念： 对于$a,b\in \mathbb{Z},b\ne 0$，求 $a$ 除以 $b$ 的余数，称为 $a$ 模 $b$，记为 $a\mathrm{m}\mathrm{o}\mathrm{d}b$。

---

性质： 暂且研究 $a>0,b\ge 0$

0. 杂论：$(a+kb)\mathrm{m}\mathrm{o}\mathrm{d}b=a\mathrm{m}\mathrm{o}\mathrm{d}b$

1. 分配率：模运算对加、减、乘具有分配率

1.1 $(a+b)\mathrm{m}\mathrm{o}\mathrm{d}c=(a\mathrm{m}\mathrm{o}\mathrm{d}c+b\mathrm{m}\mathrm{o}\mathrm{d}c)\mathrm{m}\mathrm{o}\mathrm{d}c$

1.2 $(a-b)\mathrm{m}\mathrm{o}\mathrm{d}c=(a\mathrm{m}\mathrm{o}\mathrm{d}c-b\mathrm{m}\mathrm{o}\mathrm{d}c)\mathrm{m}\mathrm{o}\mathrm{d}c$

1.3 $(a\times b)\mathrm{m}\mathrm{o}\mathrm{d}c=[(a\mathrm{m}\mathrm{o}\mathrm{d}c)\times (b\mathrm{m}\mathrm{o}\mathrm{d}c)]\mathrm{m}\mathrm{o}\mathrm{d}c$

1.4 $(a^b)\mathrm{m}\mathrm{o}\mathrm{d}c=(a\mathrm{m}\mathrm{o}\mathrm{d}c{)}^b\mathrm{m}\mathrm{o}\mathrm{d}c$

2. 放缩性:

2.1 如果 $a\mathrm{m}\mathrm{o}\mathrm{d}b=c,d\ne 0$，则有 $(a\times d)\mathrm{m}\mathrm{o}\mathrm{d}(b\times d)=c\times d$

2.2 如果 $a\mathrm{m}\mathrm{o}\mathrm{d}b=c,d\ne 0$，则有 $\frac{a}{d}\mathrm{m}\mathrm{o}\mathrm{d}\frac{b}{d}=\frac{c}{d}$

---

证明：

0.1 $a<b$

记 $x=a+kb$

根据 $\mathrm{m}\mathrm{o}\mathrm{d}$ 的定义，$x\mathrm{m}\mathrm{o}\mathrm{d}b=a$

所以 $(a+kb)\mathrm{m}\mathrm{o}\mathrm{d}b=a$

---

0.2 $a⩾b$

$\therefore (a+kb)\mathrm{m}\mathrm{o}\mathrm{d}b=[(a-\lfloor \frac{a}{b}\rfloor \times b)+(k+\lfloor \frac{a}{b}\rfloor )b]\mathrm{m}\mathrm{o}\mathrm{d}b$

由定义得：$a\mathrm{m}\mathrm{o}\mathrm{d}b=a-\lfloor \frac{a}{b}\rfloor \times b$

$\therefore [(a-\lfloor \frac{a}{b}\rfloor \times b)+(k+\lfloor \frac{a}{b}\rfloor )b]\mathrm{m}\mathrm{o}\mathrm{d}b=[a\mathrm{m}\mathrm{o}\mathrm{d}b+(k+\lfloor \frac{a}{b}\rfloor )b]\mathrm{m}\mathrm{o}\mathrm{d}b$

$\because a\mathrm{m}\mathrm{o}\mathrm{d}b<b$

然后用 0.1 解决即可。

---

1.1 记 $a=c\ast q_a+r_a,b=c\ast q_b+r_b(q_a,q_b,r_a,r_b\in \mathbb{Z},r_a,rb<c)$

$\therefore (a+b)\mathrm{m}\mathrm{o}\mathrm{d}c=(c\ast q_a+r_a+c\ast q_b+r_b)\mathrm{m}\mathrm{o}\mathrm{d}c$

即 $(a+b)\mathrm{m}\mathrm{o}\mathrm{d}c=[r_a+r_b+(q_a+q_b)c]\mathrm{m}\mathrm{o}\mathrm{d}c$

由 0 得：$(a+b)\mathrm{m}\mathrm{o}\mathrm{d}c=(r_a+r_b)\mathrm{m}\mathrm{o}\mathrm{d}c)$

$\because r_a=a\mathrm{m}\mathrm{o}\mathrm{d}c,r_b=b\mathrm{m}\mathrm{o}\mathrm{d}c$

$\therefore (a+b)\mathrm{m}\mathrm{o}\mathrm{d}c=(a\mathrm{m}\mathrm{o}\mathrm{d}c+b\mathrm{m}\mathrm{o}\mathrm{d}c)\mathrm{m}\mathrm{o}\mathrm{d}c$

---

1.2 记 $a=c\ast q_a+r_a,b=c\ast q_b+r_b(q_a,q_b,r_a,r_b\in \mathbb{Z},r_a,rb<c)$

$\therefore (a-b)\mathrm{m}\mathrm{o}\mathrm{d}c=(c\ast q_a+r_a-c\ast q_b-r_b)\mathrm{m}\mathrm{o}\mathrm{d}c$

即 $(a-b)\mathrm{m}\mathrm{o}\mathrm{d}c=[r_a-r_b+(q_a-q_b)c]\mathrm{m}\mathrm{o}\mathrm{d}c$

由 0 得：$(a-b)\mathrm{m}\mathrm{o}\mathrm{d}c=(r_a-r_b)\mathrm{m}\mathrm{o}\mathrm{d}c)$

$\because r_a=a\mathrm{m}\mathrm{o}\mathrm{d}c,r_b=b\mathrm{m}\mathrm{o}\mathrm{d}c$

$\therefore (a-b)\mathrm{m}\mathrm{o}\mathrm{d}c=(a\mathrm{m}\mathrm{o}\mathrm{d}c-b\mathrm{m}\mathrm{o}\mathrm{d}c)\mathrm{m}\mathrm{o}\mathrm{d}c$

---

1.3 记 $a=c\ast q_a+r_a,b=c\ast q_b+r_b(q_a,q_b,r_a,r_b\in \mathbb{Z},r_a,rb<c)$

$\therefore (a\ast b)\mathrm{m}\mathrm{o}\mathrm{d}c=[(c\ast q_a+r_a)\ast (c\ast q_b+r_b)]\mathrm{m}\mathrm{o}\mathrm{d}c$

$\therefore (a\ast b)\mathrm{m}\mathrm{o}\mathrm{d}c=(q_a{q}_b{c}^2+q_a{r}_{b}c+q_b{r}_{a}c+r_a{r}_b)\mathrm{m}\mathrm{o}\mathrm{d}c$

即 $ (a * b) \bmod c = [r_a * r_b + c(q_aq_bc + q_ar_b + q_br_a)] \bmod c$

由 0 得：$(a\ast b)\mathrm{m}\mathrm{o}\mathrm{d}c=(r_a\ast r_b)\mathrm{m}\mathrm{o}\mathrm{d}c)$

$\because r_a=a\mathrm{m}\mathrm{o}\mathrm{d}c,r_b=b\mathrm{m}\mathrm{o}\mathrm{d}c$

$\therefore (a\times b)\mathrm{m}\mathrm{o}\mathrm{d}c=[(a\mathrm{m}\mathrm{o}\mathrm{d}c)\times (b\mathrm{m}\mathrm{o}\mathrm{d}c)]\mathrm{m}\mathrm{o}\mathrm{d}c$

---

1.4

由 1.3 得：

$(a^b)\mathrm{m}\mathrm{o}\mathrm{d}c=(a\times a^{b-1})\mathrm{m}\mathrm{o}\mathrm{d}c=[(a\mathrm{m}\mathrm{o}\mathrm{d}c)\times (a^{b-1}\mathrm{m}\mathrm{o}\mathrm{d}c)]\mathrm{m}\mathrm{o}\mathrm{d}c$

$(a^b)\mathrm{m}\mathrm{o}\mathrm{d}c=[(a\mathrm{m}\mathrm{o}\mathrm{d}c)\times (a\mathrm{m}\mathrm{o}\mathrm{d}c)\times (a^{b-2}\mathrm{m}\mathrm{o}\mathrm{d}c)]\mathrm{m}\mathrm{o}\mathrm{d}c$

$...$

$(a^b)\mathrm{m}\mathrm{o}\mathrm{d}c=[(a\mathrm{m}\mathrm{o}\mathrm{d}c)\times (a\mathrm{m}\mathrm{o}\mathrm{d}c)...\times (a\mathrm{m}\mathrm{o}\mathrm{d}c)]\mathrm{m}\mathrm{o}\mathrm{d}c$

---

2.1 记 $a=b\times q_a+c$

$∴ (a \times d) \bmod (b \times d) = (cd + bdq_a) \bmod bd $

$\because a\mathrm{m}\mathrm{o}\mathrm{d}b=c$

$\therefore c<b$

又 $\because d>0$

$\therefore cd<bd$

$\therefore$ 由 0.1 得：$(a\times d)\mathrm{m}\mathrm{o}\mathrm{d}(b\times d)=(cd+bd{q}_a)\mathrm{m}\mathrm{o}\mathrm{d}bd=cd$

---

2.1 记 $a=b\times q_a+c$

$∴ \frac a d \bmod \frac b d = (\frac c d + \frac {bq_a} d) \bmod \frac b d $

$\because a\mathrm{m}\mathrm{o}\mathrm{d}b=c$

$\therefore c<b$

又 $\because d>0$

$\therefore \frac{c}{d}<\frac{b}{d}$

$\therefore$ 由 0.1 得：$\frac{a}{d}\mathrm{m}\mathrm{o}\mathrm{d}\frac{b}{d}=(\frac{c}{d}+\frac{b{q}_a}{d})\mathrm{m}\mathrm{o}\mathrm{d}\frac{b}{d}=\frac{c}{d}$

---

0x03 同余

概念： 设 $m$ 为给定正整数，若满足 $m\mid (a-b),a,b\in \mathbb{Z}$，则称 $a$ 与 $b$ 对 $m$ 同余。记作 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$

---

性质：

0. 一些基本性质：

0.1 反身性：$a\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}m)$

0.2 对称性：$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $b\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}m)$

0.3 传递性：$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $b\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $a\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}m)$

1. 同加性：若 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $a+c\equiv b+c(\mathrm{m}\mathrm{o}\mathrm{d}m)$

2. 同减性：若 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $a-c\equiv b-c(\mathrm{m}\mathrm{o}\mathrm{d}m)$

3. 同乘性：若 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $a\times c\equiv b\times c(\mathrm{m}\mathrm{o}\mathrm{d}m)$

4. 同除性：若 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m),c\mid a,c\mid b,(c,m)=1$，则 $\frac{a}{c}\equiv \frac{b}{c}(\mathrm{m}\mathrm{o}\mathrm{d}m)$

5. 同幂性：若 $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$，则 $a^c\equiv b^c(\mathrm{m}\mathrm{o}\mathrm{d}m)$

6. 若 $a\mathrm{m}\mathrm{o}\mathrm{d}p=x,a\mathrm{m}\mathrm{o}\mathrm{d}q=x,(p,q)=1$，则 $a\mathrm{m}\mathrm{o}\mathrm{d}(p\times q)=x$

---

1. 由题：$m\mid (a-b)$

$\therefore m\mid [(a+c)-(b+c)]$

$\therefore a+c\equiv b+c(\mathrm{m}\mathrm{o}\mathrm{d}m)$

---

2. 由题：$m\mid (a-b)$

$\therefore m\mid [(a-c)-(b-c)]$

$\therefore a-c\equiv b-c(\mathrm{m}\mathrm{o}\mathrm{d}m)$

---

3. 由题：$m\mid (a-b)$

$\therefore m\mid [ac-bc]$

$\therefore a\times c\equiv b\times c(\mathrm{m}\mathrm{o}\mathrm{d}m)$

---

4. 记 $a=k_{a}c,b=k_{b}c$

$\therefore p\mid (k_a-k_b)c$

$\because (c,p)=1$

$\therefore p\mid (k_a-k_b)$

$\therefore pc\mid (k_{a}c-k_{b}c)$

即 $pc\mid (a-b)$

$\therefore p\mid \frac{a-b}{c}$

即 $p\mid (\frac{a}{c}-\frac{b}{c})$

$\therefore \frac{a}{c}\equiv \frac{b}{c}(\mathrm{m}\mathrm{o}\mathrm{d}m)$

---

5. 由题：$m\mid (a-b)$

$\therefore a^c-b^c=(a-b)(a^{c-1}+a^{c-2}b+...+a{b}^{c-2}+b^{c-1})$

$\because a,b\in \mathbb{Z}$

$\therefore (a^{c-1}+a^{c-2}b+...+a{b}^{c-2}+b^{c-1})\in \mathbb{Z}$

$\therefore (a-b)\mid (a^c-b^c)$

$\therefore m\mid (a^c-b^c)$

即 $a^c\equiv b^c(\mathrm{m}\mathrm{o}\mathrm{d}m)$

---

6. $\because a\mathrm{m}\mathrm{o}\mathrm{d}p=x,a\mathrm{m}\mathrm{o}\mathrm{d}q=x$

$\therefore p\mid (a-x),q\mid (a-x)$

$\therefore a-x=p{k}_p,a-x=q{k}_q(k_p,k_q\in \mathbb{Z})$

即 $p{k}_p=q{k}_q$

$\because (p,q)=1$

$\therefore k_p=kq(k\in \mathbb{Z})$

$\therefore a-x=pqk$

故 $pq\mid a-x$

即 $a\mathrm{m}\mathrm{o}\mathrm{d}(p\times q)=x$