第11讲同余基本理论

第n讲同余基本理论

【考点预测】

同余理论是初等数论的重要组成部分，是研究整数问题的重要工具之一，利用同余来论证某些整除性

的问题是很简便的.

【定义1】设，”是大于1的正整数，是整数，如果词则称。与b关于模加同余，记作

<7=/?(modm),读作。同余模加.

显然，有如下事实：

(1)若a三O(modm),则词a；

(2)。三6(mod/%)=分别用加去除〃与Z?,余数相同.

【定理1】设a,b,c,皿〃2>1)都是整数，则有

(1)6r=iz(modm)(反身性)；

(2)若a三伏mod”)，贝Ub三。(mod机)(对称性)；

(3)若〃三。(mod〃z),b=c(modm),则a三c(modm)(传递性).

【定理2】设%三4(mod/〃)，a2=b2(modm),贝lj

(1)4±々2三(4±%)(moch%)；

(2)a{a2=bIb2(modtn).

【推论1】若4三为(modM,2=l,2,,n,则

(1)£1a卜=y.(mod〃?)；

k=lk=l

(2)ak=「J%(modm).

k=\k=\

【推论2】若。三伙mod/%),则〃"三//'(modm).

【定理3】若《生三43(modm)M2=b2(modnt),且(〃2，")=1，贝ljq三4(modm).

【推论3】若ac=bc(modm),且则〃三伏mod/??).

注意(m,c)=1这一条件，当(〃z,c)wl时，此性质不成立，如2/4(modl2),但2x6三4x

6(mod12).

【定理4]若〃三Z?(modm1),tz=Z?(mod/n2),,a三mod〃z,J,且M=[g，叫，,mn],贝lja三伙modM).

【定义2】设机£N,M.2.把全体整数按其对模〃?的余数“假处机-1)归于一类，记为K,..每一类

储”=0,1,2,，机-1)均称为模加的剩余类(又叫同余类).

由定义知K,.={q〃7+r|qeZ},r=0,l,2,,m-\,即&={a|awZ，。三r(mod/n)},

r=0,l,2,,m-\.它是一个公差为机的(双边无穷)的等差数列.

根据定义，剩余类具有如下性质：

(1)Z=K(,&K,“_],且K,Kj=0(i^j)；

(2)对任一数“eZ,有唯一的“使”e勺,；

(3)对任意的Kra=b{modm).

【定义3】设(),&,,Kai是模机的全部剩余类，从每个K,中任取一个数a,,这机个数出,%

组成的一个数组称为模用的一个完全剩余系，简称完系.

显然，模沉的完系有无穷多个，但最常用的有

(1)非负最小完系:0,1,2,,m-\.

(2)绝对值最小完系：

当，"为奇数时，有0,±1,士2,,±—；

2

当，”为偶数时，有0,±1,±2,,±^y-l^,±y.

由定义不难得到如下判别完系的方法：

【定理5】m个整数风,再，，%1是模巾的一个完系的充要条件是巷壬Xj(modm)(iw/).

【定义6】若与,西，是模团的完系，则与+/?,司+。，，%加_1+Z?也是模m的完系.

【定理7】若闻,办，，Xg是模m的完系，(a9m)=l,则叫^儿叫+匕，+人也是模用的完系.

【定义4】如果一个模〃?的剩余类K,中任一数与相互质，则称降是与模相互质的剩余类；在与模加

互质的每个剩余类中任取一个数(共例加)个)所组成的数组，称为模加的一个简化剩余系，简称简系.

由此定义不难得到：

【定理8】国,々，，％⑼是模〃7的简系的充要条件是(知优)=1且占wXj(modm)(iW/，

i,j=1,2,.，以加))•

【定理9】在模加的一个完系中，取出所有与〃z互质的数组成的数组就是一个模〃，的简系.

质数模〃的最小非负简系为1,2,3,.

