高中数学竞赛 数论剩余类及剩余系(1)定义1 设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r ≤m-1}称为模m 的一个剩余类(也叫同余类)。

K 0,K 1,…,K m-1为模m 的全部剩余类.(2)性质(ⅰ)i m i K Z 10-≤≤= 且K i ∩K j =φ(i ≠j). (ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里.(ⅲ)对随意a 、b ∈Z ，那么a 、b ∈K r ⇔a ≡b(modm).(1)定义2 设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系,简称完系. 特殊地,0,1,2,…,m -1叫做模m 的最小非负完全剩余系.下述数组叫做模m 的肯定最小完全剩余系:当m 为奇数时,21,,1,0,1,,121,21--+----m m m ;当m 为偶数时,12,,1,0,1,,12,2--+--m m m 或2,,1,0,1,,12m m -+-. (2)性质(ⅰ)m 个整数构成模m 的一完全剩余系⇔两两对模m 不同余. (ⅱ)假设(a,m)=1，那么x 及ax+b 同时遍历模m 的完全剩余系. 证明:即证a 0,a 1,…,a m-1及aa 0+b, aa 1+b,…,aa m-1+b 同为模m 的完全剩余系, 因a 0,a 1,…,a m-1为模m 的完系时,假设aa i +b ≡aa j +b(modm),那么a i ≡a j (modm),冲突!反之,当aa 0+b, aa 1+b,…,aa m-1+b 为模m 的完系时,假设a i ≡a j (modm),那么有aa i+b≡aa j+b(modm),也冲突!(ⅲ)设m1,m2是两个互质的正整数,而x,y分别遍历模m1,m2的完系,那么m2x+m1y历遍模m1m2的完系.证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数.假定m2x/+m1y/≡m2x//+m1y//(modm1m2),其中x/,x//是x经验的完系中的数,而y/,y//是y经验的完系中的数.因(m1,m2)=1,所以,m2x/≡m2x//(modm1),m1y/≡m1y// (modm2),从而x/≡x//(modm1),y/≡y//(modm2),冲突!(1)定义3假如剩余类K r里的每一个数都及m互质，那么K r叫及m互质的剩余类.在及模m互质的全部剩余类中，从每一类中任取一个数所做成的数组，叫做模m的一个既约(简化)剩余系.如:模5的简系1,2,3,4;模12的简系1,5,7,11.(2)性质(ⅰ)K r及模m互质⇔K r中有一个数及m互质；证明:设a∈K r,(m,a)=1,那么对随意b∈K r,因a≡b≡r(modm),所以,(m,a)=(m,r)=(m,b)=1,即K r及模m互质.(ⅱ)及模m互质的剩余类的个数等于)m(ϕ,即模m的一个既约剩余系由)m(ϕ个整数组成()m(ϕ为欧拉函数);(ⅲ)假设(a,m)=1,那么x及ax同时遍历模m的既约剩余系.证明:因(a,m)=1,(x,m)=1,所以,(ax,m)=1.假设ax1≡ax2(modm),那么有x1≡x2(modm),冲突!(ⅳ)假设a1,a2,…,aφ(m)是)m(ϕ个及m互质的整数,并且两两对模m不同余,那么a1,a2,…,aφ(m)是模m的一个既约剩余系.证明:因a 1,a 2,…,a φ(m)是)m (ϕ个及m 互质的整数,并且两两对模m 不同余, 所以,a 1,a 2,…,a φ(m)属于)m (ϕ个剩余类,且每个剩余类都及m 互质,故a 1,a 2,…,a φ(m) 是模m 的一个既约剩余系.(ⅴ)设m 1,m 2是两个互质的正整数,而x,y 分别历遍模m 1,m 2的既约剩余系,那么m 2x+m 1y 历遍模m 1m 2的既约剩余系.证明:明显,既约剩余系是完系中全部及模互质的整数做成的.因x,y 分别历遍模m 1,m 2的完系时,m 2x+m 1y 历遍模m 1m 2的完系.由(m 1,x )=(m 2,y )=1, (m 1,m 2)=1得(m 2x,m 1)=(m 1y,m 2)=1,所以,(m 2x+m 1y,m 1)=1,(m 2x+m 1y,m 2)=1,故 (m 2x+m 1y, m 1m 2)=1.反之假设(m 2x+m 1y, m 1m 2)=1,那么(m 2x+m 1y,m 1)=(m 2x+m 1y,m 2)=1,所以,(m 2x,m 1)=(m 1y,m 2)=1,因(m 1,m 2)=1,所以,(m 1,x )=(m 2,y )=1.证毕.推论1假设m 1,m 2是两个互质的正整数,那么)()()(2121m m m m ϕϕϕ=.证明:因当x,y 分别历遍模m 1,m 2的既约剩余系时,m 2x+m 1y 也历遍模m 1m 2的既约剩余系,即m 2x+m 1y 取遍)(21m m ϕ个整数,又x 取遍)(1m ϕ个整数,y 取遍 )(2m ϕ个整数,所以, m 2x+m 1y 取遍)()(21m m ϕϕ个整数,故)()()(2121m m m m ϕϕϕ=.推论2 设整数n 的标准分解式为k kp p p n ααα 2121=(k p p ,,1 为互异素数, *1,,N k ∈αα ),那么有)11()11)(11()(21k p p p n n ---= ϕ. 证明:由推论1得)()()()(2121k k p p p n αααϕϕϕϕ =,而1)(--=αααϕp p p ,(即从1到αp 这αp 个数中,减去能被p 整除的数的个数),所以,)())(()(11221112211------=kk k k p p p p p p n ααααααϕ )11()11)(11(21kp p p n ---= .4.欧拉(Euler)及费尔马(Fermat)定理欧拉(Euler)定理 设m 是大于1的整数,(a ,m)=1,那么)(m od 1)(m a m ≡ϕ. 证明:设r 1,r 2,…,r )(m ϕ是模m 的既约剩余系,那么由性质3知a r 1,a r 2,…,a r )(m ϕ也是模m 的既约剩余系,所以, a r 1a r 2…a r )(m ϕ≡r 1r 2…r )(m ϕ(modm),即≡)(21)(m m r r r a ϕϕ)(21m r r r ϕ ,因()(21m r r r ϕ ,m)=1,所以,)(m od 1)(m a m ≡ϕ.推论(Fermat 定理) 设p 为素数,那么对随意整数a 都有)(m od p a a p ≡.证明:假设(a , p )=1,由1)(-=p p ϕ及Euler 定理得)(m od 11p a p ≡-即)(m od p a a p ≡;假设(a , p )≠1,那么p |a ,明显有)(m od p a a p ≡.例1设m>0,证明必有一个仅由0或1构成的自然数a 是m 的倍数.证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm 的同一剩余类中,它们的差即为所求的a .例2证明从随意m 个整数a 1,a 2,…,a m 中,必可选出假设干个数,它们的和 (包括只一个加数)能被m 整除.证明:考虑m 个数a 1,a 1+a 2,a 1+a 2+a 3,…,a 1+a 2+…+a m ,假如其中有一个数能被m 整除,那么结论成立,否那么,必有两个数属于modm 的同一剩余类,这两个数的差即满意要求.例3设f(x)=5x+2=f 1(x), f n+1(x)=f[f n (x)].求证:对随意正整数n,存在正整数m,使得2021|f n (m).证明:因f 2(x)=f[f(x)]=5(5x+2)+2=52x+5×2+2,f 3(x)=f[f 2(x)]=53x+52×2+5×2+2,..., f n (x)=5n x+5n-1×2+5n-2×2+ (2)因(5n ,2021)=1,所以,x 及f n (x)同时历遍mod2021的完系,1≤x ≤2021,所以,存在正整数m(1≤m ≤2021)使得f n (m)≡0(mod2021),即2021|f n (m).例4设123,,,a a a 是整数序列,其中有无穷多项为正整数,也有无穷多项为 n ,数123,,,,n a a a a 被n 除的余数都各不一样.证明:在数列123,,,a a a 中,每个整数都刚好出现一次.证明:数列各项同时减去一个整数不变更此题的条件和结论,故不妨设a 1=0.此时对每个正整数k 必有∣a k ∣<k:假设∣a k ∣≥k,那么取n=∣a k ∣,那么a 1≡a k ≡0(mod n),冲突.如今对k 归纳证明a 1,a 2,…,a k 适当重排后是肯定值小于k 的k 个相邻整数.k=1明显.设a 1,a 2,…,a k 适当重排后为-(k -1-i),…,0,…,i (0≤i ≤k -1),由于a 1,a 2,…,a k ,a k+1是(mod k+1)的一个完全剩余系,故必a k+1≡i+1(mod k+1), 但 ∣a k+1∣<k+1,因此a k+1只能是i+1或-(k -i),从而a 1,a 2,…,a k ,a k+1适当重排后是肯定值小于k+1的k+1个相邻整数.由此得到:1).任一整数在数列中最多出现一次;2).假设整数u 和v (u<v) 都出如今数列中,那么u 及v 之间的全部整数也出如今数列中.最终由正负项均无穷多个〔即数列含有随意大的正整数及随意小的负整数〕就得到:每个整数在数列中出现且只出现一次.例5偶数个人围着一张圆桌探讨，休息后，他们依不同次序重新围着圆桌坐下,证明至少有两个人，他们中间的人数在休息前及休息后是相等的。

证明：将座号依顺时针次序记为1,2,…,2n ，每个人休息前后的座号记为 (i,j)，那么i 及j 历遍完全剩余系mod2n 。

假如两个人(i 1,j 1),(i 2,j 2)休息前后在他们中间的人数不相等，那么有j 2-j 1≢i 2-i 1mod2n ，即j 2-i 2≢j 1-i 1(mod2n)，因此，j-i 也历遍完全剩余系mod2n,所以,j-i 的和=∑∑-i j ≡0(mod2n)，而任一完全剩余系mod2n 的和≡1+2+…+2n-1≡n(2n-1)≢0(mod2n),冲突！故结论成立.例6数列{a n }定义为: a 0=a (a ∈N *)，a n+1=a n +!40n (n ∈N).数列{a n }中存在无穷多项可被2021整除.证明:因(40,2021)=1,所以,)2011(m od 140)2011(≡ϕ.因当)2011(ϕ>n 时,!|)2011(n ϕ,所以,数列{a n (mod2021)}构成模2021的完系,且是周期数列,所以, 数列{a n }中存在无穷多项可被2021整除.例7证明:存在无穷多个正整数n,使得n 2+1∤n!.证明:引理1对素数p >2,⇔≡)4(mod 1p 存在x(1≤x ≤p -1)使)(m od 12p x -≡. 证:充分性:因对1≤x ≤p -1,( p ,x)=1,所以,)(mod 1)(2121p x xp p ≡=--,≡-212)(p x )(mod 1)1(21p p ≡--,所以,为偶数,即).4(mod 1≡p必要性:因1≤x ≤p -1时,x,2x,…,(p -1)x 构成modp 的既约剩余系,所以,存在 1≤a ≤p -1,使得a x ≡-1(mod p ),假设不存在a (1≤a ≤p -1), a =x,使a x ≡-1(mod p ), 那么这样的a ,x 共配成对,那么有)(mod 1)!1()1(21p p p -≡-≡--,即为奇数,及14+=k p 冲突!所以,必存在x(1≤x ≤p -1)使)(m od 12p x -≡.引理2形如4k+1(k ∈Z)的素数有无限多个.证：假设形如4k+1的素数只有n 个:p 1,p 2,…,p n ，那么p 1,p 2,…,p n 都不是 a =4(p 1p 2…p k )2+1的素因数.设q 是a 的一个素因数,那么有(2p 1 p 2…p k )2≡-1(mod q ),因存在1≤x ≤q -1使 2p 1 p 2…p k ≡x (mod q ),即x 2≡-1(mod q ),所以,由引理1知14+=k q ,冲突！所以,形如4k+1的素数有无限多个.回到原题:由引理1,2知,存在无穷多个素数p ,使得存在x(1≤x ≤p -1)使 )(m od 12p x -≡.即p |x 2+1,因p>x,所以, p ∤x!, x 2+1∤x!,因这样的素数p 无穷多,所以,相应的x 也无穷多.例8设f(x)是周期函数,T 和1是f(x)的周期且0<T<1.证明:(1)假设T 为有理数,那么存在素数p,使得p1是f(x)的周期; (2)假设T 为无理数,那么存在各项均为无理数的数列{a n }满意0<a n+1<a n <1 (n=1,2, …),且每个a n 都是f(x)的周期.证明：(1)设T=nm (正整数m,n 互质,且n ≥2),因(m,n)=1,所以,m,2m,…,nm 构成 modn 的完系,故存在k ∈N *使得km ≡1(modn),即存在t ∈N *使得km=nt+1,因 f(x)=f(x+kT)=f(x+n km )=f(x+t+n 1)=f(x+n 1),所以n1是周期. 设n=kp ,其中k ∈N *, p 为素数,那么是周期.故存在素数p,使p 1是周期. (2)当T 为无理数时,取a 1=T,那么T 为无理数, 0<T<1.设k≤n 时存在无理数 a k ,使得0<a k <a k-1<1,且a k 是周期.对k+1,总存在存在u,v ∈N *,使得0<u a k -v<a k <1,取a k+1=u a k -v,那么a k+1是无理数且是f(x)的周期,且0<a k+1<a k <1,递推知存在各项均为无理数的数列{a n }满意0<a n+1<a n <1(n=1,2,…),且每个a n 都是f(x)的周期.例9设正整数n ≥2.求全部包含n 个整数的集合A,使得A 的随意非空子集中全部元素的和不能被n+1整除.解:设A={a 1,a 2,…,a n }是满意条件的集合.),,2,1(1n k a S ki i k ==∑=,依题意知,对随意k=1,2,…,n 都有n+1∤S k ,且随意S k , S j (k ≠j)都有S k ≢S j (modn+1),所以,{S k }包含了modn+1的全部非零剩余,因对1≤i ≤n,整数a i ,S 2,S 3,…,S n 也包含了mod(n+1)的全部非零剩余,所以, a 1=S 1≡a i (modn+1),即A 中随意a i ≡a 1(modn+1).所以,对随意1≤k ≤n, a 1+a 2+…+a k ≡k a 1(modn+1).且k a 1≢0(modn+1),从而(a 1,n+1)=1.取a 1=a 得集合A={a +k i (n+1)|k i ∈Z, 1≤i ≤n,a ∈Z,且(a ,n+1)=1}为所求. 例10对随意正整数n,用S(n)表示集合{1,2,…,n}中全部及n 互质的元素之和. 证明: 2S(n)不是完全平方数;例11求全部的奇质数p ,使得.例12求全部质数p ,使得2122213)()()(|-+++p p p p C C C p .例13设n 为大于1的奇数,k 1,k 2,…,k n 是n 个给定的整数,对1,2,…,n 的每一个排列a=(a 1,a 2,…,a n ),记S(a)=.证明:存在两个1,2,…,n 的排列b 和c(b ≠c),使得n!|S(b)-S(c).证明:假如对1,2,…,n 的随意两个不同排列b 和c(b ≠c),都有n!∤S(b)-S(c),那么当a 取遍全部排列时(共n!个),S(a)遍历模n!的一个完系, 因此,有∑aa S )(≡1+2+…+n!≡(modn!) ①, 另一方面,我们有∑a a S )(=)!(mod 02)1(!])!1[(11111n k n n j n k a k a k n i i n i n j in i a i i a n i i i ≡+=-==∑∑∑∑∑∑∑===== ②. 由①∑a a S )(≡2!n (modn!)及②∑a a S )(≡0(modn!)(因n 为奇数)冲突!故原命题成立.例14m,n 为正整数,且m 为奇数,(m,2n -1)=1.证明:m|.证明:因1,2,…,m 构成modm 的完系,(m,2)=1,所以2,4,…,2m 也构成 modm 的完系,所以)(mod )2(11m k k m k n m k n ∑∑==≡即)(mod 0)12(1m k mk n n≡-∑=. 因(m,2n -1)=1,所以.得证.例15x ∈(0,1),设y ∈(0,1)且对随意正整数n ，y 的小数点后第n 位数字是x 的小数点后第2n 位数字.证明:假设x 是有理数,那么y 也是有理数.例16设A={a 1,a 2,…,a φ(n)}是模n 2≡1(modn)在A 中解的个数为N,求证:a 1a 2…a φ(n)≡2)1(N -(modn).同余方程及同余方程组1.同余方程(组)及其解的概念定义1 给定正整数m 及n 次整系数多项式0111)(a x a x a x a x f n n n n ++++=-- ，那么同余式f(x)≡0(modm)①叫做模m 的同余方程,假设a n 0(modm),那么n叫做方程①的次数.假设x=a 是使f(a )≡0(modm)成立的一个整数,那么x ≡a (modm)叫做方程①的一个解,即把剩余类a (modm)叫做①的一个解.假设a 1(modm),a 2(modm)均为方程①的解,且a 1,a 2对模m 不同余,就称它们是方程①的不同解.由此可见,只需在模m 的任一组完系中解方程①即可.例1解方程2x 2+x -1≡0(mod 7).解:取mod7的完系:-3, -2,-1,0,1,2,3,干脆验算知x ≡-3(modm)是解. 例2求方程4x 2+27x -12≡0(mod 15).解:取mod15的完系:-7, -6,…,-1,0,1,…,7,干脆验算知x ≡-6,3(modm)是解.设m ∤a ,那么a x ≡b(modm),叫模m 的一次同余方程.定理1当(a ,m)=1时,方程a x ≡b(modm)必有解,且解数为1.证明:因当(a ,m)=1时,x 及a x 同时遍历模m 的完系,所以,有且仅有一个x 使得 a x ≡b(modm).即x ≡a -1b(modm).定理2方程a x ≡b(modm)有解⇔(a ,m)|b,且有解时其解数为(a ,m),及假设x 0是一个特解,那么它的(a ,m)个解是1),(,,1,0),(m od ),(0-=+≡m a t m t m a m x x . 例3解方程6x ≡10(mod8). 解:因(6,8)=2,且-1是一个特解,所以,方程6x ≡10(mod8)的解为:1,0),8(mod 41=+-≡t t x 即)8(mod 3,1-≡x .例4解方程12x ≡6(mod9).因(12,9)=3,且-1是一个特解,所以,方程12x ≡6(mod9)的解为:2,1,0),8(mod 31=+-≡t t x 即)8(mod 5,2,1，-≡x .3.同余方程组定义3给定正整数m 1,m 2,…,m k 和整系数多项式f 1(x),f 2(x),…,f k (x),那么同余式组②,叫做同余方程组.假设x=a 是使f j (a )≡0(modm j )(1≤j ≤k)成立的一个整数,那么x ≡a (modm)叫做方程组②的一个解,即把剩余类a (modm)叫做②的一个解.其中m =[m 1,m 2,…,m k ].例5解方程组.解:由例3知6x ≡10(mod8)的解是)8(mod 3,1-≡x .所以,原解方程组⇔ 或或)56(mod 3,31)56(mod 3≡⇔≡x x .中国剩余定理:设K ≥2,而m 1,m 2,…,m k 是K 个两两互质的正整数，令 M=m 1m 2…m k =m 1M 1=m 2M 2=…=m k M k ，那么对随意整数a 1,a 2,…,a k 以下同余式组： ③的正整数解是x ≡a 1M 1M 1-1+a 2M 2M 2-1+…+a k M k M k -1(modM).其中M j -1满意M j M j -1≡1(modm j )(1≤j ≤k),即M j 对模m j 的逆.证明:(1)对1≤j ≤k ,因m j |M i (i ≠j) ,m j |M ,所以x ≡a j M j M j -1≡a j (modm j ).(2)设x,y 都是同余式组的解,即x ≡a j (modm j ),y ≡a j (modm j )(1≤j ≤k),那么x ≡y (modm j ),即m j |x -y ,因m 1,m 2,…,m k 两两互质,所以M| x-y 即x ≡y (modM). 注:(1)存在无穷多个整数x 满意同余方程组③,这些x 属于同一模m 的剩余类;(2)同余方程组③仅有一个解x ≡a 1M 1M 1-1+a 2M 2M 2-1+…+a k M k M k -1(modM).(3)当(a ,m i )=1(=1,2,…,n)时,同余方程组⎪⎪⎩⎪⎪⎨⎧≡≡≡⇔⎪⎪⎩⎪⎪⎨⎧≡≡≡---)(mod )(mod )(mod )(mod )(mod )(mod 12211112211k k k k m a a x m a a x m a a x m a ax m a ax m a ax 仍旧具有定理结论. 这在数论解题中具有重要应用.例6“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何〞.解:设物数x,那么有,这里m 1=3,m 2=5,m 3=7,M=3×5×7=105,所以,35×35-1≡2×35-1≡1(mod3)⇔35-1≡2(mod3),21×21-1≡21-1≡1(mod5)⇔21-1≡1(mod3),15×15-1≡15-1≡1(mod7)⇔15-1≡1(mod3),所以,同余方程组的解为:)105(mod 23233115212132352≡=⨯⨯+⨯⨯+⨯⨯≡x ,即x=105k+23(k ∈N). 例7有兵一队,假设分别列5,6,7,11行纵队,那么末行人数分别为1,5,4,10.求兵数.解:设兵数x,那么,其中m 1=5,m 2=6,m 3=7,m 4=11,M=2310,462×462-1≡2×462-1≡1(mod5)⇔462-1≡3(mod5),385×385-1≡385-1≡1(mod6)⇔385-1≡1(mod6),330×330-1≡330-1≡1(mod7)⇔330-1≡1(mod7),210×210-1≡210-1≡1(mod11)⇔210-1≡1(mod11),所以,同余方程组的解为:)2310(mod 2111637121010330438553462≡=⨯+⨯+⨯+⨯≡x ,即x=2310k+2111(k ∈N).例8证明:对随意n 个两两互质的正整数:m 1,m 2,…,m n ,总存在n 个连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n).证明:由剩余定理知,总存在整数k 使得,即存在连续的自然数k+1,k+2,…,k+n 使得m i |k+i(i=1,2,…,n).例9证明:对随意n ∈N *,存在n 个连续正整数它们中每一个数都不是素数的幂(当然也不是素数).证明∈N *,取两组不同的素数p 1,p 2,…,p n 及q 1,q 2,…,q n ,那么由剩余定理知存在m ∈N *,使得同时成立.于是,n 个连续正整数m+1, m+2,…,m+n 中,每一个数都有两个不同的素因子.故结论成立.例10证明:存在一个含有N(≥2)个正整数的集合A,使得A 中随意两个数都互质,且A 中随意k(k ≥2)个数的和都是合数.例11证明:存在一个由正整数组成的递增数列{a n },使得对随意k ∈N *,数列 {k +a n }中都至多有有限项为素数.证明:用p 1,p 2,p 3,…a 1=2,a 2为合适且大于a 1的最小正整数a 2=8,取a 3合适且大于a 2的最小正整数a 2=38.假定a 1,a 2,…,a n 都已确定,那么取a n+1合适且大于a n 的最小正整数,由剩余定理知满意条件的a n+1存在.那么上述递推关系定义的数列{a n }满意题意:因对随意k ∈N *,当n ≥k+1时,都有k+a n ≡0(mod p k+1),由{a n }递增可知{k +a n }从第k+2项起每一项都是p k+1的倍数,且都大于p k+1,所以,数列{k +a n }中至多有k+1项为素数.例12是否存在一个由正整数组成的数列，使得每个正整数都恰在该数列中出现一次，且对随意正整数k ，该数列的前k 项之和是k 的倍数？解:取a 1=1,假设a 1,a 2,…,a m 都已确定,令t 为不在a 1,a 2,…,a m 中出现的最小正整数, S=a 1+a 2+…+a m .由剩余定理知存在无穷多个r ∈N *,使得⎩⎨⎧+≡+++≡+)2(mod 0)1(mod 0m t r S m r S 成立.(如a 1=1,取t=2,合适且r>1,2得r=3). 取这样的r,使得r>t 且r>},,,m ax {21m a a a ,令a m+1=r, a m+2=t,那么这样得到的数列{a n }满意要求.例13证明:存在一个n ∈N *,使得对随意整数k,整数k 2+k+n 没有小于2021的质因数.例14证明:存在k ∈N *, 使得对随意n ∈N *,数2n k+1都是合数.例15设m ∈N *,n ∈Z,证明:数2n 可以表为两个及m 互素的整数之和.。