第一讲__整数奇偶性及整除性

1、竞赛数学教程第一讲 整数奇偶性与整除性张小利 严卿初等数论代数几何组合初步目 录 数论是竞赛数学中最重要的一部分，特别是在1991年，IMO在中国举行，国际上戏称那一年为数论年，因为6道IMO试题中有5道与数论有关。数论的魅力在于它可以适合小孩到老头，只要有算术基础的人均可以研究数论在前几年还盛传广东的一位农民数学爱好者证明了哥德巴赫猜想，当然，这一谣言最终被澄清了。可是这也说明了最难的数论问题，适合于任何人去研究。初等数论最基础的理论在于整除，由它可以演化出许多数论定理。一 奇数、偶数的性质：(1) 奇数 奇数=偶数，偶数 偶数偶数，奇数 偶数奇数，偶数*偶数偶数，奇数*偶数偶数，奇数*奇数

2、奇数； 即任意多个偶数的和、差、积仍为偶数，奇数个奇数的和、差仍为奇数，偶数个奇数的和、差为偶数，奇数与偶数的和为奇数，和为偶数；(2) 奇数的平方都可以表示成8m+1的形式，偶数的平方可以表示为8m或8m+4的形式；(3) 若有限个整数之积为奇数，则其中每个整数都是奇数；若有限个整数之积为偶数，则这些整数中至少有一个是偶数；两个整数的和与差具有相同的奇偶性；偶数的平方根若是整数，它必为偶数。例1 n个整数a1,a2, ,an，其积等于n，其和等于0，试证明：4|n.证明：1）先证明n是偶数.（反证法反证法） 假设n为奇数，则由 ai=n，得ai是奇数（i=1,2，n），且 是奇数个奇数之和，

3、仍为奇数，这与题给 “其和=0”矛盾，故n为偶数.再证4|n. （反证法）假设4 | n，此时a1,a2, ,an中只可能有一个偶数. 不妨设a1是偶数，则a2, ,an都是奇数。此时剩下的n-1个数都是奇数，其和仍为奇数.因此 =a1+ =偶数+奇数=奇数0，与题设矛盾，则4|n. ni 1niia1niia1niia2习题3.1.1 证明不定方程x2+y2=1983无整数解.证明：1983是奇数，x2+y2=1983 x2,y2为一偶、一奇数，x2+y2是4的倍数+1.而1983是4的倍数+3，因此说明该方程无整数解. 习题3.1.2 求x2-y2=1990所有整数解.解：原方程化为 (x

4、+y)(x-y)=19901990是偶数，结合整数奇偶性质知x+y,x-y至少有一个偶数，再则，x+y，x-y的奇偶性相同， x+y，x-y都是偶数，因此，4| (x+y)(x-y). 但4 | 1990，因此该方程无整数解. 习题3.1.5 如果ab是奇数，那么满足a2+b2+c2=d2的正整数一定不存在.证明：题给ab是奇数，则a、b均为奇数. 因而a2+b2一定是4的倍数+2.不妨设a2+b2=4k+2若方程a2+b2+c2=d2成立，则有d2-c2=4k+2. 即4k+2=d2-c2=(d+c)(d-c).由于d+c与d-c的奇偶性相同， 当d+c与d-c同为奇数时，(d+c)(d-c

5、)为4k+1型； 当d+c与d-c同为偶数时，(d+c)(d-c)为4k型；均不能为4k+2型. 所以当ab是奇数时，一定不存在正整数使得a2+b2+c2=d2成立. 二 整除 在高中数学竞赛中如果不加特殊说明，我们所涉及的数都是整数，所采用的字母也表示整数。定义1：设a,b是给定的数，b0，若存在整数c，使得a=bc则称b整除a，记作b|a，并称b是a的一个约数(因子)，称a是b的一个倍数，如果不存在上述c，则称b不能整除a,记作 b | a.性质： (1)若b|c且c|a，则b|a(传递性质)； (2)若b|a且b|c，则b|(a c). 即为某一整数倍数的整数之集关于加、减运算封闭。若反

6、复运用这一性质，则对于任意的整数u,v有b|(au cv)。更一般地，若a|bi，则a| 其中ci Z，i=1，2，n.niiibc1性质： (3)若b|a，则或者a=0，或者|a|b|，因此若b|a且a|b，则a= b； (4)a,b互质，若a|c，b|c,则ab|c； (5)p是质数，若p|a1a2an，则p能整除a1a2an中的某一个；特别地，若p是质数，若p|an，则p|a； (6)(带余除法带余除法)设a,b为整数，b0，则存在整数q和r，使得a=bq+r，其中0rb，并且q和r由上述条件唯一确定；整数q被称为a被b除得的(不完全)商，数r称为a被b除得的余数。注意：r共有种可能的取

