# 整除性

任一给定整数 $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.$ 既然可以是 $ab$ 的倍数，那么一定可以是 $a,b$ 最小公倍数的倍数

$F.$ 当 $s= a,t=b$ 时，$sa+tb = a^2+b^2$，成立

解析

$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)=(q,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$ 是三个整数，$q\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$

# 解多元一次方程

有整数解的充要条件是

$$(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_{i=1}^s p_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]$

小数部分：{ $A_n$ }