数论基础课件

第一章数论根底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,b>0那么有即令可得由此有：命题1任给二整数a及b〔b＞0〕，必有二整数q及r使a=bq+r，0≤r＜b其中，数q叫做b除a的不完全商数，数r叫做b除a的最小正余数。例如，设b=14，有177=14·12+90＜9＜14-64=14·(-5)+60＜6＜14 154=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〕式。事实上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有即有反之由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。观察等式组〔〕的构造过程不难发现：当某个余数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。证明对等式组〔〕逐项地乘以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有命题4如果(a,b)=1,那么(ac,b)=(c,b)。证明只需证(ac,b)|(c,b)∧(c,b)|(ac,b)。事实上，依推论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)又命题6如果(ai,bj)=1（i=1,2,…,m;j=1,2,…,n），则证明利用命题4有同理可得命题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)的第一式得又由等式组(1.2.1)的第二式得依此类推,有令那么(1.2.3)(1.2.4)注意到故由〔〕式不难得到特别地取k=n,那么因rn即a,b的最大公约数d而得这又是〔〕式的形式。下面给出求Sk,Tk的递推公式：令比较前后两矩阵知(1.2.5)(1.2.6)由〔〕式及〔〕式有(1.2.7)在〔〕式中取k=1有由此及〔〕式可求得(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是整数。由此推得反之，明显地，这种形式的每一M既是a的倍数，也是b的倍数，因此也是数a和b的所有公倍数的一般形式。这些公倍数中的最小正数，即最小公倍数，在t=1时得到。它就是亦即引用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的倍数的集合相同，等等，而因为mn的最小正倍数就是mn自身，所以它就是数a1,a2,…,an的最小公倍数。由此证明也可断言，命题2对于两个以上的数也成立。此外，还可肯定下述命题的正确性：命题4两两互素的数的最小公倍数等于它们的乘积。命题5假设b|a,那么［a,b］=a。1.4素数〔prime〕及复合数〔compositenumber〕按如下方法可将自然数0,1,2,…〔有些数论书中把0排除在自然数之外〕分成三类：(1)1，只有自然数1为其因子；(2)素数p，恰有两个因子，1及p自身；(3)复合数〔简称合数〕n，有真因数之自然数。此类数有两个以上的因子。最初的假设干素数是2，3，5，7，11，13，17，19，23，29，31，37，41，43，…2所能整除之数谓之偶数；非偶数之整数称为奇数。显见大于2之偶数皆非素数。命题对一数a(a＞1)，假设在小于等于 的自然数中找不到a的真因子，那么a为素数。证明用反证法，设假设如命题所述而a却不是素数，那么必然存在着a的真因子q使得注意到a1也是a的真因子但 ，这与假设不符，故命题得证。·判一数a(a＞1)是否为素数的算法1对2，3，4，…， 逐个检查，看其是否为a的约数。若都不是，则a为素数;若有一个是，则a不是素数。№1输入正整数A(A＞1)；№2若A=2，打印"2是素数";转№7；№3J1；№4JJ+1；№5判 若是，打印"A是素数"；转№7;№6判J|A?若JA，转№4；若J|A，打印"A不是素数"；№7结束。·判一数a(a＞1)是否为素数的算法2注意到:2是惟一的偶素数,3是最小的奇素数。№1输入正整数A(A＞1)；№2若A=2或A=3，打印："A为素数"；转№5；№3若A为偶数，打印："A不是素数"；转№5；№4对3， ，步长取2，逐个检查看其是否为A的因子。若都不是，则A为素数；若有一个是，则A不是素数；№5结束。·找出N(N＞3)以下全部素数的算法№1输入N(N＞3)；№2打印"2是素数，3是素数"；№3K5;№4若K＞N，转№7；№5判K是否为素数，若是，打印"K为素数"；№6KK+2,转№4；№7结束。·用数论中的筛法〔sievemethod〕求正整数N(N＞1)以下的全部素数对序列2，3，4，…，N从22开始，每隔1个数将其划去；从32开始，每隔5个数将其划去；从52开始，每隔9个数将其划去；从72开始，每隔13个数将其划去；从112开始，每隔21个数将其划去；…从p2开始，每隔2p-1个数将其划去；…上述过程一直进行到 (［x］表示不超过x的最大整数)为止,剩余的未筛划掉的数全是素数。将上述序列存放在一维数组A中，这利用K循环中的赋值语句A(K)K(K=2，3，…，N)即可实现。对于划去，可采用冲零的办法(如A(J)0)来实现。对每隔2p-1个数，可用循环步长取2p来实现。剩下来的问题是如何确定作为筛划基准的素数p。这里不用再去检查p是否为素数。只需在序列A(K)中找出前一次以q为基准，从q2开始向后筛划后，剩下的非零数中第一个大于q的即是。··算法1№1输入N；A(2)2;№2对K=3,N，步长取2，A(K)K;I3；№3LI*I;№4对J=L,N，步长取2*I,A(J)0；№5对K=I+2,［ ］，步长取2，若A(K)≠0，则IK，转№3；№6对K=2,N，打印非零A(K)；№7结束。对算法1的改进如下：注意到2是惟一的偶素数，N以下的素数除去2外都将在奇数中产生，故不用存放除2外的其它偶数。这可用A(2)2及A(K)2K-3(K=3,4,…,N)来实现，从而使被筛序列及其存放单元对应如下：235791113151719A(2)A(3)A(4)A(5)A(6)A(7)A(8)A(9)A(10)A(11)212325272931333537…A(12)A(13)A(14)A(15)A(16)A(17)A(18)A(19)A(20)…对这一序列的筛划将从32开始。从32(A(6))开始，每隔2个数将其划去；从52(A(14))开始，每隔4个数将其划去；…从p2(A(p2+3)/2)开始，每隔p-1个数将其划去；…以上过程进行到［］为止。·算法2№1输入N(N＞2)；№2对K=1,［(N+3)/2］，A(K)0；№3A(K)2;№4对K=3,［(N+3)/2］,A(K)2*K-3;IA(3);№5LI*I;L1(L+3)/2;L2(L+3)/2+1№6对J=L1,［(N+3)/2］，步长取I,A(J)0；№7对J=L2,［］，若A(J)≠0,则IA(J)并转№5；№8K=2,［(N+3)/2］,打印非零A(K)；№9结束。·验证哥德巴赫猜测(Goldbachguess)的算法“哥德巴赫猜测〞是指德国数学家哥德巴赫在200多年前提出的“每一个大偶数N(N＞4)都可以表示为两个奇素数之和；每一个大奇数m(m＞7)都可以表示为三个奇素数之和。〞这样一个至今未证明的猜测。此即人们常说的“1(1个奇素数)+1(1个奇素数)=1(1个大偶数)〞及“1+1+1=1〞这个数论中的趣题。例如：20=3+17=7+13，28=5+23=7+11，33=11+11+11=3+7+23。要想证明这个猜测是很难的，这里只是给出一个游戏算法，可以用来在计算机上检验若干偶数，看其是否符合“哥德巴赫猜想”。具体做法是将偶数N分成两个奇数N1,N2之和，其中N1≤N/2,N2≥N/2。进而分别判断N1,N2是否为素数，若N1,N2都是，则输出标记，若有一个不是,则N1

N1+2,N2N2-2并继续检验，一直进行到N1＞N/2为止。№1输入N(N＞4∧N为偶数)；(偶数可用表达式［N/2］=N/2判别)№2N13；N2N-N1；№3分别检验N1,N2是否为素数，若都是则输出标记，转№5;否则N1N1+2;N2N2-2；№4若N1＜［N/2］转№3；否则输出信息“皇冠上的明珠属于你”№5结束。1.5素因子分解命题1每一整数a或者与素数p互素或者能被p除尽。证明观察a与p的最大公约数(a,p)，它要么等于1，要么等于p。在前一种情形下，a与p互素，在第二种情形下，a被p除尽。命题2如果某些因子的乘积能被p除尽，那么其中至少有一个因子能被p除尽。证明由命题1，每个因子或者与p互素，或者被p除尽。而如果所有因子都与p互素，那么由节命题6知，它们的乘积也与p互素,因此至少有一个因子被p除尽。命题3(算术学根本定理)每一个大于1的整数都能分解成它的素因子之积，且如不计排列的先后顺序，其分解法还是惟一的。证明假设a为素数，自不待言。今设a非素数，而p1为其最小非1因子。显见p1为素数，令a=p1a1(1＜a1＜a)，假设a1已为素数，命题已明；不然，再令p2为a1的非1最小因子，可得a=p1p2a2(1＜a2＜a1＜a)；如是而下，直到引出一个等于1的ak+1而止。因a＞a1＞a2＞…＞1至多只有a项，故这种ak+1总能求得。最后我们得到a=p1p2…pk其中,p1,p2,…,pk皆为素数。下证惟一性。假设对同一a还有第二个素因子分解式a=q1q2…qt那么p1p2…pk=q1q2…qt上式右端能被q1除尽，因此根据命题2，上式左端至少有一个因子应该被q1除尽，不妨设p1能被q1除尽，那么p1=q1〔除掉1以外，p1只能被p1除尽〕。约掉两边因子p1=q1，得到p2p3…pk=q2q3…qt。对这个等式重复引用前述论证可得p3…pk=q3…qt，依次类推，直到有一边〔不妨设为左边〕的因子全被约掉为止。与此同时，右边所有因子也应被全部约掉了，原因是1=qk+1…qt对大于1的qk+1…qt不可能成立。这样，第二个素因子分解式与第一个完全相同。例如：105=3·5·7；180=2·2·3·3·5。在a的因子分解式中，可以有一些因子是重复的。用p1,p2,…,pk表示a的所有不同的素因子，用α1,α2,…,αk表示它们在a中重复出现的次数，可以得到a的标准因子分解式例如588000=25·3·53·72,540=22·33·5·对任给正整数N(N＞1),求其素因子分解式的算法利用一维数组P存放诸素因子，并用表达式M/K=［M/K］判K是否整除M。№1输入正整数N(N＞1)

MN（保存原始数据）；

I0（用变量I做计数器）；№2对K=2,［ ］，当M/K=［M/K］时反复执行；

I=I+1;P(I)K;MM/K；№3若I=0，输出：″N为素数″；否则对J=1,I，输出N的素因子P(J)；№4结束。命题4(Euclid定理)素数无穷多。证明假设只有有限个素数，命为p1,p2,…,pn。观察下式N=p1p2…pn+1假设N本身是素数，这与假设矛盾；假设N为复合数，那么其素因子p必不与pi(i=1,2,…,n)中的任一个相同，这又与假设不符。1.6同余式(congruenceexpression)通常在做除法运算时，人们总是关注运算的结果——商数，而把余数置于其次。这里将侧重强调余数的概念，并从中引出假设干有用的结果。定义由节命题1，取定正整数m做除数，对每个整数做被除数时，都能得到一个确定的余数。其中，m常称为模〔module〕。(1)如果二整数a和b对应的是同一余数，那么称a，b关于模m同余〔congruent〕。(2)关于模m同余的数a和b，常记做a≡b(modm)读作：关于模m，a与b同余。从而，若a≡b(modm)，则称a与b在模m同余的意义下等价。反之，以ab(modm)表示a与b模m不同余。命题1以下四种说法是等价的：(1)a≡b(modm);(2)存在整数t使a-b=mt；(3)a可以表示成a=b+mt；(4)m|(a-b)。

证明(1)(2):a≡b(modm)a=mq1+r∧b=mq2+r(0≤r＜m)a-b=m(q1-q2)=mt(t=q1-q2)；(2)(3):a-b=mta=b+mt；(1):a=b+mt，令b=mq2+r(0≤r＜m)a=m(q2+t)+r=mq1+r(q1=q2+t)a≡b(modm);至于（4），显见就是（2）。(3)命题2同余式的等价性质：(1)a≡a(modm)(自反性)；(2)a≡b(modm)b≡a(modm)（对称性）；(3)a≡b(modm)∧b≡c(modm)a≡c(modm)（传递性）。证明(1)显然；(2)a≡b(modm)a-b=mtb-a=m(-t)=ms(s=-t)b≡a(modm);(3)a≡b(modm)∧b≡c(modm)a-b=mt1∧b-c=mt2a-c=m(t1+t2)=mt(t=t1+t2)a≡c(modm)。命题3同余式的累加性质：设ai≡bi(modm),其中,i=1,2,…,k,那么证明由命题1，有

推论1

a+b≡c(modm)a≡c-b(modm)。

证明将-b≡-b(modm)加到同余式a+b≡c(modm)上即得。

推论2

a≡b(modm)a+km≡b(modm)。

证明将km≡0(modm)加到同余式a≡b(modm)上即得。命题4同余式的累乘性质。设ai≡bi(modm)，其中，i=1,2,…,k，那么证明由命题1

推论1

a≡b(modm)ak≡bk(modm)。

证明令命题4中的ai=a∧bi=b立得。

推论2

a≡b(modm)ak≡bk(modm)。

证明

a≡b(modm)∧k≡k(modm)ak≡bk(modm)。概述命题3、命题4及其推论为：若干对模m的同余式，关于加、减、乘保持封闭。这种概述对除法不一定成立，例如：3·2≡1·2(mod4)，2≡2(mod4)，但3≡1(mod4)。关于除法，可有如下命题：命题5设a≡b(modm)∧d为a，b的任一公约数，假设(d,m)=1，那么证明由题设有a=a1d∧b=b1d∧a≡b(modm)a-b=(a1-b1)d=mt

m|(a-b)m|(a1-b1)d但(d,m)=1，由1.2节命题5（b|ac∧(a,b)=1b|c）知即命题6同余式的两边和模可以乘同一整数。证明a≡b(modm)a=b+mtak=bk+mktak≡bk(modmk)。命题7同余式的两边和模可以被它们的任意公约数除。证明设a≡b(modm),d|a∧d|b∧d|m,则a=a1d∧b=b1d∧m=m1da1d=b1d+m1dta1=b1+m1ta1≡b1(modm1)。

命题8若a≡b（modmi）(i=1,2,…,k)，m=［m1,m2,…,mk］，则a≡b(modm)

证明

a≡b(modmi)mi|(a-b)(i=1,2,…,k)m|(a-b)a≡b(modm)。

推论如对i≠j有(mi,mj)=1且a≡b(modmi)（i,j=1,2,…,k），则

命题9设a≡b(modm)∧d|m，则a≡b(modd)。证明

a≡b(modm)∧d|md|m∧m|(a-b)d|(a-b)a≡b(modd)命题10设a≡b(modm)，（1）若存在d，使d|a∧d|m，则d|b；（2）若存在d，使d|b∧d|m，则d|a。

证明

a≡b(modm)a=b+mt，由命题1，（1）、（2）显然。

推论若a≡b(modm)，那么(a,m)=(b,m)。命题11若(a,m)=1，则对任意的b，在模m等价的意义下，恰有一数x使ax≡b(modm)

证明因(a,m)=1，由1.2节命题8，存在s,t，使得as+mt=1asb+mtb=basb≡b(modm)取x=sb，即有ax≡b(modm)。又若ax≡b(modm)且ay≡b(modm)，这导致ax≡ay(modm)，注意到(a,m)=1，由命题5，有x≡y(modm)。

推论设p为素数，若a≡0(modp),则对任意的b，在模p等价的意义下，恰有一数x，使ax≡b(modp)。

命题12（孙子定理）设m1,m2,…,mk两两互素，并对每一个mi指定一个整数ai，则在模等价的意义下，恰有一数x存在，使x≡ai(modmi),i=1,2,…,k

证明如下采用构造法求Li(i=1,2,…,k)，使满足(1.6.1)(1.6.2)因j≠i时， ，由命题6，有ci使 。取 ，显见Li适合（1.6.2）式。今取(1.6.3)则现证惟一性。若存在x,y都适合（1.6.1）式，则有x≡y(modmi),i=1,2,…,k,注意到i≠j时(mi,mj)=1，由命题3的推论知·本命题的构造性证明过程，给出了一个求x的简便算法，现改写如下：№1输入Mi,ai(i=1,2,…,k);№2M1;№3对i=1,k,做MM*Mi;№4MMiM/Mi(i=1,2,…,k);№5CiMMi(i=1,2,…,k);№6对i=1,k,做当(MMi-1)/Mi≠［(MMi-1)/Mi］时反复做

MMiMMi+Ci;№7LiMMi(i=1,2,…,k);№8x0;№9对i=1,k,做xx+aiLi;№10打印x;№11结束。?孙子算经?记有：“物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？〞用上述的符号可将此题表示为求x，使满足x≡2(mod3)x≡3(mod5)x≡2(mod7)故见题目即为求上同余式组之解。解此问题有如下歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。意为：用70乘3除所得的余数，21乘5除所得的余数，15乘7除所得的余数，再将其相加，然后减105的倍数即可求得结果。具体计算为2×70+3×21+2×15=233,233-2×105=2323即为所求。观察上式不难发现，70为5和7的倍数且3除恰余1；21为3和7的倍数且5除恰余1；15为3和5的倍数且7除恰余1，从而70a1+21a2+15a3显见有3除余a1，5除余a2，7除余a3。又105是3、5及7的最小公倍数，累减之后即可求得最小正数23。如不取23，直接用233检验，也是符合题目要求的，但请不要忘记233≡23(mod105)例如，表演者请观众随意写一相当大的数。任意颠倒各位数字所得的数与原数相减，然后任意删去差中的一个非零数字，再把结果告诉表演者。表演者把此数输入计算机，计算机就能推算出删去的数字是什么并加以显示。例如，观众写的数：3208754颠倒顺序后：8047325相减后的差：4838571=8047325-3208754观众删去数字7，结果为：483851。表演者将此数输入计算机。计算机立即显示出数字7给观众看！这当然要先埋伏一道程序在计算机内，下面给出具体算法。引理1设 ，令y表示x的各位数之和，即有 ，那么x≡y(mod9)证明只需证x-y≡0(mod9)。因显见，当n>1时

引理2若x=x1x2…xn（观众给的数）， （颠倒顺序后的数），则x-x′≡0(mod9)证明令显见y=y′,从而x-x′=x-x′-(y-y′)=(x-y)-(x′-y′)

由引理1有x-x′=x-y-(x’-y’)=0(mod9)引理2指出x-x′≡0(mod9),即观众写的数与颠倒其顺序后的数相减，所得的差能被9除尽。例如：523〔原数〕；325〔颠倒顺序后的数〕；198〔差〕。(198)≡0(modm)。假设删掉了其中的8，那么19≡(1+9)≡1(mod9)。用9减1即得8。·求解上题的算法№1输入m；№2对k=0，8,做假设m≡k(mod9)那么打印:″删去的数是9-k；″№3结束。1.7完全剩余组及与模互素的剩余组

定义1关于模m同余的数组成由模m决定的数类。由定义可知，与同一类的所有数对应的是同一个余数r，观察mq+r，令q遍历所有的整数，即可得到这个类里的所有数。对应于r的m个不同的值0,1,2,…,m-1,有m个由模m决定的数类。

定义2在一个类中任取一数x做代表，对于同一类的所有数而言，x都叫做模m的剩余。定义3模m的一个剩余x，在某种意义上也代表了整个数类。该数类常记做［x］m，称其为模m的一个剩余类，或简称x类。定义4当q=0时，所得到的剩余恰为余数r，称为非负的最小剩余。按绝对值说最小的剩余ρ叫做绝对的最小剩余。明显地，当r＜m/2时，有ρ=r；当r＞m/2时，有ρ=r-m；最后当m为偶数且r=m/2时，ρ可在m/2和m/2-m=-m/2二数中任取其一。

定义5从每一个数类取一个剩余，可以得到模m的一个完全剩余组。常取作完全剩余组的是全部非负的最小剩余0,1,…,m-1或全部绝对的最小剩余。依上所述，当m是奇数时，绝对的最小剩余是数列而当m是偶数时,那么是下面两个数列中的任一个命题1关于模m两两不同余的任意m个数，组成这个模的完全剩余组。

证明事实上，由于不同余的缘故，这些数属于不同的类，而因它们的个数m正好是类的个数，所以每个类里恰有一个数。命题2如果(a,m)=1∧xi(i=1,2，…,m)为模m的完全剩余组，那么axi+b〔b为任意整数,i=1,2,…,m〕也是模m的完全剩余组。证明事实上，axi+b(i=1,2,…,m)与xi(i=1,2,…,m)的个数相同〔都有m个〕。因此，根据命题1，只需证axj+b与axk+b〔j,k为i的某一取值且j≠k〕关于模m不同余即可。采用反证法，假设axj+b≡axk+b(modm)，这引出axj≡axk(modm)，但由于(a,m)=1，从而xj≡xk(modm)，这与数xj和xk不同余的前提矛盾。命题3同余类的等价性质：(1)x∈［x］m（自反性）；(2)x∈［y］my∈［x］m对称性）；(3)x∈［y］m∧y∈［z］mx∈［z］m（传递性）。证明本命题可由同余式的等价性立得。

命题4设a∈［x］m∧b∈［x］m,则(a,m)=(b,m)。

证明由1.6节命题10的推论立得。在1.6节命题12证明中的(1.6.3)式中，令ai(i=1,2,…,k)分别遍历modmi的一个完全剩余类，则可求得

mi个x。设

是这样的两个x。即有从而，若

(i=1,2,…,k)不全同，则此即在 等价的意义下得到的 个x分属于不同的剩余类。但 只有 个剩余类，故有如下命题成立：

命题5设 ，而m1,…,mk两两互素。在（1.6.3）式中，使ai(i=1,2,…,k)分别遍历modmi的一个完全剩余组，则x遍历modm的一个完全剩余组。由1.6节命题10的推论知，模m的同一数类中的数与模有同一个最大公约数（反之不然）。特别重要的是那些公约数为1的数类，即那些包含着与模互素的数所组成的类。

定义6在与模m互素的数所在的每个类中各取一个剩余组成的剩余组，称为与模m互素的剩余组。可由完全剩余组中与模互素的数组成与模互素的剩余组。通常与模m互素的剩余组从非负的最小剩余组0,1,…,m-1中分出。命题6令φ(m)表示0,1,…,m-1中与m互素的数的个数〔φ(m)常称为Euler函数〕，那么与模m互素的剩余组由φ(m)个元素组成。证明因任一完全剩余组已包括了模m同余的全部数类〔m个〕，且在非负的最小剩余组0,1,…,m-1中，恰有φ(m)个与m互素的数都可作为各自所在类的代表，故由定义6，命题为真。例如，与模42互素的剩余组是1511131719232529313741

命题7对于模m两两不同余的任意φ(m)个与模互素的数，组成一个与模m互素的剩余组。

证明因不同余且与模互素，这些数分属于与模互素的不同的类，又因它们共有φ(m)个，所以在每个与模互素的类中都取到了一个数。命题8如果(a,m)=1,且x遍历与模m互素的剩余组，那么ax也遍历与模m互素的剩余。证明事实上，ax的个数与x相同，即有φ(m)个,因此根据本节命题2，只需证明所有的ax对于模m两两不同余且都与m互素就可以了。因为前一局部已在更普遍的形式ax+b时证明过，后一局部那么从(a,m)=1∧(x,m)=1推出。

命题9设 ，而m1,…,mk两两互素。则

证明在1.6节孙子定理证明中的（1.6.3）式中，若(ai,mi)=1(i=1,2,…,k)，则由孙子定理中（1.6.1）式，有(x,mi)=1(i=1,2,…,k),而由1.2节命题6，有(x,m)=1；反之，若(x,m)=1，则必须(x,mi)=1(i=1,2,…,k)，因此,(ai,mi)=1(i=1,2,…,k)。可见，当ai(i=1,2,…,k)分别遍历一个与模mi互素的剩余组时，x就遍历一个与模m互素的剩余组。命题10设 是n的素因子分解式。当i≠j时,pi≠pj。于是

证明设p为素数，先求φ(pα)。对任意的a,(a,pα)=1,说明a不是p的倍数。而在1~pα的pα个数中，是p的倍数者共有pα-1(pα=p×pα-1)个，即p,2p,…,pα-1·p。故小于pα与pα互素者共有pα-pα-1=pα(1-p-1)个，于是φ(pα)=pα(1-p-1)。由命题9，有命题11〔Euler定理)设n＞1∧(a,n)=1，那么aφ(n)≡1(modn)。证明令x遍历从非负的最小剩余得来的与模互素的剩余组x=r1,r2,…,rφ(n)，那么ax的非负的最小剩余组ρ1,ρ2,…,ρφ(n)也是这样的组，只是先后顺序有所变动〔命题8〕。把同余式ari≡ρi(modn),i=1,2,…,φ(n)逐项相乘，可得从等式两边约掉，得到ac≡1(modn),c=φ(n)推论〔Fermat定理〕设p为素数且(a,p)=1，那么ap-1≡1(modp)式中两边同乘以a，可得更简捷的形式，即ap≡a(modp)，它对任意的整数a都成立。1.8数论中特殊的函数及特殊的数1.8.1整数a的因子函数τ(a)

