欧拉函数





Disambig gray.svg  本文介紹的是小於或等於n的正整數中與n互質的數的數目。關於形式為ϕ(q)=∏k=1∞(1−qk){displaystyle phi (q)=prod _{k=1}^{infty }(1-q^{k})}phi (q)=prod _{{k=1}}^{infty }(1-q^{k})的函數，請見「歐拉函數 (複變函數)」。



当n为1至1000的整数时φ(n){displaystyle varphi (n)}varphi (n)的值


在數論中，對正整數n，歐拉函數φ(n){displaystyle varphi (n)}varphi (n)是小於或等於n的正整數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為φ函數（由高斯所命名）或是歐拉總計函數[1]（totient function，由西爾維斯特所命名）。


例如φ(8)=4{displaystyle varphi (8)=4}varphi (8)=4，因為1,3,5,7均和8互質。


欧拉函数实际上是模n的同余类所构成的乘法群（即环Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} }{mathbb {Z}}/n{mathbb {Z}}的所有单位元组成的乘法群）的阶。这个性质与拉格朗日定理一起構成了欧拉定理的證明。




目录






  • 1 歷史：欧拉函數與費馬小定理


  • 2 欧拉函數的值


  • 3 性质


  • 4 生成函数


  • 5 欧拉函数的走势


  • 6 其他与欧拉函数有关的等式


  • 7 与欧拉函数有关的不等式


  • 8 参考来源


  • 9 文獻来源





歷史：欧拉函數與費馬小定理


1736年，欧拉證明了费马小定理[2]：


假若 p{displaystyle p}p 為質數，a{displaystyle a}a 為任意正整數，那麼 ap−a{displaystyle a^{p}-a}a^{p}-a 可被 p{displaystyle p}p 整除。

然後欧拉予以一般化：


假若 a{displaystyle a}a 與 n{displaystyle n}n 互質，那麼 aφ(n)−1{displaystyle a^{varphi (n)}-1}{displaystyle a^{varphi (n)}-1} 可被 n{displaystyle n}n 整除。亦即，aφ(n)≡1(modn){displaystyle a^{varphi (n)}equiv 1{pmod {n}}}a^{{varphi (n)}}equiv 1{pmod n}。

其中 φ(n){displaystyle varphi (n)}varphi (n) 即為歐拉總計函數。如果 n{displaystyle n}n 為質數，那麼 φ(n)=n−1{displaystyle varphi (n)=n-1}{displaystyle varphi (n)=n-1}，因此，有高斯的版本[3]：


假若 p{displaystyle p}p 為質數，a{displaystyle a}a 與 p{displaystyle p}p 互質（a{displaystyle a}a 不是 p{displaystyle p}p 的倍數），那麼 ap−1≡1(modp){displaystyle a^{p-1}equiv 1{pmod {p}}}a^{{p-1}}equiv 1{pmod p}。


欧拉函數的值


φ(1)=1{displaystyle varphi (1)=1}varphi (1)=1（小于等于1的正整数中唯一和1互質的數就是1本身）。


若n是質數p的k次冪，φ(n)=φ(pk)=pk−pk−1=(p−1)pk−1{displaystyle varphi (n)=varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}}varphi (n)=varphi (p^{k})=p^{k}-p^{{k-1}}=(p-1)p^{{k-1}}，因為除了p的倍數外，其他數都跟n互質。


歐拉函數是積性函數，即是说若m,n互質，φ(mn)=φ(m)φ(n){displaystyle varphi (mn)=varphi (m)varphi (n)}varphi (mn)=varphi (m)varphi (n)。證明：設A, B, C是跟m, n, mn互質的數的集，據中國剩餘定理，A×B{displaystyle Atimes B}Atimes B和C{displaystyle C}C可建立雙射(一一對應)的關係。（或者也可以从初等代数角度给出欧拉函数积性的简单证明） 因此φ(n){displaystyle varphi (n)}varphi (n)的值使用算術基本定理便知，


