《数学竞赛》第三章-数论2012.2

第二篇竞赛数学的主要内容第三章数论§3．1整数的奇偶性和整除性§3．2同余§3．3不定方程§3．4高斯函数[x]2020/9/7第三章数论2第三章数论3．1整数的奇偶性和整除性一、整数的奇偶性1、偶数+偶数=偶数；奇数+奇数=偶数；奇数+偶数=奇数2、a,b为整数，若a±b为偶数，则a,b的奇偶性相同；若a±b为奇数，则a,b的奇偶性相反。3、奇数个奇数之和是奇数；偶数个奇数之和是偶数。4、奇数×奇数=奇数；偶数×偶数=偶数；奇数×偶数=偶数性质2020/9/7第三章数论3第三章数论3．1整数的奇偶性和整除性一、整数的奇偶性5、任意n个奇数的积仍是奇数，奇数的n次幂是奇数。若n个数的积为奇数，则这n个数均为奇数。6、若任意有限个整数中至少有一个偶数，那么它们的积是偶数；反之，任意有限个整数之积是偶数，则这些因数中至少有一个偶数。7、若a,b为整数，则a+b与a-b奇偶性相同性质2020/9/7第三章数论4第三章数论3．1整数的奇偶性和整除性一、整数的奇偶性例1.在1,2,3,⋯,1999这1999个数的前面任意添上正号或负号,问它们的代数和是奇数还是偶数?例2.设a1,a2,⋯,an是自然数1,2,⋯,n的一个排列,若n为奇数,求证:(a1-1)(a2-2)⋯(an-n)为偶数。例题2020/9/7第三章数论5第三章数论3．1整数的奇偶性和整除性一、整数的奇偶性例题例3.设n个整数a1,a2,⋯,an的积等于n，其和为0.证明：4|n.例4.设n个数x1,x2,⋯,xn,它们中的每一个要么是1，要么是-1.若x1x2+x2x3+⋯+xn-1xn+xnx1=0.证明：4|n.2020/9/7第三章数论6二、整数的整除性3．1整数的奇偶性和整除性1.整除的定义：对于两个整数a、b(b≠0），若存在一个整数c，使得a=bc①成立，则称b整除a，或a被b整除，记作b|a。a叫做b的倍数，b叫做a的约数（因数）。若满足①的整数c不存在，就称a不能被b整除，或b不能整除a，记作b∤a，如2|6，4∤6。定义2020/9/7第三章数论72、整除的性质3．1整数的奇偶性和整除性性质1a,b,c为整数，1）a|a;2）若c|b，b|a，则c|a;（传递性）3）若a|b，a|c，则a|（ma+nb），m、n为任意整数.性质2等式中除某一项外，其他所有项都能被m整除，则这一项也能被m整除。性质31)若a|bm，且（a，b）=1，则a|m；2)若a|m，b|m，且（a，b）=1，则ab|m；3)若p为质数，且p|ab，则p|a，或p|b。性质二、整数的整除性2020/9/7第三章数论83．1整数的奇偶性和整除性连续整数之积的性质①任意两个连续整数之积必定是一个奇数与一个偶数之一积，因此一定可被2整除。②任意三个连续整数之中至少有一个偶数且至少有一个是3的倍数，所以它们之积一定可以被2整除，也可被3整除，所以也可以被2×3=6整除。这个性质可以推广到任意个整数连续之积。二、整数的整除性2、整除的性质性质2020/9/7第三章数论93．1整数的奇偶性和整除性例10.设p是大于5的素数，求证：240|p4-1.例11.p≥5是素数，且2p+1也是素数，证明：4p+1必是合数。例题二、整数的整除性2020/9/7第三章数论103．1整数的奇偶性和整除性1.证明：不定方程x2+y2=1983无整数解.3.能否找到10个奇数，使它们的倒数和等于1？练习二、整数的整除性4.方程ax2+bx+c=0，其中a、b、c都是奇数，证明此方程无整数解.作业2020/9/7第三章数论11第三章数论3．2同余一、同余的定义和性质定义定义1.设，若，则称和对模同余，记作a≡b(modm)；若不然，则称和对模不同余，记作a≢b(modm)例如：，等等。2020/9/7第三章数论123．2同余一、同余的定义和性质性质性质（1）（反身性）；（2）（对称性）若，则；（3）（传递性）若，，则；（4）（同余式相加）若，，则；（5）（同余式相乘）若，，则；2020/9/7第三章数论133．2同余一、同余的定义和性质性质反复利用（4）（5），可以对多个（模相同的）同余式建立加、减和乘法的运算公式。特别地，由（5）易推出：若)(modmba，则)(modmbann；但是同余式的消去律一般并不成立，即从未必能推出。正确的结果是：（6）若，则)),((modcmmba，由此可以推出：若则有。即在与互素时，可以在原同余式两边约去（不改变模）。2020/9/7第三章数论143．2同余一、同余的定义和性质性质（7）若(mod)abm，d｜m，则(mod)abd；（8）若(mod)abm，d≠0，则(mod)dadbdm；反之也成立，即有(mod)dadbdm⇒(mod)abm（9）若),,2,1)((modnimbai，则，特别地，若nmmm,,,21两两互素时，则有；2020/9/7第三章数论153．2同余一、同余的定义和性质例题例1.今天是星期四，则101000天后是星期几？例2.证明：993993+991991能被1984整除.练习习题3.21.n为任意正整数，证明：A=2034n+846n-1917n-963n能被1989整除.2020/9/7第三章数论163．2同余一、同余的定义和性质例题例3.求证：x14+x24+x34+…+x144=1599无整数解.练习1.（1898年匈牙利奥林匹克竞赛题）求使2n+1能被3整除的一切自然数n.2.求证31980+41981能被5整除.2020/9/7第三章数论173．2同余二、剩余类、完全剩余系、费马小定理性质定理3（费马小定理）设p是素数，且(a,p)=1，那么ap-1≡１（modp）.更一般地,设p是素数,对任意整数a,有ap≡a(modp).例题例9.求20032005被17除的余数.习题3.25.求19992000被29除的余数.练习例13.设a为正整数，且17∤a，求证：a8-1与a8+1中有且仅有一个能被17整除.2020/9/7第三章数论18第三章数论3．3不定方程历史不定方程是数论中最古老的分支之一。古希腊的丢番图（Diophantus）早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程.中国是研究不定方程最早的国家.公元5世纪的《张丘建算经》中的百鸡问题标志中国对不定方程理论有了系统研究.秦九韶的大衍求一术将不定方程与同余理论联系起来.百鸡问题说：“鸡翁一，直钱五，鸡母一，直钱三，鸡雏三，直钱一.百钱买百鸡，问鸡翁、母、雏各几何？”.费马（Fermat）大定理（当n＞2时，xn＋yn＝zn没有非平凡的整数解），历经300余年，已由英国数学家安德鲁·维尔斯（A.Wiles）证明。丢番图数书九章——大衍类2020/9/7第三章数论193．3不定方程定义一、一次不定方程定义.形如cbyax(,,,,Zcbaba,不同时为零)的方程称为二元一次不定方程。定理定理1.二元一次不定方程cbyax有解的充要条件是cba|),(.定理2.若1),(ba，且00,yx为cbyax的一个解，则方程的一切解都可以表示成00xxbtyyatt(为任意整数)。2020/9/7第三章数论203．3不定方程解法一、一次不定方程1.观察法2.逐步取整法例题例.求4x-3y=10的整数解.定理2.若1),(ba，且00,yx为cbyax的一个解，则方程的一切解都可以表示成00xxbtyyatt(为任意整数)。例1.求37x+107y=5的整数解.2020/9/7第三章数论213．3不定方程解法一、一次不定方程1.观察法2.逐步取整法例题例2.求不定方程25x+13y+7z=4的整数解.多元一次不定方程2020/9/7第三章数论223．3不定方程二、高次不定方程1.分解因式（因数）2.估计方法3.同余方法例题例3.求不定方程x2y+2x2-3y-7=0的整数解.例6.求不定方程x3+y3=1072的正整数解.2020/9/7第三章数论233．3不定方程二、高次不定方程1.分解因式（因数）2.估计方法3.同余方法例题例8.求所有正整数m，n，使得1！+2！+…+m!=n2.习题3.34.求不定方程3x2-4xy+3y2=35的正整数解.5.求不定方程x2+xy+2y2=29的整数解.练习2020/9/7第三章数论24第三章数论3．4高斯函数[x]定义对任意实数][,xx是不超过x的最大整数，称][x为x的整数部分.][xy的定义域为R，值域为Z；小数部分函数].[}{},{xxxxy定义域为R，值域为)1,0[性质性质1对任意实数x，有1}{0},{][xxxx且.性质2对任意实数x，有1[][]1xxxx.性质3若21xx则][][21xx.性质4}{}{];[][xnxxnnx.其中NnRx,.性质5[][][];{}{}{},(,)xyxyxyxyxyR2020/9/7第三章数论253．4高斯函数[x]性质性质6若x，y0，有][][][yxxy.性质7]][[][nxnx，其中NnRx,.性质9NnRx,，在1至x之间的整数中，有][nx个是n的倍数.性质10在n！中，质数p的次数是.][][][)!(32pnpnpnnp2020/9/7第三章数论263．4高斯函数[x]例题例1.分解30！为质因数乘积.例2.求1995！中末尾0的个数.例3求1111[1]1!2!3!1995!.2020/9/7第三章数论273．4高斯函数[x]习题3.42.从992到1992的整数中，有多少个数是7的倍数？如果7|9929931992k，求最大正整数k.练习3.求[617122].7.求证：(1)!(!)|(!)!nnn.习题3.41.求2000！末尾0的个数.作业