兩類廣義歐拉函數(shù)的遞歸公式

廖群英

（四川師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，四川成都610066）

1 前言和主要結(jié)果

早在18 世紀(jì)，歐拉首次定義了正整數(shù)n 的歐拉函數(shù)φ（n）為不超過n且與n互質(zhì)的正整數(shù)的個數(shù)［1］.歐拉函數(shù)作為最重要的數(shù)論函數(shù)之一，有著廣泛的應(yīng)用［1-4］.在 2002 和 2007 年，文獻(xiàn)［5 -6］把歐拉函數(shù)的定義推廣至廣義歐拉函數(shù).

定義 1.1［5-6］給定正整數(shù)n和e，n關(guān)于e的廣義歐拉函數(shù)定義為

即 φe（n）等于不超過且與n 互質(zhì)的正整數(shù)的個數(shù)，這里［x］表示不超過x的最大整數(shù).

由此定義易證

其中 μ（n）為 M?bius函數(shù)，即當(dāng)pi（i ＝1，…，k）為不同的素數(shù)時，

易知，對任意正整數(shù)n≥2，有

于是，由定義易知 φ（n）＝φ1（n）且n≥2.

問題給定正整數(shù) e，確定廣義歐拉函數(shù)φe（n）的準(zhǔn)確計算公式.

近年來，文獻(xiàn)［7 -8］利用Legendre和Jacobi符號的性質(zhì)，給出了 φe（n）（e ＝3，4，6）的準(zhǔn)確計算公式，并由此得到 φe（n）和 φe（n+1），e ＝2，3，4，6，同時為奇數(shù)或同時為偶數(shù)的幾個充分必要條件.

命題 1.1［7-8］設(shè) p1，p2，…，pk為不同的素數(shù)，α1，α2，…，αk為正整數(shù)12k

1）若 gcd（pi，3）＝ 1（i ＝ 1，2，…，k）且 n ＝3αn1＞ 3，則

2）若 gcd（pi，2）＝ 1（i ＝ 1，2，…，k）且 n ＝2αn1＞ 4，則

3）若 gcd（pi，6）＝ 1（i ＝ 1，2，…，k），且 n ＝2α3βn1＞ 6，則

我們給出 φ5（n）的計算公式，并由此得到φ5（n）為偶數(shù)的幾個充分條件［9］.利用初等的方法和技巧，本文推廣了文獻(xiàn)［7 -9］的主要結(jié)果，給出了 φe（n）（e ＝ pt或e ＝prqt）的一個遞歸計算公式，并由此得到一些特殊情形下的準(zhǔn)確計算公式，這里p、q為不同的素數(shù)，t 和 r 為正整數(shù).從而部分解決了上述提出的問題.事實上，設(shè) p、q、p1、p2、…、pk為不同的素數(shù)，r、t、α1、α2、…、αk為正整數(shù)，α 和 β 為非負(fù)整數(shù)證明了如下幾個主要結(jié)果.

定理 1. 1若 n ＝ n1，e 為正整數(shù)，e ＜ n 且gcd（e，n）＝1，則

定理 1.2若α為正整數(shù)，e ＝pt且n ＝pαn1＞e，則

定理 1.3若 e ＝ prqt且 n ＝ pαqβn1＞ e，則

定理1.4給定e ＝prqt以及 n ＝ pαqβn1＞ e.

1）若 α ≥ r + 1 且 β ≥ t + 1，或 者 pi≡1（mod e），i ＝1，2，…，k，則

2）若 α≥r +1 和 β≥t +1 不能同時成立，且pi≡ -1（mod e），i ＝1，2，…，k，則

注記11）對定理 1. 3 和 1. 4 中的 pi≡-1（mod e）（i ＝1，2，…，k）的情形，由 p 和 q 的對稱性知α和β互換后的對偶結(jié)論也成立.詳情留給有興趣的讀者.

2）在定理 1.1 中取 e ＝3，以及定理 1.2 中取p ＝3，t ＝1，則可得到命題1.1 的1）；在定理1.1 中取 e ＝4，以及在定理 1.2 中 p ＝ t ＝2，則可得到命題1.1 的 2）；在定理 1.1 中取 e ＝6，以及定理 1.4 中取 p ＝2，q ＝3，r ＝ t ＝1，即得命題 1.1 的 3）.詳情留給有興趣的讀者.

2 主要結(jié)果的證明

定理 1.1 的證明1）若 pi≡1（mod e），i ＝1，2，…，k，即對任意 d ｜n，均有 d≡1（mod e），則由（1）～（3）式可知

2）若 pi≡ -1（mod e）（i ＝1，2，…，k），則對任意 d ｜n，均有 d≡ ± 1（mod e）.故由（2）～ （4）式可得

綜上，由（4）式以及（7）～（9）式立得

