關于廣義歐拉函數φ5(n)

王 容, 廖群英

(四川師范大學 數學與軟件科學學院, 四川 成都 610066)

歐拉函數是數論中一個非常重要的函數,它是18世紀數學界最杰出的人物之一——歐拉提出來的:正整數n的歐拉函數φ(n)的值等于序列0,1,2,…,n-1中與n互素的整數個數[1].歐拉函數有著很廣泛的應用,尤其是自20世紀70年代以來,歐拉函數成為RSA公鑰密碼體制得以建立的重要數學工具之一.迄今為止,有很多關于歐拉函數的問題尚未解決[2],比如Carmichael猜想,即對于任何正整數n,總存在一個正整數m≠n,使得φ(m)=φ(n);還有Schinzel猜想,即對于任何正整數k,方程φ(n+k)=φ(n)有無限個解,等等.

另一方面,早在1938年,Lehmer[3]就建立了如下的重要同余式

(1)

其中qr(n)是歐拉商數,即

自然數n,r≥2且gcd(n,r)=1.

用(1)式和一些類似的同余式,Lehmer找到很多方法來證明費馬大定理的第一種情況[4].從2002年到2007年,文獻[5-6]將Lehmer的其它同余式從模素數的平方推廣到模任意整數的平方,并定義正整數n的廣義歐拉函數為

(2)

其中μ(n)是麥比烏斯函數,即

由歐拉函數的定義可得φ1(n)=φ(n).因此一個自然的問題是:對任意固定的e,能否得到φe(n)的準確計算公式?

近年來,文獻[7-9]利用勒讓德符號和雅可比符號等性質給出了φe(n)(e=2,3,4,6)的準確計算公式,以及給出φe(n)和φe(n+1)(e=2,3,4)同為奇數的充要條件.

本文進一步研究該問題,給出一些特殊正整數n的廣義歐拉函數φ5(n)的準確計算公式,并討論其奇偶性,即證明了如下主要結果:

1)n=5α,其中α≥2為正整數;

定理21) 若素數p=5k+m,其中k≥0為整數且0≤m≤4,則

2) 若n=pα,其中α≥2為整數且p為不等于5的素數,則

其中,m2≡pα-1(mod 5),m1≡pm2(mod 5),1≤mi≤4(i=1,2).

其中,αi≥1,gcd(pi,5)=1且1≤mi,ni≤4(i=1,2),則

定理31) 設p為素數,則φ5(p)為偶數當且僅當p=2或者p≡1,3(mod 10).

2) 設n=pα,其中α≥2為整數且p為素數,則φ5(n)為偶數當且僅當p=5,或者下列條件之一成立:

(i)p≡1(mod 5)且m1=m2;

(ii)p≡3(mod 5)且(m1,m2)=(3,1)或者(2,4);

(iii)p≡2(mod 5)且(m1,m2)=(1,3)或者(4,2),

其中1≤mi≤4(i=1,2),且

1 主要結果的證明

定理1的證明1) 若n=5α,其中α≥2為正整數,故由(2)和(3)式可知

這就證明了定理1的情況1).

這就證明了定理1的情況2).

(4)

其中,1≤mi,ni≤4(i=1,2)且

(5)

即m2=n1且m1=n2.因此,由(4)式可得

其中,1≤mi,ni≤4(i=1,2)且

這就證明了定理1的情況3).

定理2的證明1) 若素數p=5k+m,其中k≥0為整數且0≤m≤4,則由(2)和(3)式可知

這就證明了定理2的情況1).

2) 若n=pα,其中p≠5為素數,α≥2為正整數,則由(2)和(3)式可得

其中,1≤mi≤4(i=1,2)且

(7)

即

(8)

這就證明了定理2的情況2).

其中,1≤mi,ni≤4(i=1,2)且

(9)

即

(10)

這就證明了定理2的情況3).

情形 1:若m1=m2,則由(p,5)=1以及(8)式可得pα-1×(p-1)≡0(mod 5),即p≡1(mod 5).

情形 2:若m1=3,m2=1,則由(p,5)=1以及(8)式可知m1≡pm2(mod 5),即p≡3(mod 5).

情形 3:若m1=1,m2=3,則由(p,5)=1以及(8)式可知m1≡pm2(mod 5),故1≡3p(mod 5),即p≡2(mod 5).

情形 4:若m1=2,m2=4,則由(p,5)=1以及(8)式可知m1≡pm2(mod 5),故2≡4p(mod 5),即p≡3(mod 5).

情形 5:若m1=4,m2=2,則由(p,5)=1以及(8)可知m1≡pm2(mod 5),即4≡2p(mod 5),即p≡2(mod 5).

這就證明了定理3的情況2).

2 應用舉例

下面通過定義和應用定理1的2種計算方法來計算φ5(n),其中用定義直接計算顯得比較繁瑣,當n很大時,計算量就越大.而應用定理可以很便捷地計算出φ5(n),以下通過幾個實例進行說明.

另一方面,由于素數11=5×2+1,即m=1.故由φ(11)=10以及定理2的情況1)可知

另一方面,由n=33=27,即p=3,α=3,可得

m2≡32≡4(mod 5),m1≡3m2≡2(mod 5),

即m1=2,m2=4.故由φ(27)=18以及由定理2的情況2)可得

另一方面,由n=53=125,即p=5.故由φ(125)=100以及由定理1的情況1)可得

另一方面,由n=341,即

p1=11≡1(mod 5),p2=31≡1(mod 5),

故由φ(341)=300以及由定理1的情況2)可得

另一方面,由n=11×23=88,即p1=11,p2=2,α1=1,α2=3,因為p1=11≡1(mod 5),故由φ(88)=40以及由定理1的情況3)可得

另一方面,由n=23×32=72,即p1=2,p2=3,α1=3,α2=2,可得

即n1=2,n2=2,m1=1,m2=4.故由φ(72)=24以及由定理2的情況3)可得

[1] IRELAND K, ROSEN M. A Classical Introduction to Modern Number Theory[M]. New York:Springer-Verlag,1990.

[2] GUY R. Unsolved Problems in Number Theory[M]. New York:Springer-Verlag,2004.

[3] LEHMER E. On congruences involving Bernoulli numbers and the quotients of Fermat and Wilson[J]. Ann Math,1938,39(2):350-359.

[4] RIBENBOIM P. 13 Lectures on Fermat’s Last Theorem[M]. New York:Springer-Verlag,1979.

[5] CAI T X. A congruence involving the quotients of Euler and its applications(I)[J]. Acta Aritmetica,2002,103(4):313-320.

[6] CAI T X, FU X D, ZHOU X. A congruence involving the quotients of Euler and its applications (II)[J]. Acta Aritmetica,2007,130(3):203-214.

[7] 蔡天新,沈忠燕,胡孟君. 廣義歐拉函數的奇偶性(英)[J]. 數學進展,2013,42(4):505-510.

[8] 丁煜. 廣義歐拉函數及其性質[D]. 杭州:浙江大學,2008.

[9] 沈忠燕,蔡天新,胡孟君. 廣義歐拉函數的奇偶性(II)(英)[J]. 數學進展,2016,45(4):509-519.