sss第五節(jié)

初等數(shù)論的幾個重要理基知定（拉(Euler)函）一組數(shù)

xx,,x稱是模1s

m

的既約剩余系，如果對任意的j

，(,m)j

且對于任意的

若

(a

＝則有且僅有一個

j

是

對模

的剩余

a)定義j

(){1,2,,m}中和m互的數(shù)的個數(shù))稱為歐拉（）函數(shù)。這是數(shù)論中的非常重要的一個函數(shù)然

而于m)

就是?

中與

m

互素的數(shù)的個數(shù)，比如說

是素數(shù)，則有

(

。引：

m

1－可容斥定理來證（證明略PPP質(zhì)數(shù)定1拉（Euler）定理）設(shè)

(a,

＝，

m

1(mod

。證明取模

m

的一個既約剩余系

,,(12s

())

考慮

ab1

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

ab(j)j

，于是對每個j

都能找到唯一的一個

(j)得abjj

(mod)

種應(yīng)關(guān)系是一一的，從而

)jjjj

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

。(b，aj

s

1(modm，a

m

1(mod

。證畢。j分析與解答：要證

m)

1(mod)

，我們得設(shè)法找出

)個相，由)

個數(shù)我們想到

,

中與

互質(zhì)的)

的個數(shù)：

a,12

a

，由于

(m

＝1，從而aa,aa12m)

也是與

互質(zhì)的m

個數(shù)，且兩兩余數(shù)不一樣，故12)

aa1

,aa)

a

)

12)

（modm），（

12)

m

）＝1，故

m)

1(mod

。

定2費馬Fermat）小理對于質(zhì)數(shù)及意整數(shù)有

p

)

。設(shè)

為質(zhì)數(shù)

a

是

的倍數(shù)

p

