萬(wàn)文婷

(荊楚理工學(xué)院數(shù)理學(xué)院，湖北 荊門(mén) 448000)

Euler函數(shù)計(jì)算公式的證明研究

萬(wàn)文婷

(荊楚理工學(xué)院數(shù)理學(xué)院，湖北 荊門(mén) 448000)

利用孫子定理及排列組合中乘法原理的相關(guān)結(jié)論，討論了特殊區(qū)間上與已知的n個(gè)素?cái)?shù)p1,p2,…,pn互素的整數(shù)個(gè)數(shù)，并證明了Euler函數(shù)的計(jì)算公式。同時(shí)給出了對(duì)任意的正整數(shù)k和m，區(qū)間(m,m+kp1p2…pn]上與p1,p2,…,pn互素的整數(shù)個(gè)數(shù)等于k(p1-1)(p2-1)…(pn-1)的結(jié)論。

Euler函數(shù)；孫子定理；素?cái)?shù)

Euler函數(shù)是數(shù)論中的一個(gè)重要函數(shù)。 設(shè)n為自然數(shù)，φ(n)表示不大于n且與n互素的自然數(shù)個(gè)數(shù)，φ(n)就稱(chēng)為Euler函數(shù)。Euler函數(shù)在數(shù)論中十分重要且有著廣泛的應(yīng)用，如在離散數(shù)學(xué)中求循環(huán)群的生成元、在計(jì)算機(jī)網(wǎng)絡(luò)中的RSA公鑰密碼體制等。文獻(xiàn)[1,2]中利用互素剩余系與簡(jiǎn)化剩余系的性質(zhì)推得計(jì)算φ(n)的公式，文獻(xiàn)[3,4]中又利用組合數(shù)學(xué)中的容斥原理證明了φ(n)的計(jì)算公式。筆者通過(guò)對(duì)特殊區(qū)間上與已知的n個(gè)素?cái)?shù)p1,p2,…,pn互素的整數(shù)個(gè)數(shù)的討論，也推得了φ(n)的計(jì)算公式，并得到了區(qū)間長(zhǎng)度為kp1p2…pn(k∈Z+)的區(qū)間(m,m+kp1p2…pn](m∈Z+)上與p1,p2,…,pn互素的整數(shù)個(gè)數(shù)?。

1 基本概念

用N(p1,p2,…,pn;A)表示集合A中與p1,p2,…,pn互素的整數(shù)個(gè)數(shù)。

引理1已知素?cái)?shù)p1,p2,…,pn及常數(shù)c1,c2,…,cn，其中0≤cilt;pi,1≤i≤n，且ci∈N，則同余式組：

a≡c1(modp1)a≡c2(modp2) …a≡cn(modpn)

的最小正整數(shù)解a0存在，且a0∈(0,p1p2…pn]。

由孫子定理[1]，即得引理1。若設(shè)常數(shù)d1,d2,…,dn，其中0≤dilt;pi,1≤i≤n，且di∈N,同余式組：

b≡d1(modp1)b≡d2(modp2) …b≡dn(modpn)

的最小正整數(shù)解為b0，易推得a0≠b0的充要條件是至少有一個(gè)ci≠di，1≤i≤n。

引理2已知素?cái)?shù)p1,p2,…,pn及任意常數(shù)c1,c2,…，cn，其中0≤cilt;pi,1≤i≤n且ci∈N，區(qū)間(0,p1p2…pn]上的任一整數(shù)必與一個(gè)同余式組：

a≡c1(modp1)a≡c2(modp2) …a≡cn(modpn)

的最小正整數(shù)解相等。

證明由于0≤cilt;pi,1≤i≤n，因此一組常數(shù)c1,c2,…,cn的不同取法共有p1p2…pn種，與其對(duì)應(yīng)的共有p1p2…pn個(gè)不同的同余式組。再結(jié)合引理1知，這些不同的同余式組的最小正整數(shù)解都互不相同，且都屬于區(qū)間(0,p1p2…pn]。而區(qū)間(0,p1p2…pn]上共有p1p2…pn個(gè)不同的正整數(shù)。所以，引理2成立。

2 主要結(jié)果

定理1區(qū)間(0,p1p2…pn]上與p1,p2,…,pn互素的整數(shù)個(gè)數(shù)為:

N(p1,p2,…,pn;(0,p1p2…pn])=(p1-1)(p2-1)…(pn-1)

證明由引理2知，區(qū)間(0,p1p2…pn]上的任一與p1,p2,…,pn互素的整數(shù)b必與某一個(gè)同余式組：

