竞赛数学(张同君陈传理)数论2(同余)

数论同余同余1,,,|,,,(mod),.|mabmababmabmabmm定义：设是大于的正整数是整数如果则称关于模同余记作读作同余模当,,,ababma则称关于模不同余记作(mod).bm同余的性质10(mod),|.2(mod),,.ammaabmabm则分别用除余数相同例题1,,,24.abcabababbcbcbccacaca例：设、、是三个整数证明下面三个数中至少有一个是的倍数,,.24|.24833,81,3|8|.1,3,3|;,3,,31,2.mod3,3|,3|abcabababababababababababababababababab因为、、均为整数则必有两个数奇偶性相同不妨设、奇偶性相同下面证明因为且因此只须证明且若中至少有一个是的倍数时则有若均不是的倍数则是用除余数为当则从而;abababa当mod3,3|,3|.,3|.babababababababab则从而因此，对任意整数均有2,,8|;,,,,4,1,3.mod4,4|;ababababababababababa当均为偶数时显然当均为奇数时显然均为偶数且用除余数为当则当mod4,4|,8|.,,24|,,,24.babababababababababababbcbcbccacaca则所以综上所述，当奇偶性相同时即三个数中至少有一个是的倍数同余的性质1,,,1,1mod;2mod,mod;3,mod,mod.abcmmaamabmbamabbcmacm定理：同余是一个等价概念，即设是整数则有反身性：对称性：传递性：同余的性质1122121212122mod,mod,1mod,2mod.abmabmaabbmaabbm定理：设则同余的性质11111mod,1,2,,,1mod,2mod.2mod,mod.kknnkkkknnkkkknnabmknabmabmabmabm推论：若则推论：若则例题99399129939911984.例：证明能被整除993993991229939919919919911984993991,993991mod1984991991,99198208149519841,9939919914951984991991故99199199399109919910mod1984,1984|993991.所以例题444121431599xxx例：求证不定方程无整数解。12144441599160011mod1615mod16.,,,.2,160mod16.21,2iiiiXxxxxnxnxnx设是方程的整数解若则若则4432434441214444121411632248116283111mod16.14mod16,1599nnnnnnnnnxxxaxxx显然与15mod16.,.矛盾因此此方程无整数解例题4217.nn例：求使为的倍数的所有正整数3333133113,21mod7,21mod7,210mod7,3,217.231,222122mod7,21211mod7,31,217.332,mmnmmmnnmnmnmnmnm当时有故即所以，当时是的倍数当时即所以，当时不是的倍数当时323232222144mod7,21413mod7,32,217.,3.mmmnnmn即所以，当时不是的倍数因此满足条件的是所有的倍数的正整数例题5,19817.nn例：证明对任意非负整数是合数19817.,.,.0,1981736,3|;1,19817169,13|;2,198171233,3|;3,198179745,5|;nnnnnAnAnAnnnAnAnnAnAnnAnAnnAnAn分析：令要证明是合数就要考虑能被哪个素数整除为此可以从简单的素数进行实验当时当时当时当时4,1981777841,3|;5,19817622609,13|.0,1,2,3,4,5,.3,13,3,5,3,13.:,3|;41,13|;43,5|..nnnAnAnnAnAnnAnnAnnkAnnkAn当时当时由此可以看出：当时有素约数依次为于是可以猜测当是偶数时当是时当是时下面证明我们的猜测是正确的2224119817.2,19817198171886417188631170120mod3,3|.2,.41,19817198171nnkkkkknkAnnkAnAnnkAnnkAn令当时所以即当时是合数当时41441442414238688134138398139841383981396514000914mod13kkkkkkkkk0mod13,13|.41,.AnnkAn所以即当时是合数434343243343,19817198172088172088651152021020mod5,5|.nkkkkknkAnAnn当时所以即当43,.,,19817.nkAnn时是合数综上所述对任意非负整数是合数同余的性质1212222113mod,mod,,1,mod.mod,,1,mod.aabbmabmamabmacbcmmcabm定理：若且则推论：若且则例题1414714.例：求的末尾两位数1414141414,,,mod100,100425,140mod4,AAaAaA令欲求的末尾两位数即求使得由于则①236510141061066141964mod25,1446414mod25,14,251,141mod25,141mod25.14106,:1414141141411mod25,ttttA由于所以则又因为从而得到即11mod25.,2511,25110mod4,30mod4,1mod4,,41,,25411110036.AAyyyyykAkk②由②得代入①得从而有于是所以1414,1436.的末尾两位数是例题444484444,,?AABB例：的十进位数的数字之和是的数字和是的数字和是多少444444444444.,444410000,444444444120000.9,,920000180000199999,199999199999.46.12.1246BCAABBC设的数字和是显然所以的位数不超过因为每一个数字都不大于所以而的数字和总比小于的数的数字和大则的数字和于是，的数字和这是因为是小于的正整数中最大的数字4444148144444444314813912.9.4444mod9,444422221ABCC和的数字和是由于一个正整数与其数字和关于模同余于是所以27mod9.12,779.7.7.CCB因为在的正整数中只有本身才能与模同余所以这就是说的数字和是同余的性质12124mod,,,|,mod.5mod,mod,mod,,,,,nnabmabddmabmdddabmabmabmMmmm定理：若且则定理：若且则mod.abM剩余类,,0,1,2,,1.,,,.0,|mod,.rrrmmmmmrrmkkxxrmkm定义：设是正整数以为模则任何整数必与之一同余把同余数归为一类不同余数的整数必不在同一类则全体整数可分为类称每一类为模的剩余类余数为的剩余类记作是一个以为公差的等差数列剩余类的性质0011001;2;3,01,;4,,mod.mijrrZkkkkk