同余理论及其应用东北育才学校 费振鹏基础知识一、定义定义1：整数集Z 根据模正整数()1m m >来分类：若a 、b 被m 除的余数相同，则a 与b 属于同一类，否则不属于同一类．这样得到m 个类，即{}|Z,0,1,2,1i M i km k i m =+∈=- ．称之为模m 的剩余类（同余类）．定义2：若整数a 、b 之差被正整数m 整除，称a 、b 关于模m 同余，记作()mod a b m ≡．即()()m o d a b m m a b ≡⇔-．从字面上理解，所属模m的同一个剩余类的两个整数模m 同余．定义3：在模m 的m 个剩余类中各取一个整数作为代表，这些代表的集合称为模m 的完全剩余系．简称完系．定义4：绝对值不超过2m ⎡⎤⎢⎥⎣⎦的模m 的完系称为模m 的绝对最小完系．将0,1,2,,1m - 称为模m的最小非负完系．定义5：当模m 的某一剩余类i M 中某一整数与m 互质，由欧氏除法（辗转相除法）知i M 中每个数与m 均互质，则称此剩余类是模m 的缩剩余类（亦称简化剩余类）．定义6：设m 为正整数，从1到m 的整数中与m 互质的整数的个数用()m ϕ表示，称()m ϕ为欧拉函数．模m 的缩剩余类（简化剩余类）也是()m ϕ个．定义7：在模m 的()m ϕ个缩剩余类（简化剩余类）中各取一个整数作为代表，这些代表的集合称为模m 的缩剩余系（简化剩余系），简称缩系（简系）．定义8：满足()1mod k a m ≡的最小正整数k 称为整数a 模m 的指数（阶）． 二、定理定理1：同余的基本性质： ⑴()mod a a m ≡；⑵若()mod a b m ≡，则()mod b a m ≡；⑶若()mod a b m ≡，()mod b c m ≡，则()mod a c m ≡；⑷若()mod a b m ≡，m qn =，N n ∈，则()mod a b n ≡． 定理2：若()11mod a b m ≡，()22mod a b m ≡，则⑴()1212mod a a b b m +≡+；⑵()1212mod a a b b m -≡-；⑶()1212mod a a b b m ≡． 推论：⑴若()()mod 1,2,,i i a b m i n ≡= ，则()11m od nn i ii i a b m ==≡∑∑；()11mod nniii i ab m ==≡∏∏．⑵若()mod a b m ≡，n 为任意正整数，则()mod na nb m ≡；()mod n n a b m ≡． 定理3：若()mod ac bc m ≡，则()m od,m a b c m ⎛⎫≡ ⎪⎝⎭． 推论：若(),1c m =，()mod ac bc m ≡，则()mod a b m ≡． 定理4：若()mod a b m ≡，则()(),,a m b m =．定理5：若()mod i a b m ≡，1,2,,i k = ，则[]()12mod ,,,k a b m m m ≡ ．定理6：设f 是()N m +∈的正约数，在模f 的属于c 的剩余类中取整数,,,1mc c f c f f ⎛⎫++- ⎪⎝⎭，则它们是模m 的mf个剩余类．定理7：m 个整数12,,,m a a a 是模m 的完系的充要条件是12,,,m a a a 关于模m 两两不同余． 定理8：若(),1k m =，其中*Z k ∈（*Z 表示非零整数集），Z b ∈，+N m ∈，1m >且12,,,m x x x 是模m 的完系，则12,,,m kx b kx b kx b +++ 也是模m 的完系．定理9：（裴蜀定理）设a ，b ，d 是整数，则(),a b d =的充要条件是d a ，d b ，且存在整数u ，v 使得ua vb d +=．推论：⑴(),1a b =的充要条件是存在整数u ，v 使得1ua vb +=．⑵a ，b 均为正整数，(),1a b =的充要条件是存在正整数u ，v 使得1ua vb -=． 定理10：（费马小定理）若a 是整数，p 是质数且(),1a p =，则()11mod p a p -≡． 推论：若p 是质数，则()mod p a a p ≡．这里不要求a 、p 互质．定理11：()m ϕ个整数是模m 的简系的充要条件是它们均与m 互质且模m 两两互不同余． 定理12：设()12,,,m a a a ϕ 是模m 的简系，且(),1c m =，则()12,,,m ca ca ca ϕ 也是模m 的简系．定理13：（欧拉定理）若a 是整数，正整数1m >且(),1a m =，则()()1mod m a m ϕ≡． 定理14：欧拉函数的性质： ⑴若整数2m >，则()m ϕ是偶数．⑵设1iki i m p α==∏是m 的标准分解式，则()111kii m m pϕ=⎛⎫=⋅- ⎪⎝⎭∏．⑶若正整数m 、n 满足(),1m n =，则()()()mn m n ϕϕϕ=． ⑷()d md m ϕ=∑，其中d m∑表示d 遍历m 的所有正约数．定理15：（威尔逊定理）若p 是质数，则()()1!1mod p p -≡-．典型例题一、选取适当的模例1.求最大的正整数n ，使得方程组()()()()222222221212k nx y x y x k y x n y ++=++==++==++有整数解()12,,,,n x y y y ． （2003年越南数学奥林匹克）分析：我们利用平方数的性质处理问题． 解：所求最大正整数3n =．当3n =时，()()()222222123123x y x y x y ++=++=++．进而得2212222323,2 5.y y x y y x ⎧-=+⎪⎨-=+⎪⎩ 易得所给方程组有整数解()()123,,,2,0,1,0x y y y =-．当4=n 时，22122223223423,25,27.y y x y y x y y x ⎧-=+⎪-=+⎨⎪-=+⎩则1y ，2y ，3y ，4y 奇偶交替出现．从而()()22221322*y y y -+=且()()22232422**y y y -+=．若1y ，3y 为奇数，则由2y 是偶数得()2220mod 8y ≡，而由()222213224mod 8y y y =++≡． 即得出式()*矛盾．若1y ，3y 为偶数，则2y ，4y 为奇数．同理可得出式()**矛盾．所以4=n 无解．而当4n ≥时显然无解． 综上可得所求最大正整数3n =． 例2.已知11a =，22a =，{12153,,n n n n n a a a a a +++-=-11n n n n a a a a ++⋅⋅,.若为偶数若为奇数证明：对一切正整数n ，0n a ≠． （1988年全国高中数学联赛二试）分析：我们只要证明n a 模某一常数不为0即可．证明：若某一个0k a =，则对任意正整数m 有()0mod k a m ≡，因此，我们只要找到一个m ，对任何一个n 均有()0mod k a m ≡/即可．先通过计算前几项：11a =，22a =，37a =，429a =，522a =，623a =，…模3的余数分别为1，2，1，2，1，2，…于是猜想奇数项模3余1，偶数项模3余2． 即()211mod 3n a -≡，()22mod 3n a ≡，其中*n ∈ ．下面用数学归纳法证明这一猜想： 当1n =时，()111mod 3a =≡，()222mod 3a =≡，结论成立； 假设当n k =时，结论成立，即()211mod 3k a -≡，()22mod 3k a ≡．则不管()21221253241mod 3k k k k a a a a +-=-≡≡≡，还是()21221211mod 3k k k a a a +-=-≡-≡，均有()211mod 3k a +≡．进而不管()22212215322m o d 3k k k k a a a a +++=-≡≡，还是()22212122m o d 3k k k a a a ++=-≡-≡，均有()222mod 3k a +≡． 综上所述，猜想结论成立． 因此，原命题结论成立． 注：本题有如下加强命题：⑴此数列所有项都不是3的倍数；（根据上面的证明，容易得出这个结论） ⑵此数列所有项都不是4的倍数；⑶此数列为模3的模周期数列；（根据上面的证明，容易得出这个结论）⑷此数列为模4的模周期数列（模4的结果为1，2，3，…，据此也可证明加强命题⑵）．()11mod 4a ≡，()22mod 4a ≡，()33mod 4a ≡．设n k =时，()321mod 4k a -≡，()312mod 4k a -≡，()33mod 4k a ≡．则1n k =+时，()31331531mod 4k k k a a a +-=-≡，()323132mod 4k k k a a a ++=-≡，()333231533mod 4k k k a a a +++=-≡． 因此对一切n 均有()0m od 4k a ≡/，从而原命题成立．评注：选择适当的模结合相关知识，如平方数性质、模周斯数列是解决同余问题的技巧之一． 二、不定方程例3.证明：方程243y x x =+没有正整数解． （2004年韩国数学奥林匹克）分析：我们选择适当的模对x 进行分类处理问题． 证明：⑴当()1m od 3x ≡时，设()31N x a a =+∈，()42mod 3x x +≡． 而方程左边()230mod 3y ≡，矛盾． 所以此时无解． ⑵当()0mod 3x ≡时，设()*3N x a a =∈，()()()()4222113319313x x x x x x a a a a y +=+-+=+-+=． ∴()()2231931a a a a y +-+=．而(),311a a +=，()2,9311a a a -+=，()()231,93131,31a a a a +-+=+=， ∴a ，31a +，2931a a -+均为完全平方数．但由()()222319313a a a a -<-+<知2931a a -+不可能是完全平方数． 所以此时无解． ⑶当()1mod 3x ≡-时，设()*31N x a a =-∈时，()()()()4222119313313x x x x x x a a a a y +=+-+=--+=． ∴23|3|y y ⇒．令()*3N y c c =∈，则()()22313313a a a a c --+=． ∴3|a ．令()*3N a b b =∈，则()()22912791b b b b c --+=． 与⑵类似，b ，91b -，22791b b -+均为完全平方数．其中()912mod 3b -≡不可能是完全平方数，矛盾．所以此时无解．综上所述，原方程无正整数解．评注：方程右边可因式分解，而左边系数为3，因而选择模3对x 进行分类处理． 例4.x 、y 是质数，解方程219y x x y xy -=-． （2004年巴尔干地区数学奥林匹克） 分析：我们要充分利用x 、y 是质数的条件． 解：（Ⅰ）若x y =，则219xy =．显然不可能． （Ⅱ）若x y ≠，则219x y y x xy -+=．而x 、y 是质数，由费马小定理，得()mod y x x y ≡．∴2(m od )x y y x xy x y -+≡-．即19(mod )x y ≡-．∴|19y x +① 由费马小定理，得(m od )x y y x ≡．∴2(m od )x y y x xy y x -+≡．即19(mod )y x ≡．∴|19x y -②．⑴若19y >，则由①知19y x ≤+，由②知19x y ≤-即19y x ≥+．∴19y x =+．又y 是质数且2y >，故y 是奇质数．从而2x =，21y =不是质数．矛盾．所以此时无解． ⑵若19y =，则由①知19|x ．故19y x ==．这与（Ⅰ）矛盾．⑶若19y <，则由①、②，得{|19,|19.y x x x +- 当17y =时，由|19x y -，得质数2x =．不满足|19y x +． 当13y =时，由|19x y -，得质数2x =或3．不满足|19y x +． 当11y =时，由|19x y -，得质数2x =．不满足|19y x +．当7y =时，由|19x y -，得质数2x =或3．仅有()(),2,7x y =满足|19y x +，且满足原方程． 当5y =时，由|19x y -，得质数2x =或7．不满足|19y x +．当3y =时，由|19x y -，得质数2x =．()(),2,3x y =满足|19y x +，且满足原方程． 综上，()()(),2,7,2,3x y =为所求方程的解．评注：在处理有关质数幂的问题中，费马小定理常发挥重要作用．例5.设n 是整数，求证：若2+（2007年英国数学奥林匹克）证明：由2Z +，Z n ∈，得2112n +是完全平方数． 设()22112N n m m ++=∈，则()()21112m m n +-=． 又1m +、1m -奇偶性相同，故1m +、1m -均为偶数． 则211322m m n +-⋅=．记12m t +=，则112m t -=-，其中N t +∈．故()()213*t t n -=．要证222m +=+是完全平方数，只需证t 是完全平方数． 根据()*知，3t 或31t -，而()gcd ,11t t -=．若3t ，则由()gcd ,113t t -=，且()213t t n ⋅-=，知3t 与1t -都是完全平方数．设23t k =，则23t k =，()21311mod 3t k -=-≡-不可能是完全平方数．矛盾．因此，31t -．从而由()1gcd ,13t t -=，213t t n -⋅=，知t 与13t -都是完全平方数．综上，原结论成立．注：还可利用佩尔方程理论解决这个问题． 三、完系、费马小定理及其它相关定理例6.证明：对每个正整数n 存在一个各位数字均为奇数的n 位数能被5n 整除． （2003年第32届美国数学奥林匹克）证明：用数学归纳法．当1n =时，结论显然成立．假设12n N a a a = 能被5n 整除且各位数字都是奇数．考虑下列数：()11211105512nnnnn N a a a M M==⋅+=⋅+ ； ()21233105532nnnnn N a a a M M ==⋅+=⋅+ ； ()31255105552nnn nn N a a a M M ==⋅+=⋅+ ； ()41277105572nnnnn N a a a M M ==⋅+=⋅+ ； ()51299105592nnn nn N a a a M M==⋅+=⋅+ ．而数12,32,52,72,92n n n n n M M M M M ⋅+⋅+⋅+⋅+⋅+是模5的完系， 所以12345,,,,N N N N N 中之一能被55n ⋅整除．归纳推理完成． 注：由此引申一个问题：证明：对任意奇数，都可以找到它的一个倍数，使得该倍数的各位数字都是奇数． 这个问题利用例3的结论，再通过构造一个例子来证明这个命题．例7.设p 是奇质数，证明：()()121211m od 2p p k p p k p --=+≡∑．（2004年加拿大数学奥林匹克）证明：因为1p -是偶数，故()11221212111p p p p p k k k k p k -----==⎡⎤=+-⎣⎦∑∑．由二项式定理，得()()21212121p p iip ip i p k Cpk -----=-=⋅⋅-∑．模2p ，得()()()()()2122211222122121mod p p p p p p p k C p k k p p kkp -------≡⋅⋅-+-≡-⋅⋅-．故()()()()212122222222212mod p p p p p k p k p p kp p kpkp -----+-≡-⋅⋅≡-≡-．对11k p ≤≤-，必有()gcd ,1k p =．由费马小定理，得()11mod p k p -≡．故()221mod p k p -≡．即221p p k --．从而()()222221mod p p pk p k p p p ---≡---≡-．因此()()122122111m od 222p p k p p p p p kp p p --=+--≡-⋅≡+≡∑． 例8.求证：方程组6331573329147147157x x x y y x x y y y z ⎧+++=⎨++++=⎩没有整数解．（2005年第34届美国数学奥林匹克）证明：1++①②，得329157147(1)1471571x y z +++=++③． 考虑[2,9]18=，联系费马小定理，证明上式两边模19不同余． 由费马小定理，知()gcd ,191a =时，()181mod19a ≡； 否则()gcd ,191a ≠即19|a 时，()180mod19a ≡． 因此()29180zz=≡或()1m od19．从而()91,0,1mod19z ≡-④．对Z n ∀∈，有()0,1,2,,9mod19n ≡±±± ，所以()28,3,2,0,1,4,5,6,7,9mod19n ≡---⑤． 由④、⑤，得()()23915,6m od19x y z +++≡--/⑥． 由费马小定理，得1571471571471881318831471571(5)51551⨯+⨯+++≡-++≡-++13334134551551(8)581⨯+≡-++≡-++≡--⨯-+()27581115815mod19≡-⨯-+≡-⨯-+≡-⑦由⑥、⑦得()()23915714711471571m od19x y z +++≡++/．故()23915714711471571x y z +++≠++． 因此，原方程组无整数解．例9.证明序列{}232,3,n n -= 至少含有一个无穷子序列，且其中的项两两互质． （1971年第13届国际数学奥林匹克）证明：⑴2231-=，，3235-=，423-两两互质；⑵假设正整数1n ，2n ，…，k n 使序列()i 123n -，223n -， (23)n -两两互质，则只要证明存在1k n +使123k n +-与序列()i 中的每个数都互质，即得这1k +个数两两互质．由归纳法，原命题得证．证明123k n +-不含序列()i 中的所有数的质因子即可．设{}12,,,r p p p 是由序列()i 中的所有数的质因子组成的集合，显然12,,,r p p p 都是奇质数，即()gcd 2,1i p =．则由费马小定理，得()121mod i p i p -≡．因此()()1121mod ri i p i p =-∏≡，其中1,2,,i r ∀= ．进而()()1123132mod ri i p i p =-∏-≡-≡-．而()3i p ≥都是奇质数，故()11gcd 23,1ri i p i p =-⎛⎫∏ ⎪-= ⎪⎝⎭． 因此取()111rk i i n p +==-∏，则()1112323ri k i p n +=-∏-=-与23i n-都互质，其中1,2,,i k ∀= ．例10.求所有的质数p 、q ，使得()()5252p p q q pq --． （1996年保加利亚数学奥林匹克）解：显然质数p 、q 都不为2，则(),11p q -=．如果52p p p -，由费马小定理，得()55mod p p ≡，()22mod p p ≡．从而52p -，所以3p =． 假设,3p q ≠，则52q q p -，52p p q -．不妨设p q >，由裴蜀定理，存在正整数u 、v ，使()11u q vp --=．显然质数p 、q 都不为5，由费马小定理，得()151mod q q -≡，()121mod q q -≡．故1152q q q ---． 所以()()()1111525255232u q u q vp vp vp vp vp q --++-=-=-+⋅，又52p p q -，所以32vp q ⋅，矛盾． 所以p 、q 之一为3．若3p q ==，满足题意，则()(),3,3p q =．若3p =，()33q >≠，则3352913q -=⋅，所以13q =． 因此，所求的解为(,)(3,3),(3,13),(13,3)p q =．评注：完系、费马小定理结合二项式定理等是处理整除、同余问题的重要工具．练习及参考答案练习1.设质数p 满足()7mod 8p ≡，证明p 不能表示成三个平方数之和． 分析：我们利用平方数模8的性质进行处理．证明：设存在三个整数a ，b ，c 使222p a b c =++．而对Z x ∀∈，有()20,1,4mod 4x ≡． 所以()2220,1,2,3,4,5,6mod 8a b c ++≡，而得不到()2227mod 8a b c ++≡． 因此形如()7mod 8p =的质数不能表作三个平方数之和．练习 2.一会议厅有n 张椅子围绕着一张圆桌．n 位代表在开会．第一位代表任意选择他（或她）的座位．此后第()1k +位代表坐在第k 位代表的右边的（按逆时针方向）第k 个座位，这里11k n ≤≤-．（特别地，第两位代表坐在第一位的下一个座位．）每张椅子不能坐多于一位代表．求能得到如此安置代表座位的n 值． （2002年英国数学奥林匹克第2轮） 解：2m n =，其中m 是任一非负整数．记这些座位的编号分别为0,1,2,,1n - ．第k 位代表坐在座位()12k k -，其中1,2,,k n = ．于是如果这n 个数()12k k -对模n 不同余，这里1,2,,k n = ，那么这个安置座位方案是可能的． 首先，假设2m n =，其中m 是非负整数．特别地，当0m =时，显然安置座位方案是可能的．当0m ≠时，我们有()()()()111222h h k k h k h k ---+--=．若h 和k 不相等，则h k -和1h k +-都是非零数，但它们具有相异奇偶性，并且都小于2n ． 于是其中一个是奇数，另一个不能被比2m 的指数更高的2的幂整除．这样()()12h k h k -+-不能被2m 整除，即()12h h -与()12k k -对模n 不同余．因此安置座位方案在n 是一个2的幂时可操作．反之，假设()221m n a =+，其中a 是正整数，m 是非负整数． 若2m a <，取21m h a =++，2m k a =-． 则21h k a -=+，112m h k ++-=，()()()1122122mh h k k a ---=+．故()12h h -和()12k k -对模n 同余．若2m a ≥，取21m h a =++，21m k a =-+． 则12m h k +-=，121h k a +-=+，()()()1122122mh h k k a ---=+．故也得到()12h h -和()12k k -对模n 同余．上述h 、k 的取值都是1~n 范围内的整数．因此若n 不是一个2的幂就没有可能的安置座位方案． 练习3.求数200120022003的末三位数字．（2003年加拿大数学奥林匹克）解：因为()20033mod 1000≡，所以()200120012002200220033mod 1000≡．为解决这个问题，我们首先确定一个正整数n 使()31mod 1000n ≡． 由二项式定理，得()()()()()1222131011101101102mmm m m mm m m ---=-=-+⋅⋅-+⋅⋅-++ ．上式中前三项后的各项之和能被1000整除．于是设2m q =，则()()4312010021mod 1000q q q q ≡-+-≡．①由()1201002110001q q q k -+-=+，253250q q k --=，由十字相乘法易得25q =满足． 从而()10031mod 1000≡．而()20022mod 100≡，故()()200120012199920022mod 10022mod 425≡≡⋅⋅． 因为()10210241mod 25=≡-，所以()()()199199199910922215121213m od 25=⋅≡-⋅≡-≡．于是()200120012002241352mod 100≡≡⋅=，再由①，得()20012001200220021005252200333312013130025241mod 1000k +≡≡≡≡-⋅+⋅≡．因此数200120022003的末三位数字是241．练习4.设三角形的三边长分别是整数l ，m ，n ，且l m n >>．已知{}{}{}444333101010lmn==，其中{}[]x x x =-，而[]x 表示不超过x 的最大整数．求这种三角形周长的最小值． （2003年全国高中数学联赛加试）解：由题意，知()4333m od 10l m n ≡≡，即3l 、3m 、3n 的末四位数字相同． 又当且仅当l m n <+时，以l ，m ，n （l m n >>）为边才能构成三角形． 由二项式定理，得()()()()24210002122310112010021103pp pp p p p p p --=-=-+--++ ．⑴由此容易得到，()431mod 10p ≡．即1i =时，44h p =≥，()431mod 10≡； ⑵若20100p k -=，则()4231m od 10p ≡，当5p q =时，()20231m od 10q ≡． 即2i =时，2020h q =≥，()20231m od 10≡；⑶若()20100211000p p p k -+-=，则()20331m od 10q ≡． 由225350q q k --=，得5q r =，()100331m od 10r ≡． 即3i =时，100100h r =≥，()100331m od 10≡． ⑷若()()()100021222010021100003p p p p p p k---+--=，则()100431m od 10r ≡，3262500412559300r r r k -++=，得5r s =，()500431m od 10s ≡． 即4i =时，500500h s =≥，()500431mod 10≡． 设500m n x =+，500l n y =+，其中x y <， 则500500n y n x n +<++，()500500n y x >-≥． 故()3500350150033003l m n n x y ++=++≥⨯+⨯=．即当三角形的三边长分别为1501l =，1001m =，501n =时，其周长l m n ++取得最小值，且最小值为3003．练习5.求证：存在无穷多个这样的正整数，它们不能表示成少于十个奇数的平方和． 分析：对于否定性问题，我们常利用同余．解：设正整数n 能够表示成22212...,s n x x x =+++① 其中i x 为奇数，1,2,...,,19.i s s =≤≤若2(mod 8)n ≡，则由①及21(m od 8),1,2,...,i x i s ≡=知2(mod 8)s ≡，即 2.s = 若2,3|s n =，则由①及20,1(m o d 3),1,2i x i ≡=知120(m od 3)x x ≡≡，从而9|.n 这说明若3(m o d 9)n ≡，则 2.s ≠综上所述，被8除余2，被9除余3，即具有形式7266,0,1,2,...k k +=的正整数便不能表示成①，故命题得证．评注：对于某些问题，常常需要多次选择不同的模进行同余处理． 练习6.证明：132730n n -． 分析：由原式联想到费马小定理． 证明：2730235713=⨯⨯⨯⨯．由费马小定理，()13mod 13n n ≡，()7mod 7n n ≡，()5mod 5n n ≡，()3mod 3n n ≡，()2mod 2n n ≡．而由()13121n n n n -=-易得713|n n n n --，513|n n n n --，313|n n n n --，213|n n n n --． 所以13|k n n -，2,3,5,7,13k =．且2，3，5，7，13两两互质，因此原结论成立． 练习7.求出大于1的整数n 的个数，使得对任意的整数a ，都有25|n a a -． 分析：联想例4，猜想n 的最大值为2730．解：设满足条件的正整数组成集合S ，若25|n a a -，25|m a a -，则25[,]|m n a a -，因此S 中全部数的最小公倍数也属于S ，即S 中的最大数是其余每个数的倍数．25|m a a -，则m 的约数也整除25a a -，于是只需确定最大数m ，其一切大于1的约数组成集合S ．2525|22,|33m m -- ，并且2525(22,33)235713--=⨯⨯⨯⨯，由例4，由费马小定理，易证235713⨯⨯⨯⨯25|a a -，所以235713m =⨯⨯⨯⨯，集合S 共有31个元素．评注：利用特殊值法确定最大值，再进行证明是处理竞赛问题的典型技巧．练习8.34021(m od 341)≡但3411113=⨯为合数，则称341是伪质数，证明：伪质数有无穷多个． 分析：我们想办法构造出具体的表达或递推关系．证明：已知341为伪质数，假设m 是伪质数，下面证明21m -是伪质数．首先，设m pq =，其中,p q 为大于1的整数，则2121(2)1m pq p q -=-=-，含有因子21p -，并且12121p m <-<-，所以21m -为合数．其次，由于1|21m m --，设121m ms --=，其中s 为大于1的正整数，11(21)12221212121(21)(21)mmm m --------=-=-+，而1212121(2)1m msms---=-=-，可被21m -整除，因而(21)121(mod(21))mm --≡-，所以21m-是伪质数，并且21m m ->．由此可知伪质数有无穷多个．评注：利用递推关系构造是解决无穷解问题的重要构造方法．练习9.求最小的正整数n ，使得333200212 (2002)n x x x +++=有整数解． （第43届IMO 预选题）分析：我们先估计出n 的值，在构造出一组解． 解：20024(mod 9)≡，341(m od 9)≡，200266731=⨯+， 所以20022002200244(m od 9)≡≡．又30,1(m od 9)x ≡±，其中x Z ∈．于是333333112123,,4(m od 9)x x x x x x +++≡/．由于332002101011=+++，则2002667320022002(2002)=⨯=6673(102002)⨯+6673(102002)⨯+6673(2002)+6673(2002)． 所以4n =．评注：选择适当的模，利用同余进行估计是重要的方法之一．练习10.正整数n 不能被2，3整除，且不存在非负整数a ，b ，使得23a b n -=．求n 的最小值．（2003年中国集训队测试）分析：我们先通过具体赋值猜出n 值，再进行证明．解：1n =时，11231-=；5n =时，22235-=；7n =时，12237-=；11n =时，432311-=|；13n =时，412313-=；17n =时，642317-=； 19n =时，332319-=；23n =时，522323-=；25n =时，132325-=；29n =时，512329-=；31n =时，502331-=；下证35n =满足要求，用反证法，若不然，存在非负整数a ，b ，使得2335a b -=． ⑴若2335a b -=，显然0a ≠，1，2，故3a ≥．模8，得()33m od 8b -≡，即()35mod 8b ≡，但()31,3mod 8b ≡，不可能．⑵若3235b a -=，易知0b ≠，1，模9，得()21mod 9a ≡， ∵(){}2mod 9:2,4,8,7,5,1,2,4,k∴621k ≡，6122k +≡，6224k +≡，6328k +≡，6427k +≡，()6525mod 9k +≡． 于是6n k =，其中k 为非负整数，所以23835b k -=．再模7，得()31mod 7b ≡． ∵(){}3mod 7:3,2,6,4,5,1,3,2,k ，故6b k '=，k '为正整数， ∴663235k k'-=，()()3333323235k kk k''-+=．∴{3333321,3235;k kk k''⋅=+=或{3333325,327.k kk k ''⋅=+= 于是，3318k '=或6，不可能．综上可知，min 35n =． 评注：对于不定方程无解的问题常用同余处理． 练习11.证明：对于任意正整数n ，2(1)!n n n -⎡⎤⎢⎥+⎣⎦是偶数． （2004年亚太地区数学奥林匹克）分析：当n 和1n +是合数时，容易处理，我们只要处理n 和1n +之一是质数的情况． 证明：对于1,2,3,4,5n =，我们有2(1)!0n n n -⎡⎤=⎢⎥+⎣⎦，显然为偶数．我们考虑6n ≥．如果n 和1n +是合数，则它们一定整除()1!n -，并且互质．所以它们的乘积整除()1!n -．由于n 和1n +中只有一个是偶数，对于6m ≥，()2!m -所含的2的幂指数大于m 所含的幂指数，所以2(1)!n n n -⎡⎤⎢⎥+⎣⎦是偶数． 我们最后考虑1n p +=为一个质数，和n p =为一个质数． 如果1n p +=，则1p -是一个合数，所以1p -整除()2!p -．令()2!1p k p -=-，由威尔逊定理()()2!1mod p p -≡，所以()()11mod k p p -≡，因此()1mod kp ≡-．所以1k p+是一个整数．但k 是偶数，所以1k +是奇数，因此1k p+是奇数．又11k k p p⎡⎤+=-⎢⎥⎣⎦，所以()21!n k p n n -⎡⎤⎡⎤=⎢⎥⎢⎥+⎣⎦⎣⎦是偶数．如果n p =，则()1!1p k p -=+是偶数，所以1k +是奇数．由威尔逊定理()()11mod k p p +≡-，所以1k p +是一个奇数，所以()21!11n k k k p p p n n -⎡⎤⎡⎤⎡⎤+===-⎢⎥⎢⎥⎢⎥+⎣⎦⎣⎦⎣⎦是偶数． 综上，原命题成立．评注：当n 和1n +之一是质数时，由()1!n -我们联想到威尔逊定理． 练习12.设{}n a ，{}n b 定义如下：01a =，11a =，112n n n a a a +-=+，01b =，17b =，()11231,2,n n n b b b n +-=+= ．证明：除“1”以外这两个数列没有其它相同的项．证明：012351,1,3,5,11...a a a a a =====，012341,7,17,55,161...b b b b b =====下面证明：21225(m od 8),3(m od 8)n n a a ++≡≡；21227(m od 8),1(m od 8)n n b b ++≡≡，其中n 为正整数．初值易验证，假设21225(m od 8),3(m od 8)k k a a ++≡≡，则23222123255(m o d 8)k k k a a a +++=+≡+⨯≡，24232225233(m od 8)k k k a a a +++=+≡+⨯≡，可知1n k =+时结论成立．同理可证{}n b ．因而原命题成立．练习13.求所有的正整数对(),a n 使得()1nna an+-是整数．证明：若a 为任意正整数，则(),1a 显然是原问题的解，下面我们证明原问题没有其他解．若2n ≥，易知()(),,11a n a n =+=，不妨设p 为n 的最小质因子，则()1nnp a a +-，又由费马小定理()111p p p a a--+-，而()1,1p n -=，由裴蜀定理存在正整数u ，v ，使()11u p vn --=． 则()()()()()()()11111111u p vn vnu p vn vnvnp a aa aa a aa-+-++-=+-=++-+，所以vn p a ，与(),1a n =矛盾．所以没有其他的正整数解．练习14.试求与无穷数列()23611,2,n n n n a n =++-= 的一切项均互素的所有正整数． （2005年第46届国际数学奥林匹克） 解：满足条件的正整数只有一个：1．为此只要证明对任一素数p ，存在正整数n 使得n p a ．由于248a =，故2,3p =时结论为真．设3p >，则p 与2、3、6均互素，由费马小定理，()1112361mod p p p p ---≡≡≡． 于是22236p p --≡⨯，()22326mod p p p --≡⨯．()()222223632161mod p p p p p ----++≡++⨯≡．2p p a -．证毕．练习15.设k 是一个大于1的固定的整数，245m k =-． 证明：存在正整数a 、b ，使得如下定义的数列{}0121:,,n n n n x x a x b x x x ++===+，0,1,n =其所有项均与m 互质． （第45届IMO 预选题）证：取1a =，222b k k =+-．因为()245mod k m ≡，所以()2242421mod b k k k m =+-≡+． 从而()2244414644mod b k k k b m ≡+-≡+≡+．又因为m 是奇数，故()21m od b b m ≡+． 由于()()()()222gcd ,gcd 22,45gcd 22,212,211b m k k k k k k k =+--=+-+=+=， 故()gcd ,1n b m =，其中n 是任意正整数．下面用数学归纳法证明：当0n ≥时，有()mod n n x b m ≡． 当0,1n =时，显然结论成立．假设对于小于n 的非负整数，结论都成立，其中2n ≥，则有()()12222121mod n n n n n n n n x x x b b b b b b b m ------=+≡+≡+≡≡． 因此，对于所有的非负整数n ，有()()gcd ,gcd ,1n n x m b m ==．练习16.设,a b +∈ ，且对,n +∀∈ 都有()()n n a n b n ++．证明：a b =． （第46届IMO 预选题）证明：假设a b ≠，则b a >．取素数p b >，则()(),,1a p b p ==． 由费马小定理，得()111mod p p a b p --≡≡．取()11n k p =-+，则()mod n a a p ≡，()mod n b b p ≡．从而()mod n a n a n p +≡+． 现在我们想让()0mod n a n a n p +≡+≡，只要()()1110mod na n a n a k p a k p +≡+≡+-+≡+-≡．因此仅须取1k a =+，即()()111n a p =+-+即可． 此时p 是n a a +的质因子，故也是n b b +的质因子．进而()0mod n b n b n b a p +≡+≡-≡，即p b a -．但0b a b p <-<<，矛盾． 因此，原命题成立．练习17.设p 为质数．证明：存在一个质数q ，使得对任意整数n ，数p n p -不能被q 整除． （2003年第44届国际数学奥林匹克）解：由于()212111mod 1pp p p p p p p p --=++++≡+- ， 则11pp p --中至少有一个质因子q ，满足()21mod q p ≡/．下面证明q 为所求．假设存在整数n ，使得()mod p n p q ≡．则由q 的选取，有()21mod p p n p q ≡≡． 另一方面，由费马小定理，()11mod q n q -≡（由于q 为质数且(),1n q =）． 由于()2|1p q -/，有()2,1|p q p -，则()1m od p n q ≡．因此，()1mod p q ≡． 从而，导出()11mod p p p p q -+++≡ ． 由q 的选取，有()0mod p q ≡．矛盾．。