0a(mod

a

不是p

的倍數(shù)(a,p由引理及歐拉定理得

)

1(modp

，p),p(mod)

，由此即得。定*推：設(shè)為質(zhì)數(shù)，是與p互質(zhì)的任一整數(shù)，

p

1(modp

。定3威爾（）定）p

為質(zhì)數(shù)，則

(1(modp)

。分析與解答：受歐拉定理的影響，我們也找個，然后來對應(yīng)乘法。證明：對于

(,)，,2x,(px

中，必然有一個數(shù)除以

余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

中數(shù)可兩兩配對，其積除以

余1，后有

，使

x

2

1(mod)

，即與它自己配對，這時

x20(mod)

，

(0(mod)

，

x

或

x1(modp

，x

或

x

。除

xp

外的可兩兩配對除

余1()

。定義：設(shè)

f(xj

為整系數(shù)多項式（

j

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

（

j

）稱為同余方組程。特別地，當

f(x)i

均為

的一次整系數(shù)多項式時，該同余方程組稱為一次同余方程若整數(shù)

同時滿足：

f()m)jjj

，則剩余類

M{x|,xm)}c

（其中

m,,,m]1k

）稱為同余方程組的一個解，寫作

x(modm定4中剩定）設(shè)

,,12

k

是兩兩互素的正整數(shù)，那么對于任意整數(shù)a,，次余方程組12

(mod)，1jjj

必有解，且解可以寫為：

i12k，i12k，MNNaN(modm1122k這里

mm，)mi

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

j

為

M

j

對模

m

j

的逆中國定理的作用在于它能斷言所說的同余式組當模兩兩互素時一定有解，而對于解的形式并不重要。定5拉格日理設(shè)p

是質(zhì)數(shù)，

n

是非負整數(shù)，多項式

f()n

0是一個模為n次整系數(shù)多項式（即p同方程n解（在模有意義的情況下

f(x0(modp)

至多有個定6：若l為a模m的，s為一正整數(shù)，滿足

s

1(modm，則必l的數(shù)。以上介紹的只是一些系統(tǒng)的知識法經(jīng)在解決數(shù)論問題中起著突破難點的作用外還有一些小的技巧則是在解決考問題中起著排除情況助分析等作用有時也會起到意想不到的作用，如：

n

2

為奇數(shù)時0(mod9)3整時20(mod4)為偶數(shù)時0(mod3)n時

。這里我們只介紹幾個較為直接的應(yīng)用這些定理的例子。典分例1.設(shè)

)

，求證：

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

)

。注明：現(xiàn)考慮整數(shù)a的an所的數(shù)列：

,a

2,,若正整數(shù)使ak

)

，則有

nrm

，其中

kq,0r

；因而關(guān)于

m

列

a2,,a,

的項依次同余于

,a2k,,a,ak,a這個數(shù)列相繼的項一段，各段是完全相同的，因而是周期數(shù)列。如下例：例．試求大于100且使

(3

n

成立的自然數(shù)的。解：通過逐次計算，可求出3關(guān)mod11的小非負剩余（即為被11除得的余數(shù)）為：

992

3

5(mod11),3

4(mod11),3

因而通項為的列的項的最小非負剩余構(gòu)成周期為周期數(shù)列：3，9，，，，，，，，，???類似地，經(jīng)過計算可得

n

的數(shù)列的項的最小非負剩余構(gòu)成周期為10的周期數(shù)列：7，5，，，，，，，，，???于是由上兩式可知通項為

nn

的數(shù)列的項的最小非負剩余，構(gòu)成周期為（即上兩式周期的最小公倍數(shù)）的周期數(shù)列：3，7，，，，，，，，，???這就表明

時僅當

n

時n

0(mod

n

n

；又由于數(shù)列的周期性，故當k

時，滿足要求的

n

只有三個，即4,10k從而當時，足要求的

n

的和為：kkk下我著對Fetmat小定理其用舉：

.例．求證對于任意整數(shù)

，

117x5315

是一個整數(shù)。證明令

f(x

117x35315

x

則需證

f(x)3

x

x

是15的數(shù)即可。由3，是數(shù)及Fetmat小定理

x

5，x

x(mod3)

，則x

5

x

3

x

；

x

5

x

3

xx0(mod3)而（3，），故

x5x15)

，即

f(x)

是15的數(shù)。所以

f(x

是整數(shù)。例．求證

2730|13

（為意整數(shù)證明：令

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

。例．設(shè)

,bc

是直角三角形的三邊長。如果

c

是整數(shù)，求證：abc可被30整除。

22222222222222證明：不妨設(shè)

是直角三角形的斜邊長，則

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|.下面講述中國剩余定理的應(yīng)用例．證明對于任意給定的正整數(shù)

n

，均有連續(xù)

n

個正整數(shù)，其中每一個都有大于1平方因子。證明由素數(shù)有無窮多個故們可以取n互不相同的素數(shù)

,,p1

n

而慮同余組x

2

i,

①因為

p,,p1n

顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)

n

個數(shù)

xx,x

分別被平方數(shù)

,,p12n

整除。注本的解法體現(xiàn)了中國剩余定理的一個基本功效，它常常能將“找連n個整數(shù)具有某種性質(zhì)”的問題轉(zhuǎn)化為“找個兩兩互素的數(shù)具有某種性質(zhì)后者往往是比較容易解決的。（2）本題若不直接使用素數(shù)，也中以采用下面的變異方法：由費爾馬數(shù)Fk

k

兩兩互素故①中的

2i

轉(zhuǎn)化為

Fi

2

in)

后相應(yīng)的同余式也有解，同樣可以導(dǎo)出證明。例．證明對于任意給定的正整數(shù)n，有連續(xù)個正整數(shù)，其中每一個都不是冪數(shù)。分析：我們來證明，存在連n個正整數(shù)，其中每一個數(shù)都至有一個素因子，在這個數(shù)的標準分解中僅出現(xiàn)一次，從而這個數(shù)不是冪數(shù)。證明：取

n

個互不相同的素數(shù)

,,12

n

，考慮同余組

xp),i,n因為

,,p12n

顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。對于

1為i

2i

)故p

2i

|()

但①式可知

p2i

()即p在i()

的標準分解中恰好出現(xiàn)一次，故

xxx

都不是冪數(shù)。

aa例．設(shè)

是給定的偶數(shù)，

n

且

k(n

是偶數(shù)。證明：存在整數(shù)x,y

使得

(,)y,)

，且

xykn)

。證明：我們先證明，當

n

為素數(shù)冪

時結(jié)論成立。實際上，能夠證明，存在x

使

且

xy

：若

，則條件表明

為偶數(shù)，此時可取

x

；若p，則y與x2,y

中有一對滿足要求。一般情形下，設(shè)n12r

r

,i1,2,,r

是

n

的一個標準分解，上面已經(jīng)證明，對每個

i

存在整數(shù)

xyi

i

使得

xii

i

且

x(ir)ii

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

iii

,r)

①有解

，同余式i

ii

ir)

②有解y。現(xiàn)不難驗證解x,y

符合問題中的要求：因

ii

i

，故

i

(i1,2,r)

，于是

(,n)

，又由①②知

i

(mod)(iii

1,2,,r

，故

xykn)

。注此的論證表現(xiàn)了中國剩余定理