命题1设a∈Z+且a有标准因子分解式假设记a的全部因子为τ(a)，那么τ(a)=(α1+1)(α2+1)…(αk+1)。证明显见a的任一因子b必可写成如下形式：且每个βi(i=1,2,…,k)的取值都有0,1,2,…，αi这αi+1种可能之一。由于β1,β2,…,βk共有(α1+1)(α2+1)…(αk+1)种不同的取值组合，且每个组合都恰产生a的一个因子，故τ(a)=(α1+1)(α2+1)…(αk+1)。1.8.2整数a的因子的和函数σ(a)

命题2设a∈Z+，且a有标准因子分解式αi≥0(1≤i≤k)假设用σ(a)表示a的全部因子之和，那么证明对k施用归纳法。当k=1(a=p1α1)时，那么当设对k-1时有那么对k可得

例1设τ(a)=(α1+1)(α2+1)…(αk+1)=3，求a。

解因3为素数，故τ(a)的连乘表达式中只能有一个因式。所以τ(a)=α1+1=3，即α1=2。又因2是最小素数，所以应在a的标准分解式中取p1=2，从而a=p1α1=22=4，a的3个因子为1，2，4。当然，9也有3个因子1，3，9，但一般要求的是最小正数。例2假设τ(a)=(α1+1)(α2+1)=6，求a。解因α1,α2有两组解：α1=5,α2=0及α1=2,α2=1，它们分别对应a的两种不同分解形式：a=p51或a=p21p2。对后一形式，可得a=22·3=12，其5个因子分别为1,2,3,4,6,12;对前一形式，有a=25=32＞12，因此a=12。