若n=p1k1p2k2⋯prkr{displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}cdots p_{r}^{k_{r}}}n=p_{1}^{{k_{1}}}p_{2}^{{k_{2}}}cdots p_{r}^{{k_{r}}}

則φ(n)=∏i=1rpiki−1(pi−1)=∏p∣npαp−1(p−1)=n∏p|n(1−1p){displaystyle varphi (n)=prod _{i=1}^{r}p_{i}^{k_{i}-1}(p_{i}-1)=prod _{pmid n}p^{alpha _{p}-1}(p-1)=nprod _{p|n}left(1-{frac {1}{p}}right)}varphi (n)=prod _{{i=1}}^{r}p_{i}^{{k_{i}-1}}(p_{i}-1)=prod _{{pmid n}}p^{{alpha _{p}-1}}(p-1)=nprod _{{p|n}}left(1-{frac {1}{p}}right)。

其中αp{displaystyle alpha _{p}}alpha _{p}是使得pα{displaystyle p^{alpha }}p^{{alpha }}整除n{displaystyle n}n的最大整数α{displaystyle alpha }alpha （这里αpi=ki{displaystyle alpha _{p_{i}}=k_{i}}alpha _{{p_{i}}}=k_{i}）。


例如φ(72)=φ(23×32)=23−1(2−1)×32−1(3−1)=22×1×3×2=24{displaystyle varphi (72)=varphi (2^{3}times 3^{2})=2^{3-1}(2-1)times 3^{2-1}(3-1)=2^{2}times 1times 3times 2=24}varphi (72)=varphi (2^{3}times 3^{2})=2^{{3-1}}(2-1)times 3^{{2-1}}(3-1)=2^{2}times 1times 3times 2=24



性质


n的欧拉函数φ(n){displaystyle varphi (n)}varphi (n) 也是循环群 Cn 的生成元的个数（也是n阶分圆多项式的次数）。Cn 中每个元素都能生成 Cn 的一个子群，即必然是某个子群的生成元。而且按照定义，不同的子群不可能有相同的生成元。此外， Cn 的所有子群都具有 Cd 的形式，其中d整除n（记作d | n）。因此只要考察n的所有因数d，将 Cd 的生成元个数相加，就将得到 Cn 的元素总个数：n。也就是说：


∑d∣nφ(d)=n{displaystyle sum _{dmid n}varphi (d)=n}sum _{{dmid n}}varphi (d)=n

其中的d为n的正约数。


运用默比乌斯反转公式来“翻转”这个和，就可以得到另一个关于φ(n){displaystyle varphi (n)}varphi (n)的公式：


φ(n)=∑d∣nd⋅μ(n/d){displaystyle varphi (n)=sum _{dmid n}dcdot mu (n/d)}varphi (n)=sum _{{dmid n}}dcdot mu (n/d)

其中 μ 是所谓的默比乌斯函数，定义在正整数上。


對任何兩個互質的正整數a, m（即 gcd(a,m) = 1），m≥2{displaystyle mgeq 2}mgeq 2，有


aφ(m)≡1(modm){displaystyle a^{varphi (m)}equiv 1{pmod {m}}}a^{{varphi (m)}}equiv 1{pmod m}

即欧拉定理。


这个定理可以由群论中的拉格朗日定理得出，因为任意与m互质的a都属于环 Z/nZ{displaystyle mathbb {Z} /nmathbb {Z} }{mathbb {Z}}/n{mathbb {Z}} 的单位元组成的乘法群Z/nZ×{displaystyle mathbb {Z} /nmathbb {Z} ^{times }}{mathbb {Z}}/n{mathbb {Z}}^{{times }}


當m是質數p時，此式則為：


ap−1≡1(modp){displaystyle a^{p-1}equiv 1{pmod {p}}}a^{{p-1}}equiv 1{pmod p}

即費馬小定理。



生成函数


以下两个由欧拉函数生成的级数都是来自于上节所给出的性质：∑d|nφ(d)=n{displaystyle sum _{d|n}varphi (d)=n}sum _{{d|n}}varphi (d)=n。