a≡c1(modp1)a≡c2(modp2) …a≡cn(modpn)

的最小正整數(shù)解相等，其中，0≤cilt;pi(1≤i≤n)，且ci∈N。再由b與p1,p2,…,pn互素，上面的ci≠0,1≤i≤n，這樣的常數(shù)c1,c2,…,cn的不同取法共有(p1-1)(p2-1)…(pn-1)。

所以，區(qū)間(0,p1p2…pn]上與p1,p2,…,pn互素的整數(shù)個(gè)數(shù)為(p1-1)(p2-1)…(pn-1)。

引理3區(qū)間(0,m]與(kp1p2…pn,m+kp1p2…pn]上與p1,p2,…,pn互素的整數(shù)個(gè)數(shù)相等，即：

N(p1,p2,…,pn;(0,m])=N(p1,p2,…,pn;(kp1p2…pn,m+kp1p2…pn])k,m∈N

證明令b=a+kp1p2…pn，a是區(qū)間(0,m]上與p1,p2,…,pn互素的整數(shù)的充要條件就是b是區(qū)間(kp1p2…pn,m+kp1p2…pn]上與p1,p2,…,pn互素的整數(shù)。所以，區(qū)間(0,m]與(kp1p2…pn,m+kp1p2…pn]上與p1,p2,…,pn互素的整數(shù)個(gè)數(shù)相同。

定理2區(qū)間(0,kp1p2…pn]上與p1,p2,…,pn互素的整數(shù)個(gè)數(shù)為：

N(p1,p2,…,pn;(0,kp1p2…pn])=k(p1-1)(p2-1)…(pn-1)k∈N

證明由引理3知：

N(p1,p2,…,pn；(0,p1p2…pn])=N(p1,p2,…,pn;(tp1p2…pn,(t+1)p1p2…pn])t∈N

所以：

N(p1,p2,…,pn;(0,kp1p2…pn])

再由定理2，可得如下結(jié)論：

定理3區(qū)間長(zhǎng)度為kp1p2…pn的任意區(qū)間(m,m+kp1p2…pn]上與p1,p2,…,pn互素的整數(shù)個(gè)數(shù)為：

N(p1,p2,…,pn;(m,m+kp1p2…pn])=k(p1-1)(p2-1)…(pn-1)k,m∈N

證明(1)當(dāng)m≤kp1p2…pn時(shí):

N(p1,p2,…,pn;(m,m+kp1p2…pn])

=N(p1,p2,…,pn;(m,kp1p2…pn])+N(p1,p2,…,pn;(kp1p2…pn,m+kp1p2…pn])

=N(p1,p2,…,pn;(m,kp1p2…pn])+N(p1,p2,…,pn;(0,m])

=N(p1,p2,…,pn;(0,kp1p2…pn])=k(p1-1)(p2-1)…(pn-1)

(2)當(dāng)mgt;kp1p2…pn時(shí):

N(p1,p2,…,pn;(m,m+kp1p2…pn])

=N(p1,p2,…,pn;(kp1p2…pn,m+kp1p2…pn])-N(p1,p2,…,pn;(kp1p2…pn,m])

=N(p1,p2,…,pn;(0,m])-N(p1,p2,…,pn;(kp1p2…pn,m])

=N(p1,p2,…,pn;(0,kp1p2…pn])=k(p1-1)(p2-1)…(pn-1)

[1]潘承洞,潘承彪.初等數(shù)論[M].北京:北京大學(xué)出版社,1992.

[2]閔嗣鶴,嚴(yán)士健.初等數(shù)論[M].北京:高等教育出版社,1982.

[3]王迪吉,方劍英.組合數(shù)學(xué)在數(shù)論中的應(yīng)用實(shí)例[J].新疆師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2002,12(4):6～9.

[4]陳碧琴.容斥原理在數(shù)論中的應(yīng)用實(shí)例[J].綿陽(yáng)師范學(xué)院學(xué)報(bào),2004,4(2):25～28.

[編輯] 洪云飛

2009-07-29

萬(wàn)文婷(1982-)，女， 2003年大學(xué)畢業(yè)，碩士，講師，現(xiàn)主要從事代數(shù)與數(shù)論方面的教學(xué)與研究工作。

?荊楚理工學(xué)院科研項(xiàng)目(ZR200708)。

O156.1

[MR(2000)主題分類(lèi)號(hào)]11A41

A

1673-1409(2009)04-N010-02