第一章　整数的可除性

第一章主要涉及内容是整数的除法，包括整除，最大公因数，最小公倍数，解线性方程组，整数分解和素数定理。

第一节整除

1.1定义: $\forall a,b \in Z, b \neq 0 , 若 \exists q \in Z使得\ a = q \cdot b \ 则称b整除a,记作\ b|a$

这里实际上类似一个从属关系， $即a为b的倍数,b为a的因数$ 。

0为任何数的倍数
1为任何数的因数
任何非0整数a既为自身的因数，也是自身的倍数

1.2整除的性质

1 .传递性
$若\ a|b,\ b|c,\ 则\ a|c$
2 .线性变换稳定

$若a|b,a|c,则a|(b+c)$
$若a|b, k\in Z 则 a| kb$
$若a|b \ a|c,s,t\in Z,则a|(sb+tc)$
$\forall s_1,s_2,...,s_n \in Z, a|c_1 a|c_2 ... a|c_n, 则a|(\sum_{i=0}^n s_i c_i )$

由此可以看出，整除对于倍数的线性组合是稳定的(确保倍数至少为0或1)。

3 .
$若a|b, b|a \ 则 \ a=\pm b$

1.3欧几里得除法

$设a,b \in Z,b>0, 存在唯一的 q,r \in Z 使得, a= q\cdot b + r \ , 0 \leq r < b$
$r称作余数，q称作不完全商。$

存在性可以通过步长为b的数轴实现，可以证明a落在其中的一个区间中。
唯一性则可通过反证法，通过移项可知等式两侧的绝对值不可能相等，从而由矛盾得出唯一性。

1.4素数与平凡筛法

定义:若一个不为1的整数n的因数有且仅有自身和1,则称其为素数。否则称为合数。
(注:在国内潘承洞的书中，素数被扩展到了负数数域，此时则因数不为 $\pm 1,\pm n$ )

1.5素数筛法

基础定理1.
$设n为一个正合数,p为n的一个大于1的最小正因数,则p一定为素数，且p \leq \sqrt{n}$

意义，这个定理给出了合数最小因数的上界，且证明了整数的非1最小因数为素数，为快速素数表建立奠定基础。
这里就可以将素数看成整数的因子，所有整数都可以表示为素数的线性组合(加,乘)。
虽然哥德巴赫猜想没有证明，但不妨碍我们将素数的个数设置为无限制。
(哥德巴赫猜想:任何大于2的偶数都可以写做两个素数之和)

基础定理2.
$设n为正整数，若对所有素数p \leq \sqrt{n},都有p\nmid n,则n一定为素数$

由基础定理1,２可以得到两个简单素数判定方法，也可以得到素数表的获取方法------平凡筛法

$\forall n \in Z ,n \ge 2$

简单素数判定方法

1)遍历检验n不能被小于等于 $\sqrt{n}$ 的非1正整数整除，则为素数
2)利用素数表，遍历检验小于 $\sqrt{n}$ 的素数，若其不能整除n则为素数

素数表建立方法

1)对范围内的每个数进行素数判定
2)先判定出 $\sqrt{n}$ 范围内的素数，然后去除表内素数的所有倍数

练习

1.证明: $所有大于3的素数都可以被写成\forall q \in Z, q>0 , p=6q \pm 1的形式$
2.证明: $若m,n,p,q均为整数，且(m-n)|(mn+pq),则(m-p)|(mq+np)$
3.证明: $若a,b为两个不全为0的整数,则\lbrace sa+tb|s,t \in Z \rbrace = \lbrace (a,b) \cdot k | k \in Z \rbrace$
(a,b)指的是最大公因数，下一节会讲到

第一章 整数的可除性

第一节 整除

1.1定义: