初等数论整数.ppt

初等数论 §1 整数 整数、数论 整数是这样一些数：...，-2，-1，0，1，2，… 一般把整数作为一种自明的概念来接受，若想深究其哲学与逻辑意义可以参看弗雷格的《算术基础》 数论的很大一部分内容就是研究整数的性质。数论基本就是都整数本身性质的研究 除非另有说明，小写字母总表示整数 最小整数原理 一个下有界的非空整数集合总包含有它的最小元。 同样，把最小整数原理作为自明的公理来接受。 最小整数原理与数学归纳法是等价的方法：如果把数学归纳法作为公理，可推出最小整数原理，如果把最小整数原理作为公理，可推出数学归纳法。 整除的概念 定义 设a,b是任意两个整数，其中b≠0，如果存在一个整数q使得等式 a=bq (1) 成立，我们就说b整除a或a被b整除，记作b|a，此时我们把b叫作a的因数，把a叫作b的倍数。 如果(1)里的整数q不存在，我们就说b不能整除a或a不被b整除 定理1（传递性） 若a|b,b|c,则a|c b=q1a c=q2b c=q1q2a 定理2 1、若d|a,d|b，则d|(a+b) 2、若d|a,则对任何整数c,d|ca 3、以上两条可总结为：若d|a1,d|a2,…,d|an,则对任何整数c1,c2,…,cn,有d|(c1a1+c2a2+…+cnan) 应用：若d整除一个等式一端的所有项，则它也整除另一端 定理3(带余数除法) 若a,b是两个整数，其中b>0,则存在着两个整数q及r，使得 a=bq+r，0≤r<b 成立，而且q和r是唯一的 证明：存在性 感性认识： 作整数数列…,-3b,-2b,-b,0,b,2b,3b,… 则a必在上述序列的某两项之间，即存在一个整数q使得qb≤a<(q+1)b成立.令a-qb=r,则a=bq+r,而0≤r<b 证明：存在性 严格地表述： 考虑整数a-bt构成的集合S，其中t∈Z。因为S中有非负元(a为正时是a,a为负时,根据阿基米德公理,存在整数n,使得nb>-a,则a+nb>0)，由最小整数原理，我们知道S有一个最小的非负元，把它叫做r，并设q是相应的t值，则a-bq=r,且r≥0.为了完成证明，尚需证r<b.假若不然，则有r=b+r1,且r1 ≥0.因此，r1=r-b=a-bq-b=a-b(q+1).这说明r1在集合S中.但0≤ r1=r-b<r,这与r是S中的最小非负元矛盾 证明：唯一性 假设有q,r和q1,r1,使 a=bq+r=bq1+r1 其中0≤r<b,0 ≤ r1<b. 两式相减，有 0=b(q-q1)+(r-r1). 由于b整除此式左端以及右端的第一项，它也整除右端另一项：b|(r-r1).但因0≤r<b,0 ≤ r1<b,有 -b<r-r1<b. 因而r-r1=0，即r=r1,同时q=q1.因此q和r是唯一的. 最大公约数 我们称d是a和b的最大公约数(记为d=(a,b)),当且仅当: (i) d|a,d|b; (ii) 若c|a,c|b,则c≤d 条件(i)说明,d是a和b的公因子 条件(ii)说明,它是这种公因子中最大的一个 注意,若a和b不同时为零,那么a和b的公因子集合是以a,b,-a和-b中最大者为其上界的整数集.根据最小整数原理,该集合有最大元,故a和b的最大公因子存在,而且唯一.注意:一般约定(0,0)没有定义 如果(a,b)有意义,则它是正数 定理4 若a,b是不全为0的整数,则 (i) a,b与|a|,|b|的公因数相同 (ii)(a,b)=(|a|,|b|) 证明：(i)成立的话，(ii)是显然成立的 证明(i)只需说明两点： 1、任意d|a,d|b,有d | |a|,d | |b| 2、任意d | |a| , d | |b| , 有d|a , d|b 定理5(欧几里得辗转相除法) 若a,b都不为0，且a=bq+r,0≤r<b，则 (a,b)=(b,r) 设d=(a,b),c=(b,r) 由a=bq+r,d|a,d|b,可得d|r,这说明d是b和r的公因数,故d≤c 同理由a=bq+r,c|b,c|r,可得c|a,故c≤d d≤c且c≤d可推出c=d 故(a,b)=(b,r) Euclid算法 int gcd(int a , int b) { return (b == 0 ? a : gcd(b , a % b)); } Function gcd(a , b : longint) : Longint; Begin if (b = 0) then gcd := a else gcd := gcd(b , a mod b); End; 定理6 设a,b是任意两个不全为0的整数,若m是任一正整数