1整数的可除性——北邮《信息安全数学基础》

一、整数的概念

1、整除定义

设 a, b 是任意两个整数，其中 b $\neq$ 0 。如果存在一个整数 q，使 a = bq 成立，称 b 整除 a，或者 a 被 b 整除，记作 b|a，并把 b 叫作 a 的因数，a 叫作 b 的倍数。这时，q 也叫 a 的因数，将 q 写作 a/b 或 $\frac{a}{b}$ 。否则，记作 a $\nmid$ b。

注：

（1）当 b 遍历 a 的所有因数时，-b 和 a/b 也遍历 a 的所有因数。

（2）0是任何非零整数的倍数。

（3）1是任何整数的因数

（4）任何非零整数 a 是其自身的倍数，也是其自身的因数。

（5）设 a，b 为整数，若b|a，则b|(-a)，(-b)|a，(-b)|(-a) 。

证：设 b|a，则存在整数 q 使得 a = bq。因而 (-a) = b(-q)，a = (-b)(-q)，(-a) = (-b)q；
因为 -q，q 都是整数，所以根据整除的定义，我们有 b|(-a)， (-b)|a，(-b)|(-a)。

2、定理

（1）传递性

设 a，b，c $\neq$ 0 是三个整数，若 c|b，b|a，则 c|a。

（2）在加法与减法运算中，整除的性质是保持的

设 a，b，c $\neq$ 0 是三个整数，若 c|a，c|b，则 c|a $\pm$ b。

（3）在整数的线性组合中，整除的性质是保持的

设 a，b，c $\neq$ 0 是三个整数，若 c|a，c|b，则对任意整数 s，t，有 c|sa $\pm$ tb。

（4）多个整数的线性，整除的性质是保持的

若整数 a1,..., an 都是整数 c $\neq$ 0 的倍数，则对任意 n 个整数 s1,..., sn，整数 s1*a1 +...+ sn*an 是 c 的倍数。

（5）设 a，b 都是非零整数，若 a|b，b|a，则a = $\pm$ b。

3、素数定义

设整数 n $\neq$ 0， $\pm$ 1，如果除了显然因数 $\pm$ 1， $\pm$ n 外，n没有其他因数，那么 n 叫做素数/质数/不可约数。否则，n 叫做合数。

4、定理

（6）n 是一个正合数，p 是 n 的一个大于1 的最小正因数。则 p 一定是素数且 p $\leqslant \sqrt{n}$ 。

证明：（反证法）

                若 p 不是素数则 qIp，
                而 p|n 则由定理（1）知，q|n 这与 p 为最小正因数矛盾，
                所以 p 是素数。
                因为 n 是合数，则 n = p $n_{1}$ 其中1 < P ≤ $n_{1}$ < n
                因此， $p^{2}\leqslant n$ , 故 $p\leqslant \sqrt{n}$ 。

素数是乘法的最小单元，并且整数可以表示成素数的乘积。

（7）设 n 是一个正整数，如果对所有的素数 p $\leqslant \sqrt{n}$ ，都有 p $\nmid$ n，则 n 一定是素数。

5、平凡除法（Eratosthenes筛法）

例题1. 求出所有不超过 N = 100 的素数。

解：因为 N = 100，所以不大于 $\sqrt{100}$ = 10 的所有素数为 2，3，5，7，所以依次删去 2，3，5，7 的倍数，余下的即为所有不超过 N = 100 的素数。列表解答如下：

6、定理

（8）素数有无穷多个。

证明：（反证法）

假设有有限个素数，他们为 $p_{1},p_{2},...,p_{k}$ 。

考虑 $n= p_{1}*p_{2}*...*p_{n}+1$ ，所以 n一定是合数（因为素数有限，n 又不是 $p_{1},p_{2},...,p_{k}$ 中的任何一个）。

根据定理（6），n 的大于 1 的最小正因数 p 是素数。

因此，p 是 $p_{1},p_{2},...,p_{k}$ 中的一个。

又由定理（3），我们有 $p\mid n-p_{1}*p_{2}*...*p_{n}=1$ ，这显然不可能。

所以素数有无穷个。

（9）欧几里得除法

设 a，b > 0 是两个整数，则存在唯一的整数 q，r 使得 a = bq + r，0 ≤ r < b。

（证明包括存在性和唯一性两个部分，具体可以参考教材P6，在此不进行过多阐述）

注：① q 叫做不完全商

② r 叫做余数

③ $b\mid a\Leftrightarrow r=0$

7、素数的平凡判别法

例题2. 证明 137 是素数。

证：小于等于 $\sqrt{137}<12$ 的所有素数为 2，3，5，7，11

由于 $2\nmid 137,3\nmid 137,5\nmid 137,7\nmid 137,11\nmid 137$ ，

所以 137 是素数。

（！！！素数的判断，一定要掌握，考试应该是必考的！！！）

8、定理

（10）设 a，b > 0 是两个整数，则对任意整数 c，存在唯一的整数 q，r 使得 a = bq + r，c ≤ r < b + c。

例题3.

	b = 7	b = 8
最小非负余数	0，1，2，3，4，5，6	0，1，2，3，4，5，6，7
最小正余数	1，2，3，4，5，6，7	1，2，3，4，5，6，7，8
最大非正余数	0，-1，-2，-3，-4，-5，-6	0，-1，-2，-3，-4，-5，-6，-7
最大负余数	-1，-2，-3，-4，-5，-6，-7	-1，-2，-3，-4，-5，-6，-7，-8
绝对值最小余数	-3，-2，-1，0，1，2，3	-3，-2，-1，0，1，2，3，4或 -4，-3，-2，-1，0，1，2，3