由φ{displaystyle varphi }varphi (n)生成的狄利克雷级数是：


∑n=1∞φ(n)ns=ζ(s−1)ζ(s).{displaystyle sum _{n=1}^{infty }{frac {varphi (n)}{n^{s}}}={frac {zeta (s-1)}{zeta (s)}}.}sum _{{n=1}}^{infty }{frac {varphi (n)}{n^{s}}}={frac {zeta (s-1)}{zeta (s)}}.

其中ζ(s)是黎曼ζ函数。推导过程如下：



ζ(s)∑f=1∞φ(f)fs=(∑g=1∞1gs)(∑f=1∞φ(f)fs){displaystyle zeta (s)sum _{f=1}^{infty }{frac {varphi (f)}{f^{s}}}=left(sum _{g=1}^{infty }{frac {1}{g^{s}}}right)left(sum _{f=1}^{infty }{frac {varphi (f)}{f^{s}}}right)}zeta (s)sum _{{f=1}}^{infty }{frac {varphi (f)}{f^{s}}}=left(sum _{{g=1}}^{infty }{frac {1}{g^{s}}}right)left(sum _{{f=1}}^{infty }{frac {varphi (f)}{f^{s}}}right)

.               =∑h=1∞(∑fg=h1⋅φ(g))1hs{displaystyle . =sum _{h=1}^{infty }left(sum _{fg=h}1cdot varphi (g)right){frac {1}{h^{s}}}}. =sum _{{h=1}}^{infty }left(sum _{{fg=h}}1cdot varphi (g)right){frac {1}{h^{s}}}

.               =∑h=1∞(∑fg=hφ(g))1hs=∑h=1∞(∑d|hφ(d))1hs{displaystyle . =sum _{h=1}^{infty }left(sum _{fg=h}varphi (g)right){frac {1}{h^{s}}}=sum _{h=1}^{infty }left(sum _{d|h}varphi (d)right){frac {1}{h^{s}}}}. =sum _{{h=1}}^{infty }left(sum _{{fg=h}}varphi (g)right){frac {1}{h^{s}}}=sum _{{h=1}}^{infty }left(sum _{{d|h}}varphi (d)right){frac {1}{h^{s}}}

使用开始时的等式，就得到：∑h=1∞(∑d|hφ(d))1hs=∑h=1∞hhs{displaystyle sum _{h=1}^{infty }left(sum _{d|h}varphi (d)right){frac {1}{h^{s}}}=sum _{h=1}^{infty }{frac {h}{h^{s}}}}sum _{{h=1}}^{infty }left(sum _{{d|h}}varphi (d)right){frac {1}{h^{s}}}=sum _{{h=1}}^{infty }{frac {h}{h^{s}}}

于是∑h=1∞hhs=ζ(s−1){displaystyle sum _{h=1}^{infty }{frac {h}{h^{s}}}=zeta (s-1)}sum _{{h=1}}^{infty }{frac {h}{h^{s}}}=zeta (s-1)


欧拉函数生成的朗贝级数如下：


∑n=1∞φ(n)qn1−qn=q(1−q)2{displaystyle sum _{n=1}^{infty }{frac {varphi (n)q^{n}}{1-q^{n}}}={frac {q}{(1-q)^{2}}}}sum _{{n=1}}^{{infty }}{frac {varphi (n)q^{n}}{1-q^{n}}}={frac {q}{(1-q)^{2}}}

其对于满足 |q|<1 的q收敛。


推导如下：


∑n=1∞φ(n)qn1−qn=∑n=1∞φ(n)∑r≥1qrn{displaystyle sum _{n=1}^{infty }{frac {varphi (n)q^{n}}{1-q^{n}}}=sum _{n=1}^{infty }varphi (n)sum _{rgeq 1}q^{rn}}sum _{{n=1}}^{{infty }}{frac {varphi (n)q^{n}}{1-q^{n}}}=sum _{{n=1}}^{{infty }}varphi (n)sum _{{rgeq 1}}q^{{rn}}

