# 整除性

任一给定整数 $a$ 和 正整数 $b >0$，存在唯一的一对整数 $q,r(0\leq r<b)$，使得 $a=qb+r$

任意给定整数 $a$ 和负整数 $b<0$，存在唯一的一对整数 $q,r(0\leq r<|b|)$，使得 $a=qb+r$

任意给定整数 $a,c$ 和整数 $b\neq 0$，存在唯一的一对整数 $q,r(c\leq r<|b|+c)$，使得 $a=qb+r$

证明

对于整数 $a-c$，存在一对整数 $q,r'(0\leq r'<|b|)$

使得

$$a-c=qb+r'\\ a=qb+r'+c$$

令

$$r=r'+c$$

有

$$c\leq r<|b|+c$$

若 $a|b,a|c$，则对于任意整数 $s$ 和 $t$，有 $a|sb+tc$

习题：

解析

$A.$ 当 $t=0$ 时，$a|sa$

$B.$ 集合 $sa+tb$ 表示的是$(a,b)$ 的倍数的集合，$ma+nb$ 是 $(a,b)$ 的倍数，所以属于该集合

$C.$ 由欧几里得辗转相除法得，成立

$D.$ 因为 $ab$ 是 $(a,b)$ 的倍数，所以属于该集合

$E.$ $[a,b]$ 是 $(a,b)$ 的倍数，属于该集合

$F.$ 假设 $(a,b)=t$，那么$a^2+b^2=(k_1t)^2+(k_2t)^2=t(k_1^2t+k_2^2t)$，显然 $a^2+b^2$ 是 $(a,b)$ 的倍数，属于该集合

解析

$A.$

$$mq+np=mn+pq+mq-qp+np-mn\\ =(mn+pq)+q(m-p)-n(m-p)$$

$\text{C}.$

$$m^2q+n^2p+pqn+mnp=(mq+np)(m+n)$$

$D.$

$$mnp+mpq+np^2+qm^2=(mq+np)(m+p)$$

# 最大公因数与最小公倍数

设 $a,b$ 是两个不全为 0 的整数，且 $a=qb+r,q,r$ 为整数，则 $(a,b)=(b,r)$

设 $a,b$ 是两个不全为 0 的整数，$q$ 为整数，则 $(a,b)=(a\pm bq,b)=(a,b\pm aq)$

• 连续两个整数一定互素，连续的两个奇数一定互素

# 欧几里得辗转相除法

1. $$(a,b)=r_n$$

2. 存在整数 $s,t$，使得

   $$r_n=sa+tb$$

3. 任意整数 $c$，若满足 $c|a$ 与 $c|b$，则 $c|r_n$

不断带入法求 $s,t$

习题：

# 最大公因数性质

设 $a,b$ 是两个不全为 0 的整数，则

1. 对于任何正整数$k$，$(ka,kb)=k(a,b)$

2. $$(\frac{a}{(a,b)},\frac{b}{(a,b)})=1$$

设 $a,b,c$ 是三个整数，$a\neq 0,c\neq 0$，若 $(a,b)=1$，则 $(a,bc)=(a,c)$

设 $a,b,c$ 是三个整数，$a\neq 0$，若 $(a,b)=1,a|bc$，则 $a|c$

# 解多元一次方程

$$ax+b=c$$

有整数解的充要条件是

$$(a,b)|c$$

所有整数解表示成