二、最大公因数与广义欧几里得除法

1、最大公因数定义

设 $a_{1}...a_{n}$ 是 n(n ≥ 2) 个整数，若整数 d 是它们每一个的因数，那么 d 就叫 $a_{1}...a_{n}$ 的一个公因数。那么，最大的 d 叫做最大公因数，记作 $(a_{1},...,a_{n})$ 。

$(a_{1},...,a_{n})=1 \Leftrightarrow$ $a_{1}...a_{n}$ 互素/互质。

注：

（1） $(b,a)=(a,b)$

（2） $b\mid a\Rightarrow (a,b)=b$

（3）p 是素数，a 是整数， $p\nmid a\Rightarrow (a,p)=1$

证明：设( p, a ) =d 则 d|p，d|a。由于 p 是素数，那么 d = 1 或 d = p。

当 d = p 时， p|a 与 $p\nmid a$ 相矛盾，那么 d = 1 , 即( p, a ) = 1，p 与 a 与互素。

2、定理

（1） $(a,b)=(a,-b)=(-a,b)=(\left | a \right |, \left | b\right |)$

（2）设 b 是任一正整数，则 $(0,b)=b$

（3）设 a，b，c 是三个不全为 0 的整数，如果 a = bq + c，则 $(a,b)=(b,c)$

例题1.

因为1859 = 1*1573 + 286，则(1859, 1573) = (1573, 286）
因为1573 = 5*286 + 143，则(1573, 286) = (286, 143) = 143

3、求（a，b）

例题2. a = -169，b = 121，求（a，b）

解：(-169, 121) = (169, 121) = (121, 48) = (48, 25) = (25, 23) = (23, 2) = (2, 1) = 1

（！！!求最大公因数，一定要掌握，考试必考，接下来的贝祖等式也要用到！！！)

4、贝祖等式

设 a，b 是任意两个正整数，则存在整数 s，t 使得 s*a + t*b = (a , b)

例题3. 设 a = 169，b = 121，求 s，t 使得 s*a + t*b = (a , b)。

解：(a , b) = (169 , 121) = (121 , 48) = (48 , 25) = (25 , 23) = (23 , 2) = (2 , 1) = 1

那么有，1 = 2 - 1 × 1
= 2 - 1 × (23 - 11 × 2)
= -1 × 23 + 12 × 2
= -1 × 23 + 12 × (25 - 1 × 23)
= 12 × 25 - 13 × 23
= 12 × 25 - 13 × (48 - 1 × 25)
= 25 × 25 - 13 × 48
= 25 × (121 - 2 × 48) - 13 × 48
= 25 ×121 - 63 × 4
= 25 ×121 - 63 × (169 - 1 × 121)
= 88 ×121 - 63 × 169
那么 s = -63，t = 88。

（！！！这个一定要会，后面求逆元也要用到！！！）

5、定理

（8）a，b 互素 $\Leftrightarrow$ $\exists s,t \ \ sa+tb=1$

（9） $(a,b)=d\Leftrightarrow 1)d\mid a ,d\mid b\ \ \ 2)e\mid a, e\mid b\Rightarrow e\mid d$

（10）① $(am,bm)=(a,b)m$

② $d\mid a,\ d\mid b\Rightarrow (\frac{a}{d},\frac{b}{d})=\frac{(a,b)}{\left | d \right |}$ 特别地 $(\frac{a}{(a,b)},\frac{b}{(a,b)})=1$

（11） $(a,c)=1\Rightarrow (ab,c)=(b,c)$

（12） $(a_{i},c)=1\Rightarrow (a_{1}a_{2}...a_{n},c)=1$

6、多个整数的最大公因数及计算

例题4. 计算 (120 , 150 , 210 , 35)

解：(120 , 150) = (120 , 30) = 30
(30 , 210 ) = 30
(30, 35 ) = (30 , 5) = 5
所以 (120 , 150 , 210 , 35) = 5

（！！！多个数的最大公因数的计算，一定要掌握，期末会考！！！）

三、整除的进一步性质及最小公倍数

1、定理

（1） $c\mid ab, \ (a,c)=1\Rightarrow c\mid b$

（2）p 是素数，若 p|ab 则 p|a 或 p|b。

（3）p 是素数， $p\mid a _{1}a _{2}...a _{n}\Rightarrow p\mid a _{k},1\leqslant k\leqslant n$

2、最小公倍数定义

设 $a_{1},...,a_{n}$ 是 n 个整数，若 D 是这 n 个数的倍数，则 D 叫做这 n 个数的公倍数。那么最小的 D 叫做最小公倍数，记作 $\left [ a_{1},...,a_{n} \right ]$ 。

3、定理

（4） $a\mid b,\ b\mid d\Rightarrow \left [ a,b \right ]\mid d$

（5） $\left [ a,b \right ]= \frac{ab}{(a,b)}$

（6） $\left [ a_{1} ,a_{2}\right ]=D_{2},\left [ D_{2} ,a_{3}\right ]=D_{3},...,\left [ D_{n-1} ,a_{n}\right ]=D_{n} \\ \Rightarrow \left [ a_{1},a_{2} ,...,a_{n}\right ]=D_{n}$