《数论算法》教案 1章(整数的可除性).doc

《数论算法》第一章整数的可除性

/NUMPAGES39
整数的可除性

内容整除性
公因数、最大公因数
辗转相除法（欧几里得除法）
算术基本定理要点培养对数论问题的认识及证明问题的思路
《数论》从研究整数开始，叫“整数论”。经进一步发展，叫做“数论”。
确切地说，数论是研究整数性质的学科。
自然数（正整数）负整数0（统称整数）。
算术运算：加、减、乘、除（四则运算）。
加法、减法和乘法在整数范围内可以毫无阻碍地进行。但整数之间的除法在整数范围内并不一定能够无阻碍地进行。
《数论算法》主要从应用角度出发，研究数论问题中实用的方法和技术。
整除的概念欧几里得除法
整除概念
【定义1.1.1】设a,b∈Z（整数集合），b≠0，如果存在q∈Z，使得a＝bq，则称b整除a或a可被b整除，记作b│a，且称a是b的倍数，b是a的因数（也可称为除数、约数、因子）。否则，称b不能整除a或a不能被b整除，记作ba。
◆说明：
q也是a的因数，并将q写为a/b或；
当b遍历整数a的所有因数时，－b也遍历整数a的所有因数；
当b遍历整数a的所有因数时，a/b也遍历整数a的所有因数。
例：设a＝6，则有
当b＝3时，q＝2＝6/3
当b＝1,2,3,6,－1,－2,－3,－6时有－b＝－1,－2,－3,－6,1,2,3,6
当b＝1,2,3,6,－1,－2,－3,－6时有a/b＝6,3,2,1,－6,－3,－2,－1

【特例】：
0是任何非零整数的倍数；
±1是任何整数的因数；
任何非零整数a是其自身的倍数，也是其自身的因数。
性质
设，则│。
（证）a＝bq－a＝q(－b)
其余类推。

【例1.1.1】30的所有因数：±1，±2，±3，±5，±6，±15，±30

传递性：，
（证）且b＝c，a＝b
a＝cc│a。

，，则
，，则对任意整数s、t，有
推广：

若，，则a＝±b
（证）a＝b
b＝a
a＝
＝1
＝±1
（c≠0）
若，则≤
例
【例1.1.2】证明：若且，则。
（证）
已知。
。即m＝7q
n＝3(7q)＝21q。

【例1.1.3】设。若，则。
（证）
又＝(an＋n)－an＝n，即
（由a＝2t－1知2t＝a＋1，从而2tn＝an＋n）

【例1.1.4】设a,b是两个给定的非零整数，且有整数x,y，使得。证明：若且，则
（证）
由且。
＝n(ax＋by)，即。
注意：，由此也证明了例1.1.2。

【例1.1.5】设是整系数多项式。若，则
（证）

由及
＝
（k＝1,2,…,n）
∴。
应用：若，那么。
例：设，判断7能否整除。
因＝7q＋4，故只需判断：
＝＝3082？
答：不能
素数
定义（素数与合数）
设整数p≠0,±1。如果它除了显然约数±1,±p外没有其它的约数，那么，就称为素数（或质数、不可约数）。若a≠0,±1，且不是素数，则称为合数。
约定：素数一般指正整数。
性质
最小正因数必是素数
n是正整数，当2≤p≤且pn，则n是素数。
素数有无穷多。
（证）（c）：用反证法。
假设只有有限个素数：。构造

则且（＝1,2,…,k）。
∴a必是合数存在素数p，使得。
由假设知p等于某个
一定整除
但素数，矛盾。
因此，假设是错误的，即素数必有无穷多个。
性质（b）的应用：快速判断素数。
扩展：设是全体素数按大小顺序排成的序列，以及
。直接计算可得：
，，，，
，，，
，，
前五个是素数，后五个是合数，但都有一个比更大的素因数。
未解决的问题：至今还不知道是否有无穷多个k使是素数，也不知道是否有无穷多个k使是合数。

欧几里德除法
也叫带余数除法、除法算法
初等数论的证明中最重要、最基本、最常用的工具之一。
欧几里德除法：
设a,b是两个给定的整数，b≠0。那么，一定存在唯一的一对整数q与r，满足
,
约定：b>0。上式可表为
,（2）
存在性
当时，可取，r＝0。
当ba时，考虑集合
＝{……，－3b，－2b，－b，0，b，2b，3b，……}
将实数分为长度为b的区间，a必落在某区间内，即存在整数q，使得
qb≤a＜(q＋1)b
令r＝a－bq，则有
,
唯一性
设有也满足（2）式，即

必有
当q≠时有≥b，
矛盾，故必有，。
推论：的充要条件是r＝0。
当a＝qb＋r时,有。
当满足时，就有r＝0。
一般形式
设a,b是两个给定的整数，，则对任意整数c，一定存在唯一的一对整数q与r，满足
,（3）
此外，的充要条件是。
例：a＝100，b＝30，c＝10，则10≤r＜40，即100＝3*30＋10
若c＝35，则35≤r＜65，即100＝2*30＋40
若c＝－50，则－50≤r＜－20，即100＝5*30＋(－50)

不完全商和余数
【定义1.1.2】设a＝bq