后者等价于：


∑k≥1qk∑n|kφ(n)=∑k≥1kqk=q(1−q)2.{displaystyle sum _{kgeq 1}q^{k}sum _{n|k}varphi (n)=sum _{kgeq 1}kq^{k}={frac {q}{(1-q)^{2}}}.}sum _{{kgeq 1}}q^{k}sum _{{n|k}}varphi (n)=sum _{{kgeq 1}}kq^{k}={frac {q}{(1-q)^{2}}}.


欧拉函数的走势


随着n变大，估计φ(n){displaystyle varphi (n)}varphi (n) 的值是一件很难的事。当n为质数时，φ(n)=n−1{displaystyle varphi (n)=n-1}varphi (n)=n-1，但有时φ(n){displaystyle varphi (n)}varphi (n)又与n差得很远。


在n足够大时，有估计：


对每个 ε > 0，都有n > N(ε)使得 n1−ε<φ(n)<n{displaystyle ,n^{1-varepsilon }<varphi (n)<n},n^{{1-varepsilon }}<varphi (n)<n

如果考虑比值：


φ(n)/n,{displaystyle ,varphi (n)/n,},varphi (n)/n,

由以上已经提到的公式，可以得到其值等于类似1−p−1{displaystyle 1-p^{-1}}1-p^{{-1}}的项的乘积。因此，使比值小的n将是两两不同的质数的乘积。由素数定理可以知道，常数 ε 可以被替换为：


Clog⁡log⁡n/log⁡n.{displaystyle C,log log n/log n.}C,log log n/log n.

φ{displaystyle varphi }varphi 就平均值的意义上来说是与n很相近的，因为：


1n2∑k=1nφ(k)=3π2+O(log⁡nn){displaystyle {frac {1}{n^{2}}}sum _{k=1}^{n}varphi (k)={frac {3}{pi ^{2}}}+{mathcal {O}}left({frac {log n}{n}}right)}{frac {1}{n^{2}}}sum _{{k=1}}^{n}varphi (k)={frac {3}{pi ^{2}}}+{mathcal {O}}left({frac {log n}{n}}right)

其中的O表示大O符号。这个等式也可以说明在集合 {1, 2, ..., n} 中随机选取两个数，则当n趋于无穷大时，它们互质的概率趋于 6/π2{displaystyle 6/pi ^{2}}6/pi ^{2} 。一个相关的结果是比值φ(n)/n{displaystyle varphi (n)/n}varphi (n)/n的平均值：


1n∑k=1nφ(k)k=6π2+O(log⁡nn).{displaystyle {frac {1}{n}}sum _{k=1}^{n}{frac {varphi (k)}{k}}={frac {6}{pi ^{2}}}+{mathcal {O}}left({frac {log n}{n}}right).}{frac {1}{n}}sum _{{k=1}}^{n}{frac {varphi (k)}{k}}={frac {6}{pi ^{2}}}+{mathcal {O}}left({frac {log n}{n}}right).