例3对τ(a)=60，求a。

解因τ(a)=60=2·2·3·5，又由大到小α1=4,α2=2,α3=1,α4=1，故a的标准分解式为a=p41·p22·p3·p4，在10000以内满足条件的数共有3个，即24·32·5·7=5040,24·32·5·11=7920,24·32·5·13=9360其中以5040为最小。1.8.3Mobius（μ）函数设a∈Z+且a有标准因子分解式： ,αi≥0(1≤i≤k)，则..设a,b∈Z+，(a,b)=1，假设θ(ab)=θ(a)θ(b)，那么称θ为积性函数。对积性函数有命题3设a∈Z+，a的标准分解式为 ,则本命题说明τ,σ,φ,μ均为积性函数。积性函数有很重要的用途，即对某个a∈Z+,能利用其所有素因子幂的函数值求出该积性函数对a的函数值。1.8.4梅桑数〔MersenneNumbers〕法国数学家梅桑〔M.Mersenne,1588~1648〕猜测，当p为素数时，具有特殊形式Mp=2p-1的数是素数。确实，当p=2,3,5,7时，Mp是素数，但当p=11时，M11=211-1=23·89=2047却是个合数，这是梅桑在世时就知道的结论。为了纪念梅桑对2n-1(n∈N)形状的数所做的研究，常称其为梅桑数，并记为Mn。好几个世纪以来，人们一直在Mn中寻找素数，可是却发现这种素数越往后越稀疏。借助于计算机，20世纪80年代中期发现的最大的梅桑数Mp中，p已是216091。但对Mn有如下断言:命题4对Mn=2n-1，当n(n＞1)不是素数时，Mn必不为素数。证明假设n是偶合数,且n＞2,令n=2m，那么2n-1=22m-1=(2m-1)(2m+1)。当n为奇合数时，设n=pq，那么2pq-1=(2p-1)((2p)q-1+(2p)q-2+…+(2p)+1)。由此可见，当n＞1时，2n-1为素数的必要条件是n为素数。梅桑数中是否有无穷多个素数?这是一个尚未解决的问题。有人曾提出过新的猜测：当Mp是素数时，MMp也是素数。但对MM13=28191-1，有人已证明了它是合数。另一个涉及梅桑数的著名猜测是由卡塔朗提出的。卡塔朗观察到既然都是素数，于是他猜测一切形如Cn+1=2Cn-1的数都是素数。在目前，卡塔朗的猜测是无法验证的，因为光是C5的位数就已经多达1038位。1.8.5费尔马数（FermatNumbers）命题5若2p+1是素数，则n∈Z+，使p=2n。

