资源描述：
《《数论算法》教案 1章(整数的可除性)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数论算法》第一章整数的可除性第1章整数的可除性内容1.整除性2.公因数、最大公因数3.辗转相除法（欧几里得除法）4.算术基本定理要点培养对数论问题的认识及证明问题的思路《数论》从研究整数开始，叫“整数论”。经进一步发展，叫做“数论”。确切地说，数论是研究整数性质的学科。自然数（正整数）负整数0（统称整数）。算术运算：加、减、乘、除（四则运算）。加法、减法和乘法在整数范围内可以毫无阻碍地进行。但整数之间的除法在整数范围内并不一定能够无阻碍地进行。《数论算法》主要从应用角度出发，研究数论问题中实用的方法和技术。1.1整除的概念欧几里得除法（
2、一）整除概念【定义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。◆说明：39/39《数论算法》第一章整数的可除性（1）q也是a的因数，并将q写为a/b或；（2）当b遍历整数a的所有因数时，－b也遍历整数a的所有因数；（3）当b遍历整数a的所有因数时，a/b也遍历整数a的所有因数。例：设a＝6，则有（1）当b＝3时，q＝2＝6/3（2）当b＝1,2,3,6,－1,－
3、2,－3,－6时有－b＝－1,－2,－3,－6,1,2,3,6（3）当b＝1,2,3,6,－1,－2,－3,－6时有a/b＝6,3,2,1,－6,－3,－2,－1【特例】：（1）0是任何非零整数的倍数；（2）±1是任何整数的因数；（3）任何非零整数a是其自身的倍数，也是其自身的因数。（一）性质（1）设，则│。（证）a＝bq－a＝q(－b)其余类推。【例1.1.1】30的所有因数：±1，±2，±3，±5，±6，±15，±30（2）传递性：，（证）且b＝c，a＝ba＝cc│a。（3），，则39/39《数论算法》第一章整数的可除性（1），，则对
4、任意整数s、t，有推广：（2）若，，则a＝±b（证）a＝bb＝aa＝＝1＝±1（3）（c≠0）（4）若，则≤（一）例【例1.1.2】证明：若且，则。（证）已知。。即m＝7qn＝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。39/39《数论算法》第一章整数的可除性【例1.1.5】设是整系数多项式。若，
5、则（证）由及＝（k＝1,2,…,n）∴。应用：若，那么。例：设，判断7能否整除。因＝7q＋4，故只需判断：＝＝3082？答：不能（一）素数（1）定义（素数与合数）设整数p≠0,±1。如果它除了显然约数±1,±p外没有其它的约数，那么，就称为素数（或质数、不可约数）。若a≠0,±1，且不是素数，则称为合数。约定：素数一般指正整数。（2）性质（a）最小正因数必是素数（b）n是正整数，当2≤p≤且pn，则n是素数。（c）素数有无穷多。（证）（c）：用反证法。假设只有有限个素数：。构造39/39《数论算法》第一章整数的可除性则且（＝1,2,…,k
6、）。∴a必是合数存在素数p，使得。由假设知p等于某个一定整除但素数，矛盾。因此，假设是错误的，即素数必有无穷多个。性质（b）的应用：快速判断素数。扩展：设是全体素数按大小顺序排成的序列，以及。直接计算可得：，，，，，，，，，前五个是素数，后五个是合数，但都有一个比更大的素因数。未解决的问题：至今还不知道是否有无穷多个k使是素数，也不知道是否有无穷多个k使是合数。（一）欧几里德除法也叫带余数除法、除法算法初等数论的证明中最重要、最基本、最常用的工具之一。（1）欧几里德除法：设a,b是两个给定的整数，b≠0。那么，一定存在唯一的一对整数q与r
7、，满足,39/39《数论算法》第一章整数的可除性约定：b>0。上式可表为,（2）（1）存在性当时，可取，r＝0。当ba时，考虑集合＝{……，－3b，－2b，－b，0，b，2b，3b，……}将实数分为长度为b的区间，a必落在某区间内，即存在整数q，使得qb≤a＜(q＋1)b令r＝a－bq，则有,（2）唯一性设有也满足（2）式，即必有当q≠时有≥b，矛盾，故必有，。（3）推论：的充要条件是r＝0。当a＝qb＋r时,有。当满足时，就有r＝0。（4）一般形式设a,b是两个给定的整数，，则对任意整数c，一定存在唯一的一对整数q与r，满足39/39《
8、数论算法》第一章整数的可除性,（3）此外，的充要条件是。例：a＝100，b＝30，c＝10，则10≤r＜40，即100＝3*30＋10若c＝35，则35≤r＜65，即100＝2*30＋40若c