其他与欧拉函数有关的等式



  1. φ(nm)=nm−1φ(n){displaystyle ;varphi left(n^{m}right)=n^{m-1}varphi (n)};varphi left(n^{m}right)=n^{{m-1}}varphi (n)


  2. ∀a∈N,∀n∈N, ∃l∈N{displaystyle forall ain N,forall nin N, exists lin N}forall ain N,forall nin N, exists lin N 使得 [(a>1∧n>1)→(l|φ(an−1)∧l≥n)]{displaystyle [(a>1land n>1)rightarrow (l|varphi (a^{n}-1)land lgeq n)]}{displaystyle [(a>1land n>1)rightarrow (l|varphi (a^{n}-1)land lgeq n)]}


  3. ∀a∈N,∀n∈N, ∃l∈N{displaystyle forall ain N,forall nin N, exists lin N}forall ain N,forall nin N, exists lin N 使得 [(a>1∧n>6∧4∤n)→(l|φ(an−1)∧l≥2n)]{displaystyle [(a>1land n>6land 4nmid n)rightarrow (l|varphi (a^{n}-1)land lgeq 2n)]}{displaystyle [(a>1land n>6land 4nmid n)rightarrow (l|varphi (a^{n}-1)land lgeq 2n)]}

  4. ∑d∣nμ2(d)φ(d)=nφ(n){displaystyle sum _{dmid n}{frac {mu ^{2}(d)}{varphi (d)}}={frac {n}{varphi (n)}}}sum _{{dmid n}}{frac {mu ^{2}(d)}{varphi (d)}}={frac {n}{varphi (n)}}

  5. ∑1≤k≤n(k,n)=1k=12nφ(n) for n>1{displaystyle sum _{1leq kleq n atop (k,n)=1}!!k={frac {1}{2}}nvarphi (n){text{ for }}n>1}sum _{{1leq kleq n atop (k,n)=1}}!!k={frac {1}{2}}nvarphi (n){text{ for }}n>1

  6. ∑k=1nφ(k)=12(1+∑k=1nμ(k)⌊nk⌋2){displaystyle sum _{k=1}^{n}varphi (k)={frac {1}{2}}left(1+sum _{k=1}^{n}mu (k)leftlfloor {frac {n}{k}}rightrfloor ^{2}right)}sum _{{k=1}}^{n}varphi (k)={frac {1}{2}}left(1+sum _{{k=1}}^{n}mu (k)leftlfloor {frac {n}{k}}rightrfloor ^{2}right)

  7. ∑k=1nφ(k)k=∑k=1nμ(k)k⌊nk⌋{displaystyle sum _{k=1}^{n}{frac {varphi (k)}{k}}=sum _{k=1}^{n}{frac {mu (k)}{k}}leftlfloor {frac {n}{k}}rightrfloor }sum _{{k=1}}^{n}{frac {varphi (k)}{k}}=sum _{{k=1}}^{n}{frac {mu (k)}{k}}leftlfloor {frac {n}{k}}rightrfloor

  8. ∑k=1nkφ(k)=O(n){displaystyle sum _{k=1}^{n}{frac {k}{varphi (k)}}={mathcal {O}}(n)}sum _{{k=1}}^{n}{frac {k}{varphi (k)}}={mathcal {O}}(n)

  9. ∑k=1n1φ(k)=O(log⁡(n)){displaystyle sum _{k=1}^{n}{frac {1}{varphi (k)}}={mathcal {O}}(log(n))}sum _{{k=1}}^{n}{frac {1}{varphi (k)}}={mathcal {O}}(log(n))



与欧拉函数有关的不等式




  1. φ(n)>neγlog⁡log⁡n+3log⁡log⁡n{displaystyle varphi (n)>{frac {n}{e^{gamma };log log n+{frac {3}{log log n}}}}}varphi (n)>{frac {n}{e^{gamma };log log n+{frac {3}{log log n}}}}，其中n > 2，γ 为欧拉-马歇罗尼常数。


  2. φ(n)≥n2{displaystyle varphi (n)geq {sqrt {frac {n}{2}}}}varphi (n)geq {sqrt {{frac {n}{2}}}} ，其中n > 0。

  3. 对整数n > 6，φ(n)≥n{displaystyle varphi (n)geq {sqrt {n}}}varphi (n)geq {sqrt {n}}。

  4. 当n为质数时，显然有φ(n)=n−1{displaystyle varphi (n)=n-1}varphi (n)=n-1。对于合数的n，则有：


φ(n)≤n−n{displaystyle varphi (n)leq n-{sqrt {n}}}varphi (n)leq n-{sqrt {n}}