【定理10]若=且为,巧，，毛(⑼是模小的简系，则4叫,畛，，鸣.(⑼也是模〃2的简系.

剩余类与完系、简系在解题中的应用是十分广泛的.

欧拉定理设a,mGN,(tz,/n)=1,则加刈三1(modm).

费马小定理设〃为质数，(a,p)=l,则a，—三l(modp).

威尔逊(Wilson)定理设〃是素数，则(〃-1)!三-1(1110(1〃).

中国剩余定理设女..2,而叫，径，，"4是2个两两互质的正整数，令M=/g1nlmk=

mxMx=m2Mk==mkMk,则下列同余式组：

x三a1（modm}）,

「="2""°山"2），的正整数解是x三“MM-i+“2M2〃丁++akM.

x三4（modmk）

其中，M］满足监三1（mode）.

【定理Hl设〃为质数，。/为两个正整数，且a力在〃进制下，分别为。=（44-a。）。，

b=（bkbk_xM，,0,,即4<p.求证：CW：：Cj（modp）.

【定理12】在1,2,中，有/pi+%*2++4个数是p的倍数，有4p"2+%〃-3++出

个为p2的倍数，，以为小的倍数.所以在〃!中P的指数为

ak（pA1+pk2++1）+%1（*2+*3++1）++“|

_4（P*-1）ak-\（/?A'-1）q（p-l）_〃-S（〃）

p—lp-1p-\p-\

【典例例题】

例1.（2019・全国•高三竞赛）对给定的正整数M,定义工（M）表示M的各个数位上的数字之和的平方，当

">1且〃eN时，力（£i（M））表示£一（"）的各个数位上的数字之和的乙,次方，其中，当”为奇数时，4=2；

当〃为偶数时，5=3,试求嬴伉u（32"">））的值.

【答案】729

【详解】设正整数加=4々4，其中，%eN,«,>0（Z=l,2,,m）,

则工（用）=（4+生++qj三"2（mod9）,当M=323°时，工（M）三“三0（mod9）,

由数学归纳法易知，对〃eN,且“22时，恒有力（/；i（M）”0（mod9）,

^32010=91005<101005,其各位数字之和小于9x1005=9045,

贝了（323°）<9045?<9x10，，于是，力（3刈0）的各位数字之和小于9x8=72,

2010222

故为（工（3刈°））<723<400000,f3（f2（3））<（3+9x5）=48<50,

设人（a（3刈°））的各位数字和为“，

川14a<1+9x3=28,且°三力（&（3"""））三0（mod9）,

所以，as{9,18,27},故人（力"'。））=a3e{93,183,273}={729,5832,19683},

而729、5832、19683这三个数的各位数字的和分别为18、18、27,

故人(人(3刈°))e{18),27?}={324,729},

进而，/(.4(32010))e(9\183}={729,5832}

=f-,(4(32010))=182=324n%(力(32O1O))=93=729

nJ伍(3划。))=182=324n……"。凰仗”。))=729.

例2.(2019・全国•高三竞赛)设整数x、y、z满足27](x+y+z),证明：xsy(mod3),xXz(mod3).

【答案】见解析

【详解】首先，由已知条件推出X、V、z必须两两模3同余.

反证法.

®3|(x-j)=>3|(x+y+z)=>3|(2x+z)=>3|(z-x).

则3|(x+y+z),3](x-y)(y-z)(z-x),矛盾.

其次，设X、外z关于模3的余数互不相同.此时，27|(x+y+z)矛盾.

因此，万、八z必须两两模3同余.

从而，I+£_L2应2y.

k=\akk=l\<=l7

例3.(2019・全国•高三竞赛)四位数小和〃互为反序的正整数，且m+〃=18Z+9(A€N)〃?、〃分别有16

个、12个正因数(包括1和本身)，”的质因数也是小的质因数，但〃的质因数比加的质因数少1个，求切

的所有可能值.

【答案】〃?=1998

【详解】设〃?=abed，a"H0.则〃=deba-

由=9(2Z+1),则9](机+〃).

故9[(1000a+100〃+10c+d)+(1000d+100c+10〃+a)],9|2(a+/>+c+J),9K“+b+c+4).

于是，9|/n,9|n.

由帆+〃为奇数，知m与〃一奇一偶.

若〃为偶数，即2|〃，则2加，用为偶数.矛盾.

因此，团为偶数，”为奇数.

记方分解质因数后，3的个数为四,2的个数为a?.则%之2,a2>l.

由因数个数定理得[(%

于是，(0,4-1)18,a,+l>3.

所以，/+1=4或8,%=3或7.

故小至多有三个质因数.

于是，”至多含有两个质因数，3是鼠的一个质因数.

若〃只有一个质因数，则这个质因数为3.从而，«=3">10000,与"是四位数相矛盾.

因此，〃含有两个质因数.

设"的另一个质因数为P.

因为外〃，所以，〃=3"3或33P2或35P(/?>3).

故加=2%3"p%(%、%、a,eM，).

X(«2+l)(«i+l)(a3+1)=16,则因=3,a2=a3=1,即加=54p.

由"21000,知p219.

此时，32P3的值大于9999.

当0=19时，33P②=9747.

而机=54p=1026不互为反序数，于是，p*23.此时，33p2>9999.

7%2

因此，〃=3'p.于是，一=一=>9m=2〃，

n9

9(1000Q+100/?+10c+d)=2(1000d+100c+10Ha),

818a+80Z?=18k/+10c.①

818。4181x9+10x9=1719V3x818.

故a<3.

因为〃为奇数，所以,。为奇数.故。=1.

由式①得

」818+8010。、818—10x9、4

d=------------>----------=4---

181—181181,

因为加为偶数，所以，d为偶数.

于是，d=6或8.

当d=6时，由式①得

880力—ll(k=2948.

因为5|(8(乃-10c),所以，"=8.

7

得助-c=63,汕=63+cN63,b>l-.

8

于是，6=8或9.

当6=8时，c=l；

当6=9时，c=9.

于是,机=1818或1998.

因为27皿，所以，〃?片1818.

乂“7=1998=2x33x37,〃=8991=3酿37符合题意.

因此，机=1998.

例4.(2021.全国•高三竞赛)对每个正整数小定义〃〃)为从1到"中所有与〃不互质的正整数的和.求证：

若〃机)=，(")且6*〃，则加-“I是合数.

【答案】证明见解析

[详解】首先计算”〃)的表达式，注意到从1到〃中所有与n互质的正整数有*(")个,并且它们是以i^n-t

的形式成对出现的，

因此/(〃)=；〃(〃+1)-；〃•(p(n)=g〃(〃+1-0(〃)).

若/(〃?)=/(〃)口.加工〃，不妨设机>〃，则〃?(根+l_eG〃))=〃(〃+]_/(〃)).①

因为14〃+1-9(〃)4〃<加，所以(孙〃)>1.

若M-"不为合数，设为质数p,则〃〃z=(Z+l)p,

①式变为(％+1)[(/+1)P+1-夕(依+1)0)]=去(3+1-0(切)).

由化4+1)=1,可设(4+1)/?+1一e((％+1)/7)=/%,切+1—姒切)=/(2+1)

其中0</<p,相减得e((A:+l)p)一9(切)=〃+/,

%=1时，*(2p)-(p-l)<p+/不合题意，所以&22,

0=2时，/=i，e”+i)p)-e(s)=/?+/左右奇偶性不同，所以p*3.

注意(p-i)M(S),(p-i)W”+i)p),因此(P-I)I(P+/).

又0</<p,p23,所以/=〃_2,所以e((Z+l)p)=2&+p+l，e(3)=2々一0+3.

若“无，则川。(切)，所以川(24一2+3),所以p=3,

所以9((Z+l)p)=29(Z+l)<2k+p+l,矛盾，

同理若pl优+1)也得矛盾，所以(p—l)e(%+l)=2Z+p+l,

(p_i)e(%)=2%-p+3,(2)

所以染+1)-好)=2,于是以%+1)和研&)恰有一个不是4的倍数，必模4余2,但研S)模4余2当且仅

当s=4,7,2r,这里q是模4余3的奇质数，〃是正整数，分别代回②知都无解.

综上，若/(加)=/(〃)且加工〃，则帆-"|是合数.

例5.(2021•全国•高三竞赛)正整数nN2,且〃的素因子个数不超过2,对于任意整数。，若则

有三a(mod〃)成立，求证：〃是质数.

【答案】证明见解析.

【详解】假设〃(其中P、夕均为质数，8分GN).

首先证明：p丰q,若”=p,(P为质数，，=。+夕).

因为(〃,a)=l,所以取最小整数使得/三1(modp，)(易知3为。对模/的阶).

又a""'-1(modri)。a"~'--1(modpy),

所以5M(p，)=s-i)*，a(D=bi(p，-i),所以引p-i.

取a=p，三(1一p'T)'''三_p'T(p_l)+]三p"'+1(modpy)，矛盾.

所以〃wp,npw夕.

任取与P、4互质的。，

由Euler定理知：五)三1(mod〃),双〃)=(p〈p°q°)=(p-1)(4-1).

从而S|(p—1)(4—1),又因为6|(〃-1)=>5](PZ"-1),

所以5|(p。产+paT/-paT产-1).所以，…尸八严，尸t=1(mod”),

所以三](modp"),所以^'-'=1(modpa).

同理4-八『1(010£1/).

不既设P>q,则P一定是奇质数.因此它存在原根g,满足g■壬i(modpa).

因此，一定存在整数改，使得4函"+g,取a="+g,矛盾！

结合“22,知”只能有一个质因子，即〃是质数.

又由Fermat小定理知，当〃为质数时，满足题意.

111H+1

例6.(2019•吉林・高三校联考竞赛)求所有的正整数小使得方程=+=++==〒有正整数解.

玉X2X”Xn+]

【答案】{〃€乂|九.3}.

【详解】当〃=1时，方程变为4=W，得%=&,显然无正整数解.

[13

当〃=2时，方程变为7+7=7，得(々占)2+(%W)2=3(%々)\

人1]人24R

先证引理：〃+〃=3c、2无正整数解

假设有一组正整数解a7、c,不妨设a、b、c•的最大公因数为1.

由a、b为正整数,知a?=0或\{modi),b2=0或l(modi).

又3c2s0(mod3),故a?三0(mod3)H.b2=0(mod3),

即a三(Xmod3)且方三0(mod3),从而c三0(mod3).

这与“a、氏c的最大公因数为1”矛盾.

引理得证

由“2+b2=3c2无正整数解，可知此时原方程无正整数解.

_1114,

当〃=3R寸，方程变为=+=+==由3?+4?=5"得

苍毛毛毛

324252

(3x4x5)2(3x4x5)2一(3x4x5)?’

1I1]1_1

lI|J20F+lF=12r，所以20\22+152/22一百，

可得刀(乔+丘》152.122=可，即备+肃+五*=春’

故一U-U'j

40023OO21802288”

这说明原方程有正整数解：石=400,马=300,刍=180,5=288.

111H+1

当定4时，—+—++F=F"有正整数解：

XX2Xn玉+1

%!=400,x2=300,x3=180,x4=x5==xtl=xn+1=288.

综上，当片1或〃=2时，原方程无正整数解；当九23时，原方程有正整数解.

即所求的〃为｛〃wN,1〃..3｝.

例7.(2019・上海•高三校联考竞赛)求证：不存在无穷多项的素数数列R,幺，，p“，，使得

=54+4，k=l,2,.

【答案】见解析

【详解】用反证法.假设存在满足题设的无穷多项的素数数列由，。2，，P“，，

则由Pk+t=5pk+4得pk+i+1=5(4+1),

于是数列｛pk+1｝是以5为公比的等比数列，所以以+1=5*T(月+1),

故0=51(0+1)-1次=1,2,.

易知数列｛〃〃｝是严格递增的，不妨设〃/>5(否则用p2作为首项)，则有(5,p/)=l,

于是由费马小定理得夕「11(modpj,

所以4=5"T(P1=+5“T-1=0(mod/7,),

这与P。,是素数矛盾

所以，满足题设的素数数列不存在.

例8.(2023•全国•高三专题练习)试证明对函数yupf+qx+r应用拉格朗日中值定理时所求得的点&总是

位于区间的正中间.

【答案】证明见解析

【分析】不妨设所讨论的区间为口，勿，则由拉格朗日中值定理可得/⑹=噌二^外，代入化简即可证明.

b-a

【详解】证明：不妨设所讨论的区间为3,3，则函数y=px2+qx+r在5,句上连续,

在(0力)内可导，从而有

b-a

即(请+效+-)-"+«+「),

b-a

解得g="，结论成立.

例9.(2023•全国•高三专题练习)已知函数〃幻=/在区间［1,2］上满足拉格朗日中值定理的条件，试求满

足定理的久

【答案】十(1,2)

【分析】由拉格朗日中值定理可知，/©=弋一/⑴,解方程即可得出答案.

2—1

【详解】要使解©=/;二⑴,

只要"3=15=4=后，从而岑=后€(1,2)即为满足定理的久

例10.(2021•全国•高三竞赛)对于正整数n,记〃・«!-(-1)"与/+〃_(_］)"的最大公因子为d(高，若d(〃)>1,

则称”是奇异的.证明：若〃是奇异的，则1也是奇异的.

【答案】证明见解析.

【详解】记(〃•”!-(-1)”,〃2+〃-(_1)")=或〃)，我们任取4(“)的一个质因子p.

若。<〃，则p|一(T)",这不可能，故+

而“2+”-(-1)“<("+1)2,知4(")=°,

这是因为若d(〃)有两个质因子(允许相同)p、q,则/+”_(-1)"之以〃)2Pqz(〃+1)2,出现矛盾！

故d(〃)=p,且p为/+〃-(一1)"的最大质因子.

(若否，则设4为〃z+〃一(T)"的最大质因子，贝IJ/+〃一(-1)">pq>(n+1)2出现矛盾！)

故P为奇质数(因〃2+〃-(T)"为奇数)，我们记"=或〃)-〃-1=。-"-1知切与〃同奇偶.

下面我们证明：+m+

由于团2+胴+(—1)‘"三(〃+1)2-(〃+1)+(-1)"=/+〃+(—1)"=0(modp),

注意至Ijs!=(〃一九一1)(〃一〃一2)21=(〃+1)(〃+2)(〃-1)(一l)〃'(modp),

所以加•加三(p-l)!(-1)〃'三(-1)"出(modp)(威尔逊定理).

又因为加•〃三(-1)"(modp),故〃!加！三一〃!•〃(modp),

而(〃!，p)=l知：m！三t(modp).

那么三-mn=(n+V)n=(一1)"=(-l)"(modp),

即后者得证，这就说明-也是奇异的.

例11.(2019・江苏•高三校联考竞赛)设晨/、c均为正整数，证明：存在正整数“、b满足匕-a=c(〃b),

且J,[,其中(小b)表示a、b的最大公因数，r(m)表示正整数m的所有不同正因子的

\(a,b)J\,a,b)

个数.

【答案】见解析

【详解】如果m的标准分解式为加=P「'P贯成，那么7(利)=(%+1)(4+1)(«„+1).

取定两个不同的素数p、q使得(pq，C)=l.

由于(p,4)=1,利用裴蜀定理，存在正整数〃使得炉u「q&=c.

由于(pq,c)=1,那么p3＞且q①。.

由中国剩余定理，下列同余方程组：

1

ua+tq-1(modp)

…o+”三l(modq)有正整数解，=/().

1

w0+tq-1(modc)

k

^u=u„+tQq',v=v0+tttp,那么p'-q'v=c,

而且(mpqc)=1.因此(v,pqc)=l,(w,v)=l.

现在取d=pMT/T,〃=/v)则”+c=/v+c=p"w.

从而(〃,〃+c)=1.

令a=nd,b=(n+c)d,那么(“，b)=d,因此力-。=4=0(。,切.而且：

-r-(-a--)--./,=-r-(-n-<--/-)-I,=----------------k2(l2+l)/

fa]?(〃)r(力)

{a,bIl+l

户iqf

Kb)r((w+c)J)T\P

—7----r-•K=---------------K=------•空匕处用2

5)r(n+c)7(P%)

k+\

r(a)TS)卜

所以ra

(a,次3次

例12.(2018•全国•高三竞赛)已知”(〃N3,〃eN+)个两两互质的正整数4M印，为满足：可以适当添加“+”

或使得其代数式的和为0.问：是否存在一组正整数配优，也,(允许有相同的)，使得对任意正整数女，

都有A+a#也+%%,-也+《«两两互质.

【答案】存在

【详解】当〃=4时，

若仇也，也中有两个偶数，

则当女为偶数时，仇+。泼,仇+见匕，勿+4*中有两项同为偶数，不互质.

（2）若仇也，也中至多有一个偶数，则其中至少有三个奇数（不妨设为伉也力3）.

2），

考虑4,%,生,由题设其中至少有两个奇数（不妨设为01M

则当女为奇数时,々+4无也+贴,也+贴同为偶数,不互质.

当n=3时，由题意不妨设4+生=4.

因为依,生）=1,所以，由装蜀定理知存在整数乂丫使得

不妨设x>0>y.

令队=-y,b2=x,b,=4+4.则atb2-02bl=1,

a力2—a2b3=（q+a2^b2-a2（£>,+Z>2）=1,

a四一%4=4（4+4）一（4+4）a=1.

故4（伪+生女）-生佃+印）=1,

021b3+砧）-03（2+a2k）=-1，

0,（/?,+邛）-4他+%左）=—1.

因此，仇+%&,，4+44两两互质.

所以，当〃=3时，这样的整数存在.

例13.（2018•全国•高三竞赛）设“GN卡.证明：存在，〃€N.,使得同余方程x2三l（modm）至少有"个根.

【答案】见解析

【详解】对任意的奇质数P,同余方程幺三l（modp）恰有两个不同的解x三1或p-l（modp）.

任取$个不同的奇质数,其中,S为满足2,2n的正整数.

令机=［鸟R,为这s个质数的积.

考虑2’个不同的数组对生，%,其中，4€{1,〃-1}.

x=a,(modpj

x=a(modp,)

由中国剩余定理，知方程组，2有解x,,令此解满足d三l（mod/〃）,目对不同的

x三《（modp、）

（6，。2,4）,数Mq,出，《）对某个模6不同余.

从而对模，”不同余.

所以,x2三l（mod"。至少有2s>n个解.

【过关测试】

1.（2022•上海•高三校考强基计划）定义；={1,2,,p-l},其中。为奇素数.

(1)给出同余方程3f+4)*+5z'芋。(mod5)的满足x,y,zw；的一组解；

(2)(代数基本定理)设/(x)w：p[x],且deg(/)=d,求证/(x)三O(modp)在'内至多有d个解：

tp

⑶(夫e/7/m小定理)求证：Vxep,x''sl(modp)•

(4)(原根存在定理)若正整数x，z满足:£三l(modp),且VO<Zo<z,xFl(mod0,则记仇x)=z,则称z

为x在modp意义下的阶，求证：必定存在七二，有距)=2-1；

⑸求证，存在；,,都存在沙w：,；,,p|〃-况。吐川/7-A3中必有一者成立；

(6)说明当2>5时，BV+dy'+Sz'=0(modp)必有一组非零解(x,y,z)e[；'｛。｝了.

【答案】(l)x,y,z=[l,2,l]

(2)证明见解析

(3)证明见解析

(4)证明见解析

(5)证明见解析

(6)答案见解析

【分析】(1)给出x,y,z=[l,2,l],验证后符号条件.

(2)利用带余除法结合数学归纳法可证.

(3)利用完全剩余系的性质可证明费马小定理.

(4)利用代数基本定理结合欧拉函数的性质可证明该结论.

(5)记modp意义下的原根记为"，则问题可转化为同余方程组是否有解问题，取3/a,则可得存在性成

立.

(6)就3/("-1)、3|(p-l)分类讨论，后者可通过一个引理(构造有向图可证明)来证明.

【详解】(1)显然3x13+4x23+5x13=40是5的倍数，所以x,y,z=[l,2,l]：

(2)下面先证明一个引理：在4国中,若f(x)三0(modp)在内有一个根与,则(x-x0)"(.r),

引理的证明：在二；内作带余除法，

则/(x)三(x—々Jg(x)+r(modp),故〃％)三r(modp)=0(modp),

故7•三0(modp),所以/(x)三(x—%)g(x)(modp),

故在；[司中，(x-x0)l/(x).

回到原题，对次数作数学归纳法.

当4=1时，〃力有且只有个根；

假设结论对d-l成立，考虑次数为d的情况：

若/(X)无根，则命题已经成立；

若f(x)有根%,由引理，有(x-%)"(x),设g(x)=n»€p[x],

x-xo

且deg(g(x))=d-l,由归纳假设有g(x)至多有d-1个根,

故〃力至多有d个根，

由数学归纳法可得原命题成立.

(3)考虑N；(该集合为除以。后不同余数的集合)，

若re；,对任意的x壬O(modp),则有灯

又对r,se：。,任意的x羊O(modp),若r关s(modp),则p“r-s),

故p/x(r-s),故次关6x(modp),

故若x丰O(modp),则当s取遍二;,中所有兀素后，当xs取遍二；中所有元素，

所以％PTX1X2Xx(p-l)=lx2xx(p-l)(modp),

所以三l(modp).

(4)由(3)可知/㈤|(p-1),否则p—1=4,优"+r,04r<4,㈤,

故三/网三Kml(modp)，由%(%)的最小性可得r=0，故如(〃一1).

对任意\<k<p-\,定义R(A)=｛weZ；18,Xm)="，

设R㈤中元素的个数为r化),如果乂5-1)，则八小)=0；

设〃?eR(A),则〃"三l(modp),故加为4[司中多项式P(x)=f-1的•个根，

由代数基本定理，对任意的心(0-D,最多有&个剩余类"为尸(x)的根.

对于swR(A),因为/s)=3故｛1,内2,…,si｝中的元素两两相异，并且都是P")的根.

"104/4/—1,如果(，/-1)=d>1,则[，尸三1*尸三](modp)，

所以外仅)4[<衣，故厂(左)40(。，

而Z，(&)=P-1，Z"k)=p-1,

k\(p-l)H(p-D

故心=

所以必定存在fe；,有5Q)=p-l.

(5)由(4),记modp意义下的原根记为M,记“=1,6=",

30=y(modp-1)

则题设中的方程可化为a+3。三s(modp-1),

2a+36三s(modp—1)

取3/a,则上述三个方程必然有•个有整数解.

(6)任取modp意义下的原根〃，分以下两种情况讨论：

1.若31(p—l),则)同时也是modp的原根.

因为『遍历Z’,自然会使得原方程有非零解.

2.若3|(p-1),

5z3(modp)下一共有,个非零元素和元素0,

(1)存在TMCN,使得〃%"三g(modp),

则在(3V+4y3)modp下中存在这么一个元素3(-〃-+4,这个元素为0,

取z=0,构造完成.

(2)不存在meN,使得/"三：(modp),则存在〃mglmodp),

下面证明引理：如果3|(p-l),g是modp的原根，那么一定存在使得g3mg3i三igodp).

证明：假设不存在，

先考察g'-g，三l(modp),可以推出g'7-gf三l(modp),

我们规定：如果i,/e{l,2,3,,p-l}满足g；-g，三I(modp),则在盯之间连一条有向边i-/,

由前述讨论可得

1.一条0(mod3)->0(mod3)可以推出一条0(mod3)f0(mod3),设为e条.

2.一条l(mod3)fl(mod3)可以推出一条0(mod3)f2(mod3),反之亦然，所以条数一样，设为。条.

3.一条2(mod3)->2(mod3)可以推出一条0(mod3)fl(mod3),反之亦然，所以条数一样，设为方条.

4.一条l(mod3)f2(mod3)可以推出一条2(mod3)fl(mod3),反之亦然，所以条数一样，0条.

5.一条L2(mod3)f0(mod3)可以推出一条l,2(mod3)fl(mod3),分别设为c条和d条.

2a+2b+c+d+e=p-2

a+c=-----

3

故<,p-1,得到e=-l,矛盾，故引理成立

a+b——

3

,,p—l

h+d=-----

3

,4

回到原题，如果不存在〃2,〃£N，使得〃=-(modp),

设三g(modp),iw{l,2},设/为另一个余数，

由引理，一定存在九，2tN,使得〃3M—〃3"=i(modp),

故1+g=〃3j,+/(modp),

考察3〃°+4x0,3/?+4x0,,3〃1+4x0(1),

3〃°(1+§〃“2)+4X0,3〃3(I+§〃3A)+4X0,,3^-4(l+-//3j2)+4X0(2),

4〃°+3x0,4"+3x0,,+3x0(3),

这3组数(modp)互不相同且没有•个元素modp为零，元素个数为

一定存在z使得原命题条件成立.

2.(2020.北京.高三强基计划)求证：对任意正整数鼠均存在〃为&的倍数，且〃的十进制表示以2020开

头.

【答案】证明见解析

【分析】利用代数基本定理及抽屉原理可证该命题成立.

【详解】设4=25"，共中PM/eN,g10)=1./(*)=1000010000^-

上个］0000

则数列/⑴,/(2),…中必然存在两个数模r同余，

设为，"，〃且r"(M—/(〃)，进而

进而-2020/0』(〃,")-/(〃))，而后者的十进制表示以2020开头，命题得证.

3.(2021・江苏・高三强基计划)求能使2〃(〃+1)(”+2)(〃+3)+12表示为两整数平方之和的所有〃的值(〃©；7).

【答案】不存在两整数平方之和为2〃(n+1)("+2)(〃+3)+12,

【分析】根据整除性的性质可得“(“+1)(〃+2)("+3)必为8的倍数，假设存在两整数x,y满足条件，通过讨

论其奇，偶证明满足条件的数不存在.

【详解】V对于任意的〃eN,"5+1)5+2)(”+3)是四个连续自然数之积，所以必为4的倍数，又12为4

的倍数,故2〃(〃+1)(〃+2)(〃+3)+12必为4的倍数，

设2〃(〃+1)(〃+2)(〃+3)+12可表示为两整数x,y的倍数和，

若X=2/M+1,F二4%时,+y2=4/n2+4m+4k2+4k+2,

此时f+y2不是4的倍数，矛盾，

若x=2，?i+l,y=24时，x2+y2=4m2+4m+4Z:2+1,

此时9+),2不是4的倍数，矛盾，

若x=2m,1二B't，J?+y2=4机2+4%2+4%+i,

此时V+,2不是4的倍数，矛盾,

当x-2m,y=2左时，x2+y2=4nr+4k2,

m2+k2=—M(«+l)(n+2)(M+3)+3,

2

同理讨论m，k的奇偶可得》?+为被4除的余数可能为0,1,2,

而n(«+1)(〃+2)(〃+3)必为8的倍数，所以gn(n+1)(〃+2)(〃+3)+3被4除的余数为3,

故不存在满足条件的机，％使得等式成立，

即不存在两整数平方之和为2〃(〃+1)(〃+2)(〃+3)+12,

4.(2021・全国•高三竞赛)设M"为”个正整数，并且满足q+生++4”=2”,令%+；=q,i=l,2,,

并记S”.”=《,+J++4.1，("#=1,2,).求证：对于任意AwZ’,必存在正整数“、v,使得黑“，等于A

或4+1.

【答案】证明见解析

【分析】因为=1,2,,所以为以〃为循环节，从而染2〃，对于很大的数A,我们只需

要循环相加即可得到，所以只需证明Aw[l,2〃],存在正整数“、V,使得鼠，，等于A或A+1,新定义一个

数%=<+%++40=1,2,3,,〃)，接下来分类讨论，当2〃个数々也，,b„,b,+A,b2+A,也+A不是模2〃

的完系，当2〃个数〃也,也在+4+1,也+A+1不是mod2〃的完系时,找到相应的数S…等于A或A+1,

若上述两组数均是mod2w的完系，证明不成立，证毕.

【详解】证明:因为4+生++a„=2n,所以S…,=%+2〃,从而不妨设1WA42”.

记4=4+%++q(i=1,2,3,

下面分情况讨论：

(i)若2〃个数4也，,也，A+A也+A也+A不是模2〃的完系，则由于々也，，"mod2”余数互不相同，

所以4+A也+A,,2+A模2〃的余数也互不相同，故必存在i,j,使得%三%+A(mod2〃).

如果，>/,则有S-=A.

如果i=/,则有A三0(mod2n)=>A=2〃=S”,=A.

如果则〃Ybj+A44〃，知2+2〃=4+A,即5月,“_川=4.

均满足条件.

(H)若2〃个数4也，,也M+4+L也+A+1不是mod2〃的完系时，同理可知满足条件.

(iii)若上述两组数均是mod2〃的完系，则

4+&+-+b=+(4+A)++(b“+A)

三伪++A+1)++(勿+A+1)(IYKX12〃)

=0三”(mod2”)矛盾.

综上，证毕.

【点睛】数论的基础题目，要结合题干中的条件缩小讨论的范围，一般使用数论的四个基本定理来解决问

题.

5.(2021•全国•高三竞赛)已知4={4，生，，%0},3=他也，，4°J是两个整数集合，且对于任意整数〃，存

在唯一的qeA，%eB使得"4+%(mod2020),记(")A=q,(%=%.证明：对任意的ae存在

ak&A,使得a=(1()1%+助.

【答案】证明见解析

【详解】考虑满足(项+9++玉0[+6)4=。且演,々,「，占0|wA的所有有序数对(为,々，，%|)构成的集合X.

要证结论等价于：

“存在(办,孙，为oJeX且西=々•=占01."①

对任意整数(定义映射g：A-A,g(q)=(q+/〃)A.

引理：8是双射.

设g(4)=g㈤,即(《+4=(%+矶.

再由q+优=(勾+加)]+(4+机•，%+"7=(%+6)t+(4+'")/'，

得4+(勺+，*=%+(4+m)B.

由题设中唯一性得4=%,所以g是单射.A是有限集，

所以g是双射.引理得证.

对任何固定的芭，多,,西0neA,令机=%+%++x100+Z),

由引理，存在唯一的(工,孙，,和JwX使得机=X|+x?++xm+b,

因此IX|=|Af00=20'°°.

另一方面，任取(X|,&,,XIOI)GX,设％,当，，工侬,办"中包含q个可(1V”2O),

101!..

任意交换为，%,的顺序，得到的有序数对(共》0।个)仍然是X的元素，所以|X|是一些

1•%0•

101!

Q；类型的整数之和.

d♦%,

|X|=20i°°不是101的倍数,而101为质数,

所以存在某个(5,9，,与JwX使得》Q：不是101的倍数，

即且(14420)中有一个为101,其余为0,即％=七==x”>i

.至此，结论①得证，从而题中结论成立.

6.(2021.浙江•高三竞赛)已知素数。，4满足P=2q+1.证明：存在正整数机使得〃火的十进制表示的各位

数字之和是2或3.

【答案】证明见解析

【详解】。=2,3不合题意，若P=5则取，叩=110即可.下面假设pN7.

由费马小定理H10^-1=吁—l=(1071)(l(T-l)可知p|104+l或印0，-1.前者意味着取叫=10。+1满足

条件.若是“10"-1,我们断言A={100,10',102,…,102}中的数模。两两不同余，即有夕个不同的余数.

这是因为若有10"三10ft(modp),(04a<6“7)则1(T“三l(modp),由匕—a与q互素以及裴蜀定理知存

在正整数“，v使得"(b-a)-vq=l,这样

1=(io4-0)M=lO^1=(10»)pX10(modp).

这意味着p|10-l=9即p=3,不合题意因此A={100』01102,…,10"。中的数模，两两不同余.设它们的余数

是8={d…,％}={1,2,…,p-1}.

我们考虑下面的，个余数对，它们覆盖了除了0,1,，，P-2,P-1之外的所有余数：

(2,p-3),(3,p-4),(勺^，苫^)

若某个对子的两个余数都在B中出现，不妨设10"三％，10"三p-1-无，则在=10。+106+1是P的倍数，满

足题意.

若每个对子中的余数都在B至多出现一个的话，由于忸卜，■,所以0,1,，，P-2,2-1在B中出

现至少两个，已知leB,OiB,其余三个余数，，P-2,至少有一个在B中出现.

若与LB,即有某个10"三匕口，则〃?p=2xl0“+l满足题意.

22

若p-2eB,即有某个10"三p-2,则，叩=10"+2满足题意.

若p-leB,有某个10“三p_i,贝I]"7P=10"+1满足题意.

综上所述，存在P的倍数的十进制数字和是2或3.

7.(2021•浙江•高三竞赛)给定素数。25.称1,2,…，P的排列(。“4,…,4)为“好排列”，如果对％=1,2,

。均有并且q+2%+…+/吗是P的倍数.求“好排列，，的个数除以22_夕的余数

【答案】除以/-P的余数是

【详解】解：把排列看成是P={12…,p},以到自身的置换(一一映射)/：尸一P.“好排列”即没有不动

点(即对x=l,2，…，P均有旦5(/)=Z：N(x)=0的好置换九(本题所有同余均为mod。意

义).

设所有好置换构成集合〃.我们按照/(P)的取值把M分成个部分

MMB'DBZU…DB.T，Bk-[f&M,f[p)=k\,k=l,2,…，p-1

我们想实现纥之间的对应，为此考虑对置换f进行操作：

Z，(.f)(x)=4(aTx),a=l,2,p-\

若/wM,即/没有不动点并且5(7)三0,则7；(/)亦没有不动点，同时

p2p

S(方⑺)=f何⑹*)=a±a-'kf(a'k)=a2s⑺=0