证明只需证明p没有任何奇数真因子。采用反证法，设q为p的任一奇数真因子，则p=qt。于是2p+1=2qt+1=(2t+1)(2t(q-1)-…-2t+1)即2p+1有一因子2t+1，这导致2p+1不是素数，与前提矛盾。故 n∈Z+,使p=2n。费尔马猜想命题5的逆命题也成立，即当p=2n时，2p+1=22n+1是素数。后来,常把形如Fn=22n+1的数称为费尔马数。当n=0,1,2,3,4时，F0=3,F1=5,F2=17,F3=257,F4=65537都是素数。F5=4294967297已是一个十位数，费尔马的耐心有限，他深信不疑，不仅F是素数，而且所有的Fn都是素数。费尔马死后67年，另一位大数学家欧拉在1732年证明了当n＞2时，一切Fn如有因子，那么它们必具有形式k×2n+2+1，利用这一方法，他终于找出(640=5×27)F5=641×6700417从而否认了费尔马的猜测。1.8.6完全数〔PerfectNumber〕设a∈Z+，令σ(a)表示a的全部因子之和，假设σ(a)=2a，那么称a为完全数。公元2世纪末已算出的4个完全数是6，28，496，81281202年，Fibonacci给出了一个寻找完全数的规那么,即命题6。命题6当p与2p-1都是素数时，那么a=2p-1(2p-1)为完全数。证明迄今为止，已发现的完全数都是偶数，有无奇完全数存在还是未知数。数学家奥斯丁·欧尔〔OysteinOre〕已证明，如果确有奇完全数，那么其形状必定为12p+1或36p+9〔其中p为素数〕的形式。1018以下的自然数已被推查过，没有一个是奇完全数。1.8.7亲和数〔FriendSum〕设a,b∈Z+，σ(a)、σ(b)分别为a、b的因子之和，假设σ(a)-a=b∧σ(b)-b=a那么称a与b是一对亲和数。由σ(220)-220=284∧σ(284)-284=220可知，220与284是一对亲和数。又由σ(1210)-1210=1184∧σ(1184)-1184=1210可知,1210与1184是一对亲和数。费尔马给出的一对亲和数是17296与18416。欧拉1750年曾公布出60对亲和数，但其中却不包含1210与1184。命题7设m∈Z+∧n＞1，并设a,b,c可表示如下：a=3·2n-1，b=3·2n-1-1，c=9·22n-1-1当a,b,c都是素数时，2nab与2nc是一对亲和数。证明从略。在10000以内，亲和数分布的密度较大，这段区间内发现了13对。他们是：〔1〕220与284〔2〕1184与1210〔3〕2620与2924〔4〕5020与5564〔5〕6232与6368〔6〕10744与10856〔7〕12285与14595〔8〕17296与18416〔9〕63020与76084〔10〕66928与66992〔11〕67095与71145〔12〕69615与87633〔13〕79756与88730值得指出的是,(7)、(11)、(12)都是奇亲和数。一对亲和数可以都是偶数,也可以都是奇数，但却始终没有发现一奇一偶组成的亲和数。通过对30亿以下的自然数依次搜索,尚未发现一奇一偶的亲和数。亲和数可扩展为金兰数。假设a,b,c三数满足σ(a)-a=b+c,σ(b)-b=a+c,σ(c)-c=a+b可称a,b,c为金兰数a:123228768=25·3·13·293·337b:103340640=25·3·5·13·16561c:124015008=25·3·13·99371a′:214·3·5·19·31·89·151b′:214·5·19·29·31·151c′:214·5·19·31·151·3591.9同余式的一般性讨论定义1设 ，其中n＞0,ai∈Z，0≤i≤n。对m∈Z+,称f(x)≡0(modm)为模m的同余式。若m|an，称n是同余式的次数。若x0满足f(x0)≡0(modm)，则x∈x0(modm)称为同余式f(x)≡0(modm)式的解。注意：不同的解指不同余的解。又若x0是f(x)≡0(modm)的解，则模m的剩余类［x0］={x|x=x0+km,k∈Z}即剩余类中的每个x都满足同余式，而x0是［x0］中的最小非负整数，即非负的最小剩余。定理1设(a,m)=1,m＞0，那么一次同余式ax≡b(modm)恰有一个解x，且其为x≡baφ(m)-1(modm)证明因为0,1,2,…,m-1是模m的完全剩余组,(a,m)=1,故0,a,2a,…,(m-1)a也是模m的一个完全剩余组,所以其中恰有一整数,设为ak,满足ak≡b(modm),即x≡k(modm)是ax≡b(modm)的惟一解。又由Euler定理aφ(m)≡1(modm),从而aφ(m)-1(ax)=aφ(m)x≡baφ(m)-1(modm)，即x≡baφ(m)-1(modm)定理3设(a,m)=d,m＞0,d|b，那么ax≡b(modm)恰有d个解。证明由定理2知ax≡b(modm)有解。又x*为ax≡b(modm)的解，那么x*也是的惟一解。即!x*使从而对模m恰选出d个互不同余的整数使为ax≡b(modm)的不同的解。又若k1,k2(0≤k1,k2＜d)，使那么有k1=k2。定理4设n≥1,m＞0，同余式有解iff(a1,a2,…,an,m)|b。对n的归纳证明从略。