参考来源


  • Milton Abramowitz、Irene A. Stegun， Handbook of Mathematical Functions， (1964) Dover Publications , New York. ISBN 0-486-61272-4. 24.3.2节.

  • Eric Bach、Jeffrey Shallit， Algorithmic Number Theory, 卷 1, 1996, MIT Press. ISBN 0-262-02405-5, 8.8节，234页.

  • Kevin Ford, The number of solutions of φ(x)=m, Ann. of Math. 150(1999), 283--311.

  • 柯召，孙琦：数论讲义（上册），第二版，高等教育出版社，2001


文獻来源




  1. ^ Where does the word “totient” come from?


  2. ^ Mathematical Thought From Ancient to Modern Times, 第 2 卷，p.608


  3. ^ Mathematical Thought From Ancient to Modern Times, 第 3 卷，p.814




-

Popular posts from this blog

Y

Image
This article is about the letter of the alphabet. For other uses, see Y (disambiguation). See also: Wye (disambiguation) Y Y y (See below) Usage Writing system Latin script Type Alphabetic and Logographic Language of origin Latin language Phonetic usage [ y ] [ ɨ ] [ j ] [ iː ] [ ɪ ] [ ɘ ] [ ə ] [ ɯ ] [ ɛː ] [ j ] [ ɥ ] [ ɣ̟ ] / w aɪ / / aɪ / Unicode value U+0059, U+0079 Alphabetical position 25 History Development Υ υ 𐌖 Y y Time period 54 to present Descendants  • U  • V  • W  • Ỿ  • ¥  • Ꮙ  • Ꮍ  • Ꭹ Sisters F Ѵ У Ў Ұ Ү ו و ܘ וּ וֹ ࠅ 𐎆 𐡅 ወ વ ૂ ુ उ Variations (See below) Other Other letters commonly used with y(x), ly, ny This article contains IPA phonetic symbols. Without proper rendering support, you may see question marks, boxes, or other symbols instead of Unicode characters. For an introductory guide on IPA symbols, see Help:IPA. ISO basic Latin alphabet Aa Bb Cc D...
Read more

Mount Tamalpais

Image
Mount Tamalpais Mount Tamalpais, viewed from the south Highest point Elevation 2,571 ft (784 m)   NAVD 88 [1] Prominence 2,456 ft (749 m)  [1] Listing California county high points 55th Coordinates 37°55′45″N 122°34′40″W  /  37.929088°N 122.577829°W  / 37.929088; -122.577829 Coordinates: 37°55′45″N 122°34′40″W  /  37.929088°N 122.577829°W  / 37.929088; -122.577829   [1] Geography Mount Tamalpais Marin County, California, U.S. Show map of California Mount Tamalpais Mount Tamalpais (the US) Show map of the US Parent range California Coast Ranges Topo map USGS San Rafael Geology Mountain type Sedimentary Climbing First ascent 1830s by Jacob P. Leese (first recorded ascent) [2] Easiest route Railroad Grade fire trail Mount Tamalpais ( / t æ m əl ˈ p aɪ . ɪ s / ; TAM -əl- PY -iss ; Coast Miwok: /t̪ɑmɑlˈpɑis̺/ , known locally as Mount Tam ) is a peak in Marin County, California, United State...
Read more

Indian Forest Service

Image
Indian Forest Service Service Overview Preceding service Imperial Forest Service (1864 to 1935) Year of Constitution 1966 Country India Staff College Indira Gandhi National Forest Academy (IGNFA), Dehradun, Uttarakhand Cadre Controlling Authority Ministry of Environment, Forests and Climate Change Legal personality Governmental: Government service General nature Administration of Forest and Wildlife resources Cadre strength 3131 (2182 Direct Recruits and 949 Promotion Posts) Website ifs.nic.in Service Chief Director General of Forests Siddhanth Das, IFS (1982 Batch, Odisha Cadre) [1] Head of the All India Civil Services Cabinet Secretary Pradeep Kumar Sinha, IAS Indian Forest Service (भारतीय वन सेवा) [2] is one of the three All India Services of the Government of India. The other two All India Services being the Indian Administrative Service (IAS) and the Indian Police Service (IPS). [3] [4] [5] It was constituted in...
Read more