Euler函数计算公式的证明研究

万文婷

(荆楚理工学院数理学院，湖北 荆门 448000)

Euler函数计算公式的证明研究

万文婷

(荆楚理工学院数理学院，湖北 荆门 448000)

利用孙子定理及排列组合中乘法原理的相关结论，讨论了特殊区间上与已知的n个素数p1,p2,…,pn互素的整数个数，并证明了Euler函数的计算公式。同时给出了对任意的正整数k和m，区间(m,m+kp1p2…pn]上与p1,p2,…,pn互素的整数个数等于k(p1-1)(p2-1)…(pn-1)的结论。

Euler函数；孙子定理；素数

Euler函数是数论中的一个重要函数。 设n为自然数，φ(n)表示不大于n且与n互素的自然数个数，φ(n)就称为Euler函数。Euler函数在数论中十分重要且有着广泛的应用，如在离散数学中求循环群的生成元、在计算机网络中的RSA公钥密码体制等。文献[1,2]中利用互素剩余系与简化剩余系的性质推得计算φ(n)的公式，文献[3,4]中又利用组合数学中的容斥原理证明了φ(n)的计算公式。笔者通过对特殊区间上与已知的n个素数p1,p2,…,pn互素的整数个数的讨论，也推得了φ(n)的计算公式，并得到了区间长度为kp1p2…pn(k∈Z+)的区间(m,m+kp1p2…pn](m∈Z+)上与p1,p2,…,pn互素的整数个数❶。

1 基本概念

用N(p1,p2,…,pn;A)表示集合A中与p1,p2,…,pn互素的整数个数。

引理1已知素数p1,p2,…,pn及常数c1,c2,…,cn，其中0≤cilt;pi,1≤i≤n，且ci∈N，则同余式组：

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

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

由孙子定理[1]，即得引理1。若设常数d1,d2,…,dn，其中0≤dilt;pi,1≤i≤n，且di∈N,同余式组：

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

的最小正整数解为b0，易推得a0≠b0的充要条件是至少有一个ci≠di，1≤i≤n。

引理2已知素数p1,p2,…,pn及任意常数c1,c2,…，cn，其中0≤cilt;pi,1≤i≤n且ci∈N，区间(0,p1p2…pn]上的任一整数必与一个同余式组：

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

的最小正整数解相等。

证明由于0≤cilt;pi,1≤i≤n，因此一组常数c1,c2,…,cn的不同取法共有p1p2…pn种，与其对应的共有p1p2…pn个不同的同余式组。再结合引理1知，这些不同的同余式组的最小正整数解都互不相同，且都属于区间(0,p1p2…pn]。而区间(0,p1p2…pn]上共有p1p2…pn个不同的正整数。所以，引理2成立。

2 主要结果

定理1区间(0,p1p2…pn]上与p1,p2,…,pn互素的整数个数为:

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

证明由引理2知，区间(0,p1p2…pn]上的任一与p1,p2,…,pn互素的整数b必与某一个同余式组：

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

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

所以，区间(0,p1p2…pn]上与p1,p2,…,pn互素的整数个数为(p1-1)(p2-1)…(pn-1)。

引理3区间(0,m]与(kp1p2…pn,m+kp1p2…pn]上与p1,p2,…,pn互素的整数个数相等，即：

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

证明令b=a+kp1p2…pn，a是区间(0,m]上与p1,p2,…,pn互素的整数的充要条件就是b是区间(kp1p2…pn,m+kp1p2…pn]上与p1,p2,…,pn互素的整数。所以，区间(0,m]与(kp1p2…pn,m+kp1p2…pn]上与p1,p2,…,pn互素的整数个数相同。

定理2区间(0,kp1p2…pn]上与p1,p2,…,pn互素的整数个数为：

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，可得如下结论：

定理3区间长度为kp1p2…pn的任意区间(m,m+kp1p2…pn]上与p1,p2,…,pn互素的整数个数为：

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

证明(1)当m≤kp1p2…pn时:

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)当mgt;kp1p2…pn时:

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]潘承洞,潘承彪.初等数论[M].北京:北京大学出版社,1992.

[2]闵嗣鹤,严士健.初等数论[M].北京:高等教育出版社,1982.

[3]王迪吉,方剑英.组合数学在数论中的应用实例[J].新疆师范大学学报(自然科学版),2002,12(4):6～9.

[4]陈碧琴.容斥原理在数论中的应用实例[J].绵阳师范学院学报,2004,4(2):25～28.

[编辑] 洪云飞

2009-07-29

万文婷(1982-)，女， 2003年大学毕业，硕士，讲师，现主要从事代数与数论方面的教学与研究工作。

❶荆楚理工学院科研项目(ZR200708)。

O156.1

[MR(2000)主题分类号]11A41

A

1673-1409(2009)04-N010-02