第五节初等数论中的几个重要定理

sss第五节

初等数论的几个重要理基知定（拉(Euler)函）一组数

xx,,x称是模1s

m

的既约剩余系，如果对任意的j

，(,m)j

且对于任意的

若

(a

＝则有且仅有一个

j

是

对模

的剩余

a)定义j

(){1,2,,m}中和m互的数的个数)称为欧拉（）函数。这是数论中的非常重要的一个函数然

而于m)

就是„

中与

m

互素的数的个数，比如说

是素数，则有

(

。引：

m

1－可容斥定理来证（证明略PPP质数定1拉（Euler）定理）设

(a,

＝，

m

1(mod

。证明取模

m

的一个既约剩余系

,,(12s

())

考虑

ab1

,于与s互，故j)仍m互，且有ji

ab(j)j

，于是对每个j

都能找到唯一的一个

(j)得abjj

(mod)

种应关系是一一的，从而

)jjjj

)(mod)，s())(mod)jjjjjj

。(b，aj

s

1(modm，a

m

1(mod

。证毕。j分析与解答：要证

m)

1(mod)

，我们得设法找出

)个相，由)

个数我们想到

,

中与

互质的)

的个数：

a,12

a

，由于

(m

＝1，从而aa,aa12m)

也是与

互质的m

个数，且两两余数不一样，故12)

aa1

,aa)

a

)

12)

（modm），（

12)

m

）＝1，故

m)

1(mod

。

定2费马Fermat）小理对于质数及意整数有

p

)

。设

为质数

a

是

的倍数

p