$$\left\{\begin{matrix} x=x_0-\frac{b}{(a,b)}t & t\in \Z\\ y=y_0+\frac{a}{(a,b)}t &t\in \Z \end{matrix}\right.$$

特解的求法：利用最小公约数 + 不断代入法求 $s,t$

当有三个及三个以上的未知数的时候，可以先选择两个互素的系数，因为这样两者组合可以遍历所有整数

习题：

# 最小公倍数性质

设$a,b$ 是两个正整数，且 $(a,b)=1$，则

1. 若 $a|c,b|c$，则 $ab|c$
2. $[a,b]=ab$

设 $a,b$ 是两个正整数，则

1. 对于任何正整数 $k$，$[ka,kb]=k[a,b]$

2. $$[a,b]=\frac{ab}{(a,b)}$$

3. 若 $a|c,b|c$，则$[a,b]|c$

证明

$(2)$

$$a=p_1^{\alpha_1}\cdot p_2^{\alpha_2}...p_s^{\alpha_s}\\ b=p_1^{\beta_1}\cdot p_2^{\beta_2}...p_s^{\beta_s}\\ [a,b]=p_1\cdot p_2...p_s^{max(\alpha_s,\beta_s)}\\ (a,b)=p_1\cdot p_2...p_s^{min(\alpha_s,\beta_s)}\\ a\cdot b=\prod_{i=1}^s p_i^{a_i+b_i}\\ [a,b](a,b)=\prod_{i=1}^sp_i^{min+max}$$

最小公倍数不仅是最小的正公倍数，还是所有公倍数的公因数

# 素数与算数基本定理

对于任意的正整数 $n$，必有 $n$ 个连续正整数都是合数

合数 $m$ 的最小的不等于 1 的正因子 $p$ 一定是素数，且 $p\leq \sqrt m$

• 设整数 $m>1$，如果所有不大于 $\sqrt m$ 的素数都不是 $m$ 的因子，那么 $m$ 是素数

# 素数定理

$$\lim_{x\to \infty}\pi(x)\frac{lnx}{x}=1$$

# 伯特兰 - 切比雪夫定理

设整数 $n>3$，至少存在一个素数 $p$ 满足 $n<p<2n-2$

# 因数个数 & 因数之和

设 $n$ 是大于 1 的正整数， ${n=\prod\limits_{i=1}^s p_i^{\alpha_i}}$

因数个数：

$$(\alpha_1+1)\cdot (\alpha_2+1)\cdot....\cdot(\alpha_s+1)$$

因数之和：

$$(1+p_1+p_1^2+...+p_1^{\alpha_1})\cdot(1+p_{2}+...+p_2^{\alpha_2})...(1+p_s+...+p_s^{\alpha_s})$$

# 高斯函数

向下取整

整数部分： $[x]$

小数部分： ${\left\{A_n\right\}}$

定理：设 $p$ 是一个素数，则 $n!$ 中包含 $p$ 的幂次为 $\sum\limits_{i\geq 1}[\frac{n}{p^i}]$

证明

在 $1\sim n$ 中

$p$ 的倍数共有 $[\frac{n}{p}]$

$p^2$ 的倍数共有 $[\frac{n}{p^2}]$

$...$

$p^i$ 的倍数共有 $[\frac{n}{p^i}]$

将所有这些贡献相加，得到 $n!$ 中 $p$ 的总幂次为：

$$\sum\limits_{i\geq 1}[\frac{n}{p^i}]$$

试证明 $( \frac{100}{50} )$ 的十进制末位数不为 0。

解析

证明：

$$( \frac{100}{50} ) = \frac{100 \times 99 \times \cdots \times 51}{50!} = \frac{100!}{50! \times 50!}$$

$100!$ 中含有 $5$ 的幂次为

$$\sum_{i=1}^{50} \left[ \frac{100}{5^i} \right] = \left[ \frac{100}{5} \right] + \left[ \frac{100}{25} \right] = 20 + 4 = 24$$

50! 中含有 5 的幂次为

$$\sum_{i=1}^{50} \left[ \frac{50}{5^i} \right] = \left[ \frac{50}{5} \right] + \left[ \frac{50}{25} \right] = 10 + 2 = 12$$

所以

$$\frac{100!}{50! \times 50!}$$

中含有 5 的幂次为

$$24 - (12 + 12) = 0$$

因此 5 不是 $( \frac{100}{50} )$ 的因子，其十进制末位数不为 0。