定理5（Largrange定理）设p为素数， 为整数多项式，an0(modp),则同余式f(x)≡0(modp)至多有n个解。对n的归纳证明从略。

推论1设同余式 的解的个数大于n，其中p是素数，则p|ak(0≤k≤n)。

证明对0≤k≤n，否定p|ak，即可引出与Largrange定理的矛盾。推论2对任给素数p，整数多项式f(x)=(x-1)(x-2)…(x-p+1)-xp-1+1的所有系数均能被p整除。证明令g(x)=(x-1)(x-2)…(x-p+1)，那么显见1，2，…,p-1是同余式g(x)≡0〔modp〕的p-1个解。又由Fermat定理知1，2，…,p-1也是同余式h(x)=xp-1-1≡0〔modp〕的p-1个解。故f(x)≡(g(x)-h(x))(modp)有p-1个解。但f(x)已是p-2次多项式。由推论1，其所有系数均能被p除尽。推论3〔威尔逊定理〕对素数p,(p-1)!≡-1(modp)。证明推论2中取x为0，那么f(0)=(-1)p-1(p-1)！+1，且所有系数均能被p除尽。故f(x)=(-1)p-1(p-1)！+1≡0〔modp〕，即有(p-1)！≡-1(modp)。关于n>1的同余式，仅限于考虑模为奇素数的根本形式x2≡a(modp),(p,a)=1定义2设p为素数，假设x2≡a(modp)有解，那么称a为模p的二次剩余〔或平方剩余〕；否那么，称a为模p的二次非剩余。假设a为二次剩余，那么模p同余类［a］中每个数均是二次剩余,对二次非剩余也是如此。定理6假设a是奇素数模p的二次剩余，那么x2≡a(modp)恰有2个解。证明事实上，因a为模p的平方剩余，那么x2≡a(modp)至少已有一个解x≡x0(modp)，又由于(-x0)2=x20，该同余式还有第二个不同的解x≡-x0(modp)。因假设x0≡-x0(modp)，将导致2x0≡0(modp)，而(2,p)=(x0,p)=1，与p|2x0矛盾。又由Largrang定理，二次剩余的解不多于2个。定理得证。定理7与模p互素的剩余组，由(p-1)/2个与数同余的平方剩余和(p-1)/2个平方非剩余组成。证明事实上，在与模p互素的剩余组中出现的平方剩余，是而且只是与数〔与模互素的剩余组〕的平方，即与11,22,…,［(p-1)/2］2同余的数，且两两不同。因假设有那么x有4个解(k,-k,l,-l),与定理6矛盾。定理8如果a是模p的平方剩余，那么a(p-1)/2≡1(modp)而如果a是模p的平方非剩余，那么a(p-1)/2≡-1(modp)证明由Fermat定理ap-1-1≡0(modp)有a(p-1)/2+1)(a(p-1)/2-1)≡0(modp)注意到a(p-1)/2+1与a(p-1)/2-1有且只能有一个被p除尽,又对任意的平方剩余a，总存在x，使满足同余式a≡x2(mod