0a(mod

a

不是p

的倍数(a,p由引理及欧拉定理得

)

1(modp

，p),p(mod)

，由此即得。定*推：设为质数，是与p互质的任一整数，

p

1(modp

。定3威尔（）定）p

为质数，则

(1(modp)

。分析与解答：受欧拉定理的影响，我们也找个，然后来对应乘法。证明：对于

(,)，,2x,(px

中，必然有一个数除以

余1，是因为x,2x,(p

则好是

的一个剩余系去0。从而对

{1,2,p,使得xy1(mod)

；若

xyxy(modp，(x)，x)|(y)22

，故对于

y,y,，有xy21

xy(modp)

。即对于不同的x对于不同的y，1,2,,p

中数可两两配对，其积除以

余1，后有

，使

x

2

1(mod)

，即与它自己配对，这时

x20(mod)

，

(0(mod)

，

x

或

x1(modp

，x

或

x

。除

xp

外的可两两配对除

余1()

。定义：设

f(xj

为整系数多项式（

j

，我们把含有x的一组同余式f(x)0(mod)jj

（

j

）称为同余方组程。特别地，当

f(x)i

均为

的一次整系数多项式时，该同余方程组称为一次同余方程若整数

同时满足：

f()m)jjj

，则剩余类

M{x|,xm)}c

（其中

m,,,m]1k

）称为同余方程组的一个解，写作

x(modm定4中剩定）设

,,12

k

是两两互素的正整数，那么对于任意整数a,，次余方程组12

(mod)，1jjj

必有解，且解可以写为：

i12k，i12k，MNNaN(modm1122k这里

mm，)mi

，以及N满MNm)，1jjjjj（即

j

为

M

j

对模

m

j

的逆中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。定5拉格日理设p

是质数，

n

是非负整数，多项式

f()n

0是一个模为n次整系数多项式（即p同方程n解（在模有意义的情况下

f(x0(modp)

至多有个定6：若l为a模m的，s为一正整数，满足

s

1(modm，则必l的数。以上介绍的只是一些系统的知识法经在解决数论问题中起着突破难点的作用外还有一些小的技巧则是在解决考问题中起着排除情况助分析等作用有时也会起到意想不到的作用，如：

n

2

为奇数时0(mod9)3整时20(mod4)为偶数时0(mod3)n时

。这里我们只介绍几个较为直接的应用这些定理的例子。典分例1.设

)

，求证：

91|12

。证明：因为

91

，故由

(91,)

知

)

，从而

(7,a1,(13,)

，但是6,

(13)

，故由欧拉定理得：

12

a

6

)

2

2

1(mod7)

，

12

1(mod13)

，从而

12

；同理，

。于是，

12

12

0(mod91)，(

12

12

)

。注明：现考虑整数a的an所的数列：

,a

2,,若正整数使ak

)

，则有

nrm

，其中

kq,0r

；因而关于

m

列

a2,,a,

的项依次同余于

,a2k,,a,ak,a这个数列相继的项一段，各段是完全相同的，因而是周期数列。如下例：例．试求大于100且使

(3

n

成立的自然数的。解：通过逐次计算，可求出3关mod11的小非负剩余（即为被11除得的余数）为：

992

3

5(mod11),3

4(mod11),3

因而通项为的列的项的最小非负剩余构成周期为周期数列：3，9，，，，，，，，，„„„类似地，经过计算可得

n

的数列的项的最小非负剩余构成周期为10的周期数列：7，5，，，，，，，，，„„„于是由上两式可知通项为

nn

的数列的项的最小非负剩余，构成周期为（即上两式周期的最小公倍数）的周期数列：3，7，，，，，，，，，„„„这就表明

时仅当

n

时n

0(mod

n

n

；又由于数列的周期性，故当k

时，满足要求的

n

只有三个，即4,10k从而当时，足要求的

n

的和为：kkk下我着对Fetmat小定理其用举：

.例．求证对于任意整数

，

117x5315

是一个整数。证明令

f(x

117x35315

x

则需证

f(x)3

x

x

是15的数即可。由3，是数及Fetmat小定理

x

5，x

x(mod3)

，则x

5

x

3

x

；

x

5

x

3

xx0(mod3)而（3，），故

x5x15)

，即

f(x)

是15的数。所以

f(x

是整数。例．求证

2730|13

（为意整数证明：令

f()n

13

，则

f()n(nn

2

n

2

n

6

；所以

f(n)

含有因式

5,3,n2由小理，知13|

13

7

,5|n

5

,3|n

3

,2

2

又13，，，，两两素，所以2730=

13能整除n

13

。例．设

,bc

是直角三角形的三边长。如果

c

是整数，求证：abc可被30整除。

22222222222222证明：不妨设

是直角三角形的斜边长，则

c22

。若2

a

，

b

，，则

c

2

2

2

，又因为

c

2

1(mod2)

矛盾！所以

abc

.若3

a

，3

b

，3

c因为

(321(mod3)

，则

22(mod3)

，又c

2

，矛盾！从而3|.若5

a

，

b

，，因为

(5

2

，

2)

2

1(mod5)

，所以

2

或0(mod5)与

c21(mod5)

矛盾！从而abc.又2,3,5)=1，以30|.下面讲述中国剩余定理的应用例．证明对于任意给定的正整数

n

，均有连续

n

个正整数，其中每一个都有大于1平方因子。证明由素数有无穷多个故们可以取n互不相同的素数

,,p1

n

而虑同余组x

2

i,

①因为

p,,p1n

显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。于是，连续

n

个数

xx,x

分别被平方数

,,p12n

整除。注本的解法体现了中国剩余定理的一个基本功效，它常常能将“找连n个整数具有某种性质”的问题转化为“找个两两互素的数具有某种性质后者往往是比较容易解决的。（2）本题若不直接使用素数，也中以采用下面的变异方法：由费尔马数Fk

k

两两互素故①中的

2i

转化为

Fi

2

in)

后相应的同余式也有解，同样可以导出证明。例．证明对于任意给定的正整数n，有连续个正整数，其中每一个都不是幂数。分析：我们来证明，存在连n个正整数，其中每一个数都至有一个素因子，在这个数的标准分解中仅出现一次，从而这个数不是幂数。证明：取

n

个互不相同的素数

,,12

n

，考虑同余组

xp),i,n因为

,,p12n

显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。对于

1为i

2i

)故p

2i

|()

但①式可知

p2i

()即p在i()

的标准分解中恰好出现一次，故

xxx

都不是幂数。

aa例．设

是给定的偶数，

n

且

k(n

是偶数。证明：存在整数x,y

使得

(,)y,)

，且

xykn)

。证明：我们先证明，当

n

为素数幂

时结论成立。实际上，能够证明，存在x

使

且

xy

：若

，则条件表明

为偶数，此时可取

x

；若p，则y与x2,y

中有一对满足要求。一般情形下，设n12r

r

,i1,2,,r

是

n

的一个标准分解，上面已经证明，对每个

i

存在整数

xyi

i

使得

xii

i

且

x(ir)ii

，而由中国剩余定理，同余式

iii

,r)

①有解

，同余式i

ii

ir)

②有解y。现不难验证解x,y

符合问题中的要求：因

ii

i

，故

i

(i1,2,r)

，于是

(,n)

，又由①②知

i

(mod)(iii

1,2,,r

，故

xykn)

。注此的论证表现了中国剩余定理