数论基础

第一章数论基础第一章数论基础1.1整除性1.2最大公约数(greatestcommondivisor)1.3最小公倍数(leastcommonmultiple)1.4素数(prime)及复合数(compositenumber)1.5素因子分解1.6同余式(congruenceexpression)1.7完全剩余组及与模互素的剩余组1.8数论中特殊的函数及特殊的数1.9同余式的一般性讨论第一章数论基础1.1整除性设x为一实数,［x］表示不超过x的最大整数。例如：［5］=5，=1，［e］=2,［-π］=-4。若x为正，则［x］为x的整数部分,［x］≤x＜［x］+1若取x为有理数a/b,b0则有10baba第一章数论基础即bbaba0令rbaba可得brrbbaa0,由此有：第一章数论基础命题1任给二整数a及b（b＞0），必有二整数q及ra=bq+r，0≤r＜b其中，数q叫做b除a的不完全商数，数r叫做b除a的最小正余数。例如，设b=14，177=14·12+90＜9＜14-64=14·(-5)+60＜6＜14154=14·11+00=0＜14第一章数论基础定义1若命题1的r为0，即有a=bq，则称a为b的倍数，称b为a的约数（因子或因数）；常谓b可整除a，记做b|a。又以ba表示b不能整除a。若a=bq，而b既非a又非1，则称b为a之真因数。关于整除性，显然有：第一章数论基础命题2对a,b,c∈Z,b≠0,c≠0(1)1|a;(2)b|b;(3)b|0;(4)若b|a∧c|b,则c|a;(5)若b|a,则bc|ac(6)若c|d,c|e,则对任意的m,n∈Z有c|（dm+en）;(7)若bc|ac,则b|a。第一章数论基础证明只证（6）式。事实上)(|)()(,,,,|/2121212121endmcnqmqqcqnqmqcncqmcqendmZnmcqecqdZqqecdc第一章数论基础1.2最大公约数（greatestcommondivisor）定义1对任意正整数m,若m|a∧m|b,则称m为a和b的公约数。公约数中最大者，称为a与b的最大公约数。常记做(a,b)定义2若（a,b）=1，称a与b互素。例如：8与13互素；13与21互素；12与25互素。第一章数论基础命题1如果a=bq+c,则有（a,b）=（b,c）。证明证明思路是：凡是a、b的约数，都是b、c的约数；凡是b、c的约数，都是a、b的约数。对任意的x有cxqttxqxtxtcxtbxtabxax|)(||212121即有cxbx||第一章数论基础反之bxaxcxbx||||由x的任意性可知，a、b的约数集合与b、c的约数集合相同，其中最大的约数应相同，(a,b)=(b,c)·求最大公约数的Euclid按照本节命题1有第一章数论基础a=bq1+r1,0＜r1＜bb=r1q2+r2,0＜r2＜r1……rk-2=rk-1qk+rk,0＜rk＜rk-1……rn-2=rn-1qn+rn,0＜rn＜rn-1rn-1=rnqn+1,rn+1=0(1.2.1)第一章数论基础因b＞r1＞r2＞…是一递减的正整数列，包含至多b个正整数，上述等式组在有限步后必可做到rn+1=0。由本节命题1(a,b)=(b,r1)=(r1,r2)=…=(rn-1,rn)=rn推论1数a和数b的公约数集合与它们的最大公约数的约数集合相同。第一章数论基础推论2这个最大公约数等于rn(n∈Z+)，即等于上述等式组中最后的不等于零的余数。推论3若b|a,则(a,b)=b。观察等式组（1.2.1）的构造过程不难发现：当某个余数rk(k∈Z+)不为0时，即将除数作为被除数，并将余数作为除数再写出一个等式，依此类推，直至余数是零为止。故可将Euclid算法改写如下：第一章数论基础·改进的Euclid№1输入正整数A，B；№2MA;NB;№3KM-［M/N］*N；№4若K＞0,则MN,NK,转№3；№5GCDN（N为最大公约数）；输出A,B,GCD；№6结束。第一章数论基础命题2设m表示任意正整数，则有（am,bm)=(a,b)m。证明对等式组（1.2.1）逐项地乘以m，可得一新的等式组，在其中代替a,b,r1,…rn的是am,bm,…,rnm，因此(am,bm)=rnm=(a,b)m。第一章数论基础命题3设δ表示数a和b的任意公约数，则有（a/δ,b/δ）=(a,b)/δ。特别地，当δ=(a,b)时有(a/(a,b),b/(a,b))=1（即a,b分别被它们的最大公约数除后所得的两个商数互素）。证明借用命题2有),(,,,),(bababababa第一章数论基础命题4如果(a,b)=1,则(ac,b)=(c,b)。证明只需证(ac,b)|(c,b)∧(c,b)|(ac,b)事实上，bcbacacbacbbacacbac|),(|),(|),(|),(依推论1有(ac,b)|(ac,bc)(ac,b)|(a,b)c(ac,b)|c(ac,b)|b∧(ac,b)|c(ac,b)|(b,c)反之因而(c,b)|ac∧(c,b)|b(c,b)|(ac,b)(ac,b)=(c,b)第一章数论基础命题5若(a,b)=1∧b|ac,则b|c。证明由于(a,b)=1(ac,b)=(c,b)又cbbcbbacbbbacbacb|),(|),(||||第一章数论基础命题6如果(ai,bj)=1（i=1,2,…,m;j=1,2,…,n），则1,11minjjiba证明利用命题4有1),(,),(),(),(,3322211kmmikimikimikimikimikibababaababaaba同理可得1),(),(,12111miinnjmiijmiinjjababab第一章数论基础命题7求两个以上的数的最大公约数的问题，可以化成求两个数的最大公约数的问题。亦即，为了求数a1,a2,…,an的最大公约数，可写出如下的一串数：(a1,a2)=d2,(d2,a3)=d3,(d3,a4)=d4,…,(dn-1,an)=dndn即为所有已知n个数的最大公约数。第一章数论基础证明根据推论1，数a1,a2的公约数集合与d2的约数集合相同，所以数a1,a2,a3公约数集合与数d2和a3的公约数集合相同，即与d3的约数集合相同。然后肯定，数a1,a2,a3,a4的全体公约数所成之集与d4约数集相同，……最后，数a1,a2,…,an的公约数所成之集与dn约数之集相同。因而dn的最大公约数是dn自身，所以它就是数a1,a2,…,an的最大公约数。观察以上证明，可以肯定推论1对两个以上的数也成立。命题2和命题3对两个以上的数也是成立的，这是因为用m去乘或者用δ去除所有的数a1,a2,…,an,正像所有d2,d3,…,dn都被m乘或被δ除一样。第一章数论基础命题8对a,b的最大公约数d,存在着二整数s,t,使得d可表d=sa+tb(1.2.2)证明若有b|a或a|b，不妨设为前者，则d=b=0·a+1·b，此即(1.2.2)式中各项的形式，下设ab∧ba,辗转相除可有等式组(1.2.1)中各式。由等式组(1.2.1)的第一式得11011rbqba第一章数论基础又由等式组(1.2.1)的第二式得2121011rrqrb依此类推,有kkkrqqqba11011011第一章数论基础令0110111kkkkkqqUSVT则(1.2.3)kkkkkkrrUSVTba1(1.2.4)第一章数论基础注意到10110111kqq故kkkkkUSVT)1(由（1.2.4）式不难得到baTSVUbaUSVTrrkkkkkkkkkkkkkk)1()1()1()1(1111第一章数论基础特别地bTaSrkkkkk)1()1(1取k=n,则因rn即a,b的最大公约数d而得bTaSdnknn)1()1(1这又是（1.2.2）式的形式。第一章数论基础下面给出求Sk,Tk令1111111111011kkkkkkkkkkkkkkkkkSUqSTVqTqUSVTUSVT比较前后两矩阵知212111,,kkkkkkkkTVSUTVSU(1.2.5)第一章数论基础2121,kkkkkkkkVqTTSqSS1111,kkkkkkkkVqTTUqSS(1.2.6)由（1.2.5）式及（1.2.6）式有(1.2.7)在（1.2.3）式中取k=1有01111111qVSVT由此及（1.2.5）式可求得1,;0,11111010SqTUSVT(1.2.8)第一章数论基础·求二数A，B№1输入A,B；№2MA;NB；T01;S00;№3若M=N打印″(A,B)=M=S0*M+T0*N″;或″(A,B)=N=T0*M+S0*N″；转№9；第一章数论基础№4若M＜N,DM;MN;ND;№5若N|M,打印″(A,B)=N=T0*M+S0*N″;转№9；№6Q1［M/N］;S11;T1Q1;T=1;№7当M≠N*Q1时，反复做如下各步:MN;NM-N*Q1;Q1［M/N］;S2S1*Q1+S0;T2T1*Q1+T0;S0S1;T0T1;S1S2;T1T2;T-T№8打印″(A,B)=N=T*S1*A+(-T*T1)*B″;№9结束。第一章数论基础1.3最小公倍数（leastcommonmultiple）定义若a|x∧b|x，则x称做a与b的公倍数，最小的正的公倍数叫做a，b的最小公倍数，［a,b］命题1两个数a，b的最小公倍数，等于它们的乘积除以它们的最大公约数。证明设M是二整数a，b的任意公倍数。因它是a的倍数，所以M=ak，这里k是整数。但M又是b的倍数，所以M/b=ak/b也应是整数。假定［a,b］=d,a=a1d,b=b1d,上面的整数就可表示成a1k/b1，这里［a1,b1］=1。因此，k应被b1除尽，即k=b1t=bt/d，这里t是整数。由此推得第一章数论基础dabtakM反之，明显地，这种形式的每一M既是a的倍数，也是b的倍数，因此也是数a和b的所有公倍数的一般形式。这些公倍数中的最小正数，即最小公倍数，在t=1时得到。它就是dabm亦即),(],[baabba引用m，求M的公式可以改写成M=mt第一章数论基础命题2两个数的公倍数的集合与它们的最小公倍数的倍数的集合相同。·求二数A，B№1利用Euclid算法求A,B的最大公约数GCD；№2LCMA*B/GCD;№3输出A,B,GCD;№4结束。第一章数论基础命题3设要求数a1,a2,…,an的最小公倍数，［a1,a2］=m2,［m2,a3］=m3,…,［mn-1,an］=mn用这种方法得到的mn就是所有已知数的最小公倍数。证明事实上由命题2知，数a1和a2的公倍数的集合与m2的倍数的集合相同，所以数a1，a2和a3的公倍数的集合与m2和a3的公倍数的集合相同。然后肯定，数a1,a2,a3,a4的公倍数的集合与m4的倍数的集合相同