7、值：0,1，b-1. 若r=0，即为a被b整除的情形. (7)如果在等式 中取去某一项外，其余各项均被c整除，则这一项也被c整除； (8)n个连续整数中，有且只有一个是n的倍数； (9)任何n个连续的整数之积一定是n!的倍数. 特别地，三个连续的正整数之积能被6整除；mkkniiba11例2 证明： 被1001整除。100102000个 110)10()10)(110(1)10(110100136653666336673200102000个证明：所以103+1(=1001)整除 .100102000个例3 (IMO,1959)若n是正整数,则 是既约分数.314421nn:,0,( , )(

8、, ):(214,143)(71,143)(71,1)1.214.143abqrrba bb rnnnnnnn证明 由则得是既约分数延伸 对斐波那契数列1、1、2、3、5、8、13、21、，记a1=a2=1,an+1=an+an-1，求证：对 整数k和n，有 不可约.132nnnnakaaka证明：用数学归纳法证明. 当n=1时， (2k+1,3k+1)=(2k+1,k)=(1,k)=1；假设n时成立，即 不可约.当n+1时，有13122413kkakaaka11) 12() 1(nnnnakkakaak132nnnnakaaka21212413) 12() 1(nnnnnnnnakkakaa

9、kakaaka) 1( ,) 12() 12() 13( ,) 12(1111nnnnnnnnkaakakkaakakkaak此为n时情形，不可约.故对任意整数，原分式 不可约. 132nnnnakaaka例4（1992年“友谊杯”国际数学竞赛题）求最大自然数x，使得对每一个自然数y，x能整除7y+12y-1.解：当y=1时，7y+12y-1=18，因此x|18，从而x0，则(ma,mb)=m(a,b)；5）若(a,b)=d，则 ，因此两个不互素的整数，可以自然地产 生一对互素的整数；6）若(a,m)=1,(b,m)=1，则(ab,m)=1，也就是说，与一个固定整数互素的整数集关于乘法封闭.

10、并由此可以推出：若(a,b)=1，对于 k0有(ak,b)=1，进而有对 l0有(ak,bl)=1.7）设b|ac，若(b,c)=1，则b|a.1),(dbda 定义3:(最小公倍数)设a,b是两个非零整数，一个同时为a,b倍数的数称为它们的公倍数，a、b的公倍数有无穷多个，这其中最小的一个称为a、b的最小公倍数，记作a,b. 对于多个非零实数a,b,c，可类似地定义它们的最小公倍数a,b,c.最小公倍数主要有以下几条性质： 1）a与b的任一公倍数都是a,b的倍数，对于多于两个数的情形，类似结论也成立； 2）两个整数a,b的最大公约数与最小公倍数满足：(a,b)a,b=|ab|(但请注意，这只

11、限于两个整数的情形，对于多于两个整数的情形，类似结论不成立)； 3）若a,b,c两两互素，则a,b,cabc； 4）若a|d，b|d,，c|d且两两互素，则abcd.例例5（1972年第6届全苏数学奥林匹克题）（1）设a,m,n是自然数，a1证明：如果 能被an+1整除，那么m能被n整除（2）设a,b,m,n是自然数，同时a、b互素，且a1证明：如果am+bm能被an+bn整除，那么m能被n整除证明：注意到（1）是（2）的特例，即（2）中b=1的情形，所以我们只证明（2）首先证明如下两个引理：引理1：若an+bn |ak+bk,(a,b)=1，则an+bn |ak-n - bk-n引理2：若a

12、n+bn |al-bl,(a,b)=1，则an+bn |al-n + bl-n 这两个引理容易由以及下面的两个恒等式得到：1ma)()(nknknnnnkkkbabbaaba()().lll nnnnl nl nabaabbab设m=nq+r，0r0时，有若b=1，则设u=a+8，则 由u|u2-15u+57，得u|57， 于是u=19或57，得a=11或49.227|7.abbab22(7).a babk abb 222 277 ,7,7 ,1 2a b a b ba a b bb 知 或28|1.aaa2221(8)(8)11559.aauuuu 即得到两组解（a,b）=（11,1）或（4

13、9,1） 若b=2，则 由于 ，只可能7a-4=4a+9，此时a= ，舍去. 不等式对正整数a不成立 综 上，全部正整数对（a，b）=(7k2,7k)，（11,1），（49,1），k N+ .49|74.aa49742(49)aaa313链接链接 习题3.1.6 设n是正整数，求证n5-n可被30整除.例8 （1973年基辅数学奥林匹克题）设 是自然数，它们的和能被30整除证明 能被30整除证明：对 a N+，首先证明30|a5-a.由于 是连续五个整数，它们的乘积能被5！=120整除，因而能被30整除 是连续三个整数，它们的乘积能被3！=6整除，因而能被30整除 于是30|a5-a. 从而

14、又由已知 ，所以 12,na aa55512naaa5222(1)(1)(1) (1)(45)aaa aaaa aa(2)(1) (1)(2)5(1) (1).aaa aaaa a2,1, ,1,2aaa aa1,1aa a5511130|().nnniiiiiiiaaaa130|niia5130 |niia习题3.1.7 一个八位数19 abc d83能被1983整除，求这个八位数.解：记该八位数为x，则 x=19abcd83=19000083+ =19839581+960+ =19839581+10(96+ ).由于1983|x，（1983,10）=1，则1983|即 96+ =1983k

15、， =1983k-96 .显然，上式左边个位为0，则结合右边1983k-96知：k的个位数必为2. 而 最大值只可能为99990，即：1983k-9699990,k50.因此，k只能取值2,12,22,32,42.此时对应的 为：0387,2370,4353,6336,8319.故该八位数为：19 038 783,19 237 083,19 435 383,19 633 683,19 831 983.100abcd100abcd10abcd10abcd10abcd10abcd10abcdabcd习题3.1.8 设p和q均为正整数，使得 ，证明p可被1979整除.（IMO，1979）证明：1319113181-31211qp）（1318141212-131911318131211qp)6591211 (131911318131211)99019891()131916611()131916601(131911318166116601，99098919791318661197913196601979等式两边同时乘以1319！，得：即1979是素数，（1979,1319!）=1，1979|p. p1319|1979