▁▂▃▄▅▆▇█▉▊▋▌精诚凝聚 =^_^= 成就梦想 ▁▂▃▄▅▆▇█▉▊▋▌
第十七章 整数问题
一、常用定义定理
1．整除：设a,b∈Z,a≠0，如果存在q∈Z使得b=aq，那么称b可被a整除，记作a|b，且称b是a的倍数,a是b的约数。b不能被a整除，记作a b.
2.带余数除法：设a,b是两个给定的整数，a≠0，那么，一定存在唯一一对整数q与r，满足b=aq+r,0≤r<|a|，当r=0时a|b。
3．辗转相除法：设u0,u1是给定的两个整数，u1≠0，u1 u0,由2可得下面k+1个等式：u0=q0u1+u2,0 u1=q1u2+u3,0 uk-2=qk-2u1+uk-1+uk,0 4．由3可得：（1）uk+1=(u0,u1)；（2）d|u0且d|u1的充要条件是d|uk+1；（3）存在整数x 0,x1，使uk+1=x0u0+x1u1. 5．算术基本定理：若n>1且n为整数，则n?p11p22?pkk，其中pj(j=1,2,…,k)是质数（或称素数），且在不计次序的意义下，表示是唯一的。 6．同余：设m≠0,若m|(a-b)，即a-b=km，则称a与b模同m同余，记为a≡b(modm)，也称b是a对模m的剩余。 7．完全剩余系：一组数y1,y2,…,ys满足：对任意整数a有且仅有一个yj是a对模m的剩余，即a≡yj(modm)，则y1,y2,…,ys称为模m的完全剩余系。 p-1 8．Fermat小定理：若p为素数，p>a,(a,p)=1，则a≡1(modp)，且对任意整数a,有ap≡a(modp). 9．若(a,m)=1，则a?(m)≡1(modm),?(m)称欧拉函数。 10．（欧拉函数值的计算公式）若m?pp?p，则?(m)=ma11a22akkaaa?(1?i?1k1). pi11．（孙子定理）设m1,m2,…,mk是k个两两互质的正整数，则同余组： x≡b1(modm1),x≡b2(modm2),…,x≡bk(modmk)有唯一解， ''x≡M1'M1b1+M2M2b2+…+MkMkbk(modM)， 其中M=m1m2mk；Mi= M，i=1,2,…,k；Mi'Mi≡1(modmi),i=1,2,…,k. mi二、方法与例题 1．奇偶分析法。 例1 有n个整数，它们的和为0，乘积为n，（n>1），求证：4|n。 [证明] 设这n个整数为a1,a2,…,an，则a1,a2,…,an=n， ① ▃ ▄ ▅ ▆ ▇ █ █ ■ ▓点亮心灯 ~~~///(^v^)\\\\\\~~~ 照亮人生 ▃ ▄ ▅ ▆ ▇ █ █ ■ ▓ ▁▂▃▄▅▆▇█▉▊▋▌精诚凝聚 =^_^= 成就梦想 ▁▂▃▄▅▆▇█▉▊▋▌ 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|n. 2．不等分析法。 例2 试求所有的正整数n，使方程x3+y3+z3=nx2y2z2有正整数解。 解 设x,y,z为其正整数解，不妨设x≤y≤z，则由题设z2|(x3+y3)，所以z2≤x3+y3， x3?y322332222 但x≤xz,y≤yz，因而z=nxy-≥nxy-(x+y)，故x+y≥z≥[nxy-(x+y)]，2z3 2 3 2 2 2 所以nxy≤2nxy(x+y)+x+y，所以nxy<2??2 4 4 22 3 3 ?11?11?????nx3ny3。若x≥2，则4≤xy??nxy<2???11?11211≤3，矛盾。所以x=1，所以ny<，此式当且????2???333?ynnyny?xy?nx仅当y≤3时成立。又z2|(x3+y3)，即z2|(1+y3)，所以只有y=1,z=1或y=2,z=3，代入原方 程得n=1或3。 3．无穷递降法。 例3 确定并证明方程a2+b2+c2=a2b2的所有整数解。 解 首先(a,b,c)=(0,0,0)是方程的整数解，下证该方程只有这一组整数解。假设(a1,b1,c1)是方程的另一组整数解，且a1,b1,c1不全为0，不妨设a1≥0,b1≥0,c1≥0且 a12?b12?c12?0，由a12b12≡1或0(mod4)知a1,b1,c1都是偶数(否则a12?b12?c12a12b12(mod4))，从而(a1b1c1,,)是 方程x2+y2+z2=2x2y2的一组整数解，222且不全为0，同理可知 a1b1c1ab1c1,,也都是偶数(1,2,2)为方程x2+y2+z2=24x2y2的解。2222222这一过程可以无限进行下去，另一方面a1,b1,c1为有限的整数，必存在k∈N,使2k>a1,2k>b1,2k>c1，从而 a1b1c1,k,k不是整数，矛盾。所以该方程仅有一组整数解k222(0,0,0). 4．特殊模法。 例4 证明：存在无穷多个正整数，它们不能表示成少于10个奇数的平方和。 2[证明] 考虑形如n=72k+66,k∈N的正整数，若n?x12?x2???xs2，其中xi为奇 数，i=1,2,…,s且1≤s≤9。因为n≡2(mod8)，又xi2≡1(mod8)，所以只有s=2.所以 2，又因为xi2≡2或0(mod3)，且3|n，所以3|x1且3|x2，所以9|n。但n?x12?x2▃ ▄ ▅ ▆ ▇ █ █ ■ ▓点亮心灯 ~~~///(^v^)\\\\\\~~~ 照亮人生 ▃ ▄ ▅ ▆ ▇ █ █ ■ ▓ ▁▂▃▄▅▆▇█▉▊▋▌精诚凝聚 =^_^= 成就梦想 ▁▂▃▄▅▆▇█▉▊▋▌ n=72k+66≡3(mod9)，矛盾。所以n不能表示成少于10个奇数的平方和，且这样的n有无穷多个。 5．最小数原理。 442 例5 证明：方程x+y=z没有正整数解。 [证明] 假设原方程有一组正整数解(x0,y0,z0)，并且z0是所有正整数解z中最小的。 2222222因此，(x0，则x0=2ab,z0=a2+b2，其中(a,b)=1,a,b一奇一)?(y0)?z0?a2-b2,y022偶。假设a为偶数，b为奇数，那么x0?z0?0(mod4)，而x0?a2?b2?3(mod4)，矛2盾，所以a为奇数，b为偶数。于是，由x0?b2?a2得x0=p2-q2,b=2pq,a=p2+q2（这里2(p,q)=1,p>q>0,p,q为一奇一偶）。从而推得y0?2ab?4pq(p2?q2)，因为p,q,p2+q2 两两互质，因此它们必须都是某整数的平方，即p=r2,q=s2,p2+q2=t2，从而r4+s4=t2，即(r,s,t)也是原方程的解，且有t 6．整除的应用。 n3?1例6 求出所有的有序正整数数对(m,n)，使得是整数。 mn?1解 （1）若n=1,则 2是整数，所以m-1=1或2，所以(m,n)=(2,1),(3,1). m?1n3?1n3?1?22（2）若m=1,则，所以n-1=1或2，所以??n2?n?1?n?1n?1n?1(m,n)=(1,2),(1,3). m3n3?1?(m3n3?1)?m3(n3?1)m3?1（3）若m>1，n>1，因为是整数，所以也?mn?1mn?1mn?1是整数，所以m,n是对称的，不妨设m≥n， n3?1n3?n?n?11ⅰ）若m=n，则2为整数，所以n=2,m=2. ??n?2n?1n?1n?1n3?1ⅱ）若m>n，因为n+1≡1(modn),mn-1≡-1(modn)，所以≡-1(modn). mn?13 n3?1n3?1n3?11??n?, 所以存在k∈N，使kn-1=,又kn-1= mn?1n?1mn2?1n2?1n3?1n2?121?n?1?. 所以(k-1)n<1+,所以k=1，所以n=1=,所以m?mn?1n?1n?1n?1所以n-1=1或2，所以(m,n)=(5,3)或(5,2). 同理当m ▃ ▄ ▅ ▆ ▇ █ █ ■ ▓点亮心灯 ~~~///(^v^)\\\\\\~~~ 照亮人生 ▃ ▄ ▅ ▆ ▇ █ █ ■ ▓