「Note」简单数论

整除

定义

设$a,b \in \mathbb{Z}$,且$b \neq 0$.如果存在$q\in\mathbb{Z}$，使得$a=bq$,则$b$整除a，记作$b\mid a$，此时$b$为$a$的因数，$a$叫做$b$的倍数.

---

性质

1

$如果a \mid b 且 b\mid c$,那么$c\mid a$

证明 ： $设an=b, bm=c (n, m \in \mathbb{Z}).$
$\therefore c/a = nm.$
$\therefore c\mid a.$

2

$如果a\mid b且a\mid c，有a\mid (bx+cy)$

证明：
$设 as = b, at = c$
$s,t\in\mathbb{Z^+}$
$\therefore ast = c$
$\therefore a\mid c$

3

$如果c\mid a, c\mid b，那么对于任意m, n\in\mathbb{Z},有c\mid ma+mb$. 证明 $如果m\neq 0,则a\mid b \Leftrightarrow mb\mid ma$ $\because a\mid b$ $\therefore 不妨设an=b$ $\therefore anm = bm$ $\therefore n*am = bm$ $\therefore mb\mid ma$

4

$如果ax+by=1，a\mid n, a\mid n. \Rightarrow ab\mid n$. 证明： $设as=n=1, bt=n, s,t\in\mathbb{Z}且s, t \neq 0$. $\because ax+by=1$. $\therefore \frac{x}{b} + \frac{y}{a}$. $\because ab\mid n$ $\therefore \frac{n}{ab}\in\mathbb{Z}$ $\therefore n \times \frac{1}{ab}$ $=\frac{nx}{b}+\frac{ny}{a}$ $=tx+sy$

5

如果$b=d\times q + c,q\in\mathbb{Z}$
$d\mid c \Leftrightarrow d\mid b$

---

模运算

定义

对于整数$a,b (b \neq 0)$,求$a \div b$的余数.记作$a$ $mod$ $b$$(a\%b)$.

---

性质

1.分配率

$(a+b)\%c=(a\%c+b\%c)\%c$ $(a-b)\%c=(a\%c-b\%c)\%c$ $(a\times b)\%c=(a\%c\times b\%c)\%c$ $(a^b)\%c=(a\%b)^b\%c$

统一证明:
设$ka+m_a=c, kb+m_b=c$
带入整理可得:
$\Rightarrow(a+b)\%c=(m_a+m_b)%c$
$\Rightarrow(a-b)\%c=(m_a-m_b)%c$
$\Rightarrow(a*b)\%c=(m_a*m_b)%c$
而幂运算可与看做多个乘法运算

---

2.缩放性

2.1

$如果a\%b=c,d\neq 0$ $\Rightarrow (ab)\%(bd)=cd$

证明:
设$a=bs+c$
$\Rightarrow ad=(bs+c)d$
$\Rightarrow ad=sbd+cd$
$\Rightarrow (ab)\%(bd)=cd$

---

2.2

$如果a\%b=c,d\mid a, d\mid b$ $\Rightarrow(a/d)\%(b/d)=(c/d).$

证明：
设$bs+c=a$.
$\frac{b}{d}\times s + \frac{c}{d}=\frac{a}{d}$

---

2.3

$\frac{a}{b}\%c=\frac{a\%(bc)}{b}$

证明：
两边同时乘$b$，可以得到：
$a\%(bc)=a\%(bc)$