9、u0且d
10、u1的充要条件是d
11、uk+1；（3）存在整数x0,x1，使uk+1=x0u0+x1u1.5．算术基本定理：若n>1且n为整数，则，其中pj(j=1,2,…,k)是质数（或称素数），且在不计次序的意义下，表示是唯一的。86．同余：设m≠0,若m
12、(a-b)，即a-b=km，则称a与b模同m同余，记为a≡b(modm)，也称b是a对模m的剩余。7．完全剩余系：一组数y1,y2,…,ys满足：对任意整数a有且仅有一个yj是a对模
13、m的剩余，即a≡yj(modm)，则y1,y2,…,ys称为模m的完全剩余系。8．Fermat小定理：若p为素数，p>a,(a,p)=1，则ap-1≡1(modp)，且对任意整数a,有ap≡a(modp).9．若(a,m)=1，则≡1(modm),(m)称欧拉函数。10．（欧拉函数值的计算公式）若，则(m)=11．（孙子定理）设m1,m2,…,mk是k个两两互质的正整数，则同余组：x≡b1(modm1),x≡b2(modm2),…,x≡bk(modmk)有唯一解，x≡M1b1+M2b2+…+Mkbk(modM)，其中M=m1m2mk；=，i=1,2,…,k；≡1(modmi),i=
14、1,2,…,k.二、方法与例题1．奇偶分析法。例1 有n个整数，它们的和为0，乘积为n，（n>1），求证：4
15、n。8[证明] 设这n个整数为a1,a2,…,an，则a1,a2,…,an=n， ①a1+a2+…+an=0。 ②首先n为偶数，否则a1,a2,…,an均为奇数，奇数个奇数的和应为奇数且不为0，与②矛盾，所以n为偶数。所以a1,a2,…,an中必有偶数，如果a1,a2,…,an中仅有一个偶数，则a1,a2,…,an中还有奇数个奇数，从而a1+a2+…+an也为奇数与②矛盾，所以a1,a2,…,an中必有至少2个偶数。所以4
16、n.2．不等分析法。例2 试求所有的正整数n
17、，使方程x3+y3+z3=nx2y2z2有正整数解。解 设x,y,z为其正整数解，不妨设x≤y≤z，则由题设z2
18、(x3+y3)，所以z2≤x3+y3，但x3≤xz2,y3≤yz2，因而z=nx2y2-≥nx2y2-(x+y)，故x3+y3≥z2≥[nx2y2-(x+y)]2，所以n2x4y4≤2nx2y2(x+y)+x3+y3，所以nxy<。若x≥2，则4≤nxy<≤3，矛盾。所以x=1，所以ny<，此式当且仅当y≤3时成立。又z2
19、(x3+y3)，即z2
20、(1+y3)，所以只有y=1,z=1或y=2,z=3，代入原方程得n=1或3。3．无穷递降法。例3 确定并证明方程a2+b2
21、+c2=a2b2的所有整数解。解 首先(a,b,c)=(0,0,0)是方程的整数解，下证该方程只有这一组整数解。假设(a1,b1,c1)是方程的另一组整数解，且a1,b1,c18不全为0，不妨设a1≥0,b1≥0,c1≥0且，由≡1或0(mod4)知a1,b1,c1都是偶数(否则(mod4))，从而是方程x2+y2+z2=2x2y2的一组整数解，且不全为0，同理可知也都是偶数为方程x2+y2+z2=24x2y2的解。这一过程可以无限进行下去，另一方面a1,b1,c1为有限的整数，必存在k∈N,使2k>a1,2k>b1,2k>c1，从而不是整数，矛盾。所以该方程仅有一组整数解(0,0
22、,0).4．特殊模法。例4 证明：存在无穷多个正整数，它们不能表示成少于10个奇数的平方和。[证明] 考虑形如n=72k+66,k∈N的正整数，若，其中xi为奇数，i=1,2,…,s且1≤s≤9。因为n≡2(mod8)，又≡1(mod8)，所以只有s=2.所以，又因为≡2或0(mod3)，且3
23、n，所以3
24、x1且3
25、x2，所以9
26、n。但n=72k+66≡3(mod9)，矛盾。所以n不能表示成少于10个奇数的平方和，且这样的n有无穷多个。5．最小数原理。例5 证明：方程
