初等数论整除理论.ppt

初等数论整除理论
第1页，共19页，2022年，5月20日，13点35分，星期一
1、素数
(1)、素因子
(2)、素数分布
(3)、素数搜寻
ichael 数 ）。
米勒-拉宾法、……
第8页，共19页，2022年，5月20日，13点35分，星期一
GCD和LCM
定义 整数a1, a2, , ak的公共约数称为a1, a2, , ak 的公约数。
不全为零的整数a1, a2, , ak 的公约数中最大一个叫做a1, a2, , ak 的最大公约数（或最大公因数），记为(a1, a2, , ak)。
由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。
如果(a1, a2, , ak) = 1，则称a1, a2, , ak 是互素的。
如果(ai, aj) = 1，1  i, j  k，i  j，则称a1, a2, , ak 是两两互素的。
a1, a2, , ak 两两互素可以推出(a1, a2, , ak) = 1，反之则不然。
定义 整数a1, a2, , ak 的公共倍数称为a1, a2, , ak 的公倍数。
整数a1, a2, , ak 的正公倍数中最小的一个叫做a1, a2, , ak 的最小公倍数，记为[a1, a2, , ak]。
第9页，共19页，2022年，5月20日，13点35分，星期一
GCD和LCM
n的标准分解式：
n的正因数：
n的正倍数 ：
第10页，共19页，2022年，5月20日，13点35分，星期一
带余数除法 设a与b是两个整数，b  0，则存在唯一的两个整数q和r，使得
a = bq  r，0  r < |b|。
定理 若a = bq  r，则(a, b) = (b, r)。实际上给出一个求最大公因子的方法。
推论 设a1, a2, , an为不全为零的整数，以y0表示集合
A = { y：y = a1x1    anxn，xiZ，1  i  n }
中的最小正数，则
对于任何yA， y0y；
特别地， y0ai，1  i  n。
证明：
设y0 = a1x1    anxn，
对任意的y = a1x1    anxnA，存在q, r0Z，使得
y = qy0  r0，0  r0 < y0 。
因此
r0 = y  qy0 = a1(x1  qx1)    an(xn  qxn)A。
如果r0  0，那么，因为0 < r0 < y0，所以r0是A中比y0还小的正数，
这与y0的定义矛盾。所以r0 = 0，即y0y。
显然aiA（1  i  n），所以y0整除每个ai（1  i  n）。
GCD和LCM
第11页，共19页，2022年，5月20日，13点35分，星期一
定理 设a1, a2, , ak Z，记 A = { y：y = ，xiZ，  i  k }。
如果y0是集合A中最小的正数，则y0 = (a1, a2, , ak)。
推论 设d是a1, a2, , ak的一个公约数，则d(a1, a2, , ak)。
最大公约数不但是公约数中的最大的，而且是所有公约数的倍数。
定理 记d = (a1, a2, , ak)，则 (a1/d, a2/d, , ak/d)=1。
特别地, (a/(a,b), b/(a,b)=1 。
定理 (a1, a2, , ak) = 1的充要条件是存在整数x1, x2, , xk，使得
a1x1 