且與n互質(zhì)的正整數(shù)的個數(shù).因為 βi≤αi-1，i ＝1，2，…，k，故對任意有

于是，由廣義歐拉函數(shù)的定義可得

這就完成了定理1.1 的證明.

定理 1. 2 的證明由 e ＝ pt，n ＝ pαn1以及gcd（p，n1）＝1，可得

1）若1≤α≤t，則由 gcd（p，n1）＝1 以及（1）～（3）式可知

由1≤α≤t以及定理1.1，有如下2 種情形.

情形 1 若t-α≥1，故 t≥2，則由1≤α≤t -1，gcd（p，n1）＝1，（8）～ （9）式及定理1.1 可得

情形 2 否則，即 α ＝ t，則由 gcd（p，n1）＝1，（9）式以及定理 1.1 有

2）若 α≥t+1，即 e ＝ pt｜pα-ten1，則由定理 1.1可得

綜上，由（9）～ （12）式可知定理1.2 得證.

定理 1.3 的證明1）若 α ＝ β ＝0，結(jié)論顯然.

2）若 α ＝0 且1≤β≤t，即 n ＝ qβn1.則由（1）～（3）式可得

3）若 α ＝0 且 β≥t+1，即 n ＝ qβn1.則由（1）～（3）式可得

故由（14）和（15）式可得

4）若1≤α≤r，且1≤β≤t，即 n ＝ pαqβn1.則由gcd（p，q）＝gcd（pq，n1）＝1 以及（1）～（3）式有

5）若1≤α≤r，且 β≥t+1，即 n ＝ pαqβn1.則由gcd（p，q）＝gcd（pq，n1）＝1 以及（1）～（3）式可得

故由（18）～（20）式可得

6）若 α≥r+1，且 β≥t+1，即 e ｜pqen1，此時由定理1.1 立得結(jié)論.

綜上可知，定理1.3 得證.

定理1.4 的證明

情形 1 若 pi≡1（mod e），i ＝1，2，…，k，則由 gcd（p，q）＝gcd（pq，n1）＝1，定理 1.1 以及定理1.3，可知有如下7 種情形.

1）若 α ＝ β ＝0，即 gcd（e，n）＝1，則由定理1.1可得

2）若 α ＝0，且 1≤β≤t，即 n ＝ qβn1，則 φ（n）＝qβ-1（q-1）φ（n1），且由（13）式可得

3）若 α ＝0，且 β≥t +1，即 n ＝ qβn1，則 φ（n）＝qβ-1（q-1）φ（n1），且由 （16）式可得

4）若 1≤α≤r，且 β ＝0，即 n ＝ pαn1，類似于情形（2）可得

5）若 1≤α≤r，且 1≤β≤t，即 n ＝ pαqβn1，則

φ（n）＝ qβ-1pα-1（p -1）（q -1）φ（n1），從而由（17）式可得

6）若1≤α≤r，且 β≥t+1，即 n ＝ pαqβn1，則由（21）式可得

綜上可知，對于 pi≡1（mod e），i ＝1，2，…，k，總有成立.

情形 2 若 pi≡ -1（mod e），i ＝1，2，…，k，則由 gcd（p，q）＝ gcd（pq，n1）＝1 以及定理 1.1 ～1.3，可知有如下7 種情形.

1）若 α ＝ β ＝0，即 n ＝ n1，則由定理 1.1 可知結(jié)論成立.

2）若 α ＝0，且 1≤β≤t，即 n ＝ qβn1，則由（13）式可得

3）若 α ＝0，且 β≥t+1，即 n ＝ qβn1，則由（16）式可得

4）若 α ＝ r，且 β ＝ t，即 n ＝ pαqβn1＝ en1，則由（17）式可得

5）若 r≥2，1≤α≤r -1，且 1≤β≤t，即 n ＝pαqβn1，則由（17）式可得

6）若 r≥2，1≤α≤r -1，且 β≥t +1，即 n ＝pαqβn1，則由（21）式可得

7）若 α ＝ r，且 β≥t +1，即 n ＝ prqβn1，則由（21）式可得

綜上，由情形1 以及（22）～（27）式可知定理1.4 得證.

3 結(jié)束語

設(shè)n和 e為正整數(shù).近年來，Cai［5］定義了廣義歐拉函數(shù) φe（n），并完全確定了 φe（n）（e ＝3，4，6）的準(zhǔn)確計算公式.利用初等的方法和技巧，本文推廣了文獻(xiàn)［7 -9］中的主要結(jié)果，給出了φe（n）（e ＝pt或者 e ＝ prqt）的一個遞歸計算公式，這里 p、q 為不同的素數(shù)，t和r為正整數(shù).由此部分解決了廣義歐拉函數(shù)計算公式這一公開問題.