高中竞赛数学辅导：数论重要定理

NO.*

1N0.* 数论

一 、欧拉定理

设1m的整数，,1,1mamamodm则.

例1 设1000526x，求x的末三位数.

解 由二项式定理，

100010002499500100029983499639982331000100010005265262552352352323CCC是一个正整数.

记10001526x，因为105261,01,x所以从而

11xx.

而1xx是一个正整数，则11,xx所以1111.xxx

于是

又因为

500100031252251000xxmod，

33100025，

50010002500325252122mod，

又

所以

3528ymod， 25528ymod，

528ymod，

则

28minymod，

所以

则

因为

所以 NO.*

2N0.* 10010021125,31125modmod，

于是，有

150050021125,31125modmod，

50032232125mod，

又因为

15015002308mod，

5003322552y，

所以

35208ymod，

即

528ymod，

所以

68minymod，

于是，有

86yk.

所以

所以

11250751111000xxxmod.

故x的末三位数是001.

二、费马小定理

（1）p为素数，且,1,ap则

11pamodp；

（2）p为素数，则

paamodp.

例2 ,,,abcd为整数，证明

44240/bdcdaa.

证明 4240235， NO.*

3N0.* 由于

所以

444403bdcddbcaaaaamod.

即

443/()bdcdaa.

由于奇数的4次方被16除余1，偶数的4次方被16除余0，故有

4444016bdcddbcaaaaamod.

即

4442/()bdcdaa.

又由于

则

444405bdcddbcaaaaamod，

即

445/()bdcdaa.

又2,3,5两两互素，故44240/bdcdaa.

例3 设整数199919991999,,0,abcabcdabc满足记，求证d不是素数.

证明 由于1999aa与同奇偶，则

所以

19991999199902dabcabcmod，

即

2/d.

又

389333aaaaaamod，

同理

则

19991999199903dabcabcmod.

即3/d. NO.*

4N0.* 从而d不是素数.

例4 设21npnn是给定的素数，证明：数列中有无穷多项被p整除.

证明 当2p时，结论显然成立.

当1221,21pppmodp时，由于，所以，所以对任意的1,21pmmZmodp有，即121mpmodp.特别地，取1,mkpkZ.则

112111kppkppmodp.

令11,nkpp则2nnmodp，即/2npn.

三、威尔逊定理

设p是素数，则

1!1pmodp.

证明 考虑多项式1pxmodp.

由费马小定理，当1,2,,1ap时，有

所以11pax是多项式的根.则1,2,,1xxxp均为

11px的因式.则设

11121pxxxxpQx=.

得1Qx，则

11121pxxxxp=.

取xp代入，得

所以

1!1pmodp.

例5 1!1ppmodp是素数，则.证明：若21p为奇素数，NO.*

5N0.* 则

2!1021ppmodp.

证明：2!1021ppmodp

2!121pmodp.

而21p为奇素数，有2!121pmodp.

四、中国剩余定理

设12,,,kmmmk是个两两互素的正整数，则同余方程组

有整数解.令12.kMmmm

则同余方程组在模M下的解是唯一的.

令,iiiMMMm取使得

1iiiMMmodm，

则解为

111222kkkxMMbMMbMMbmodM.

例6 证明：对任意给定的正整数,nn均有个连续正整数，其中每一个都有大于1的平方因子.

分析：

则

2122212nxmodpxmodpxnmodp.

证明： 设12,,,npppn为个互不相同的素数，由中国剩余定理

存在正整数解，设S为一个正整数解，则12SSSn，，，满足要求.

例7 任给正整数n，存在n个连续正整数，使得其中每一个数都不

是幂数. NO.*

6N0.* 证明 设12,,,npppn为个互不相同的素数，由中国剩余定理，同余方程组

存在正整数解0000,12SSSSn则，，，满足要求.

例8 给定正整数n，设fn是使1fnkk能被n整除的最小正整数.证明：当且仅当n为2的幂时，有21fnn.

分析：112mkmmk，因为1/,2mmn当21mn时，

1mkkn/，所以21fnn.

则问题归结为：

证明：（1）当2mn时，2112122nknnk.

当1121.2rkrrrnk时，

∵112,12122121mmrrnrrn即，

∴112/1,2/mmrr.

∴112/,/.22mrrrrn即

综上，知21fnn.

（2）分析：2121,fnnrn使1/,rknk即1/2rrn.

（证明）

2mn当时，令21.mnaa为大于的奇数此时需证12/1marr，即证存在12/,/1mrar即可.

构造同余方程组

1021mxmodxmoda （1） NO.*

7N0.* 由中国剩余定理知，同余方程组（1）有正整数解12rrn，则

12/,/1mrar.从而有12/1marr，即12/2mrra，

1/2rrn.

考虑r的取值范围：

若2,020,rnrmodnrmoda则这与

1xmoda相矛盾，故2rn.

若121,1212mrnrmodnrmod则，这与

102mxmod相矛盾,故21rn.

从而有12221rnn，于是得证21,rn使1/2rrn.

五、阶及应用

定理1 设1,,,1nnaan为整数，且，则必有一个r

1ramodn.

证明： 011,,,naaa均与n互质，所以有

0,0,1,,1iamodnin.

由抽屉原则，,01,ijijn满足使得

jiaamodn，

1jiamodn，

令,11,1rrjirnamodn则有.

定义1：设,1,1manamodnma则满足的最小正整数叫做

an对模的阶.

注：若anr对模的阶为，则 NO.*

8N0.* 1ramodn.

当11iiramodn时，.

定理2 设,1,,1mananramodn对模的阶为若，则/.rm

证明：令110mqrrrr，则

1111qqrrrrrmqrraaaaaaamodn.

而1mamodn，所以11ramodn.而anr对模的阶为的定

,义知10r.

从而,/.mqrrm即

推论：若anr对模的阶为，则

/rn.

特例：当n为素数p时，/1rp.

例9 设1,/21,3/.nnnn证明：

证明：显然n为奇数.

假设3.pnp为的最小素因数，下证

∵/21nn，

∴210nmodn， 21nmodn，

∴2221,21nnmodnmodp.

设2/2.prrn对模的阶为，则 ①

又由小费马定理知，121pmodp，

∴/1rp. ②

由①，②知，/2,1rnp.

∵2/,n