欧拉函数的内容

• 欧拉函数的引入
• 欧拉函数的定义
• 欧拉函数的基本性质
• 欧拉函数的计算方法
• 欧拉函数的相关定理以及证明
• 欧拉函数的应用

一、欧拉函数的引入

首先引入互质关系：

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

其次引进缩系得概念：

在与模数m互素的全部剩余类中，各取一数所组成的集叫做模数m的一组缩系。

在讨论缩系的过程中，需要引入一个常用的数论函数–欧拉函数φ(n)。

请思考以下问题：  

  任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）

计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。

二、欧拉函数的定义

1. 定义： 欧拉函数φ(n)是一个定义在正整数集上得函数，φ(n)的值等于序列0，1，2，…，n-1中与n互素的数的个数。

此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。

特别的，φ(1)=1（和1互质的数(小于等于1)就是1本身）。

2. 函数表：

三、欧拉函数的性质

1. 当p是素数时，φ§=p-1。

2. 欧拉函数是积性函数,但不是完全积性函数。

   当且只当n可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)

   特别的，对于两个素数p,q， φ(pq)=(p-1)(q-1)。(RSA算法应用）

3. 当n＞2时,φ(n)都是偶数，也即φ(n)≡0（mod2)。

   简单证明，因为若n是质数p的k次幂，φ(n)=p^k-p^k-1=(p-1)p^k-1
   当p为2时，p^k-1必为偶数;
   当p＞2时，(p-1)必为偶数。

四、欧拉函数的计算方法

（一）素数分解法

1.对于一个正整数N的素数幂分解N=P₁^q₁P₂^q₂…P_n^q_n，其中，Pi为素数（1≤i≤n)。

根据第二条性质得到：

φ(N)=φ(P₁^q₁P₂^q₂…P_n^q_n)=φ(P₁^q)φ(P₂^q₂)…φ(P_n^q_n)

注意：每种质因数只有一个。
若n是质数p的k次幂，φ(n)=p^k-p^k-1=(p-1)p^k-1，因为除了p的倍数外，其他数都跟n互质。

简单证明：φ(n)=p^k-p^k-1=(p-1)p^k-1

证明：
由φ(n)的定义值，φ(p^k)等于从p^k减去在1，…，p^k中与p不互素的数的个数。因为p是素数，故φ(p^k)等于从p^k减去在1，…，p^k中被p整除的数的个数。而在
1，…，p，p+1，…，2p，…，p^a-1 * p
中，易知p的倍数共有p^a-1个，即得φ(n)=p^k-p^k-1=(p-1)p^k-1
证完

（二）编程思维

利用欧拉函数和它本身不同质因数的关系，用筛法计算出某个范围内所有数的欧拉函数值。

欧拉函数和它本身不同质因数的关系：

欧拉函数: φ(N)=N{∏p|N}(1-1/p)

亦即: $$\phi (N)=N\ast \prod (1-1/p)（P是数N的质因数）$$
如：
φ（10）=10×（1－1/2）×（1－1/5）=4； 10的质因数为2，5；
φ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8； 30的质因数为2，3，5；
φ（49）=49×（1－1/7）=42。 49的质因数为7。

1.求n以内的所有素数

#l[]
def prime(n):
    #global l=[] # 全局变量
    global l
    l=[]
    for x in range(n):
    #判断如果ｘ是素数，则打印，如果不是素数就跳过
        if x <2:
            continue
        for i in range(2,x):
            if x % i == 0:
                break
        else:
            l.append(x)
    print(l)
    
prime(100)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

2.求φ(n)

def phi(n):
    ans=n
    for i in l:
        if(n%i==0):
            ans=ans*(1-1/i)#等价于通项，把n乘进去
           
    return (int(ans))
phi(100)

#for i in range(1,10):
   # print(phi(i))

40

3.格式化输出0-100欧拉函数表（“x?”代表十位数，“x”代表个位数）

• 步骤一：输出表头和表格横向数值

print("{:>40}".format("0~100欧拉函数表（“x?”代表十位数，“x”代表个位数）"))
print()
print ("{:>6}".format("φ(n)"),end='')
for x in range(0,10):
    print ("{:>6}".format(x),end='')

          0~100欧拉函数表（“x?”代表十位数，“x”代表个位数）

  φ(n)     0     1     2     3     4     5     6     7     8     9

• 步骤二：输出表格横向和纵向数值

print("{:>40}".format("0~100欧拉函数表（“x?”代表十位数，“x”代表个位数）"))
print()
print ("{:>6}".format("φ(n)"),end='')
for x in range(0,10):
    print ("{:>6}".format(x),end='')

for x in range(0,10):
    print ("\n")
    print ("{:>6}".format(str(x)+"?"),end='')

          0~100欧拉函数表（“x?”代表十位数，“x”代表个位数）

  φ(n)     0     1     2     3     4     5     6     7     8     9

    0?

    1?

    2?

    3?

    4?

    5?

    6?

    7?

    8?

    9?

• 步骤三： 输出最终效果

import termcolor
#title=termcolor.colored("0~100欧拉函数表（“x?”代表十位数，“x”代表个位数）",'white','on_red',['bold'])
title=termcolor.colored("0~100欧拉函数表（“x?”代表十位数，“x”代表个位数）",color=None,on_color=None,attrs=['bold']) #加粗
print("{0:^70}".format(title))
print()
print ("{:>7}".format("φ(n)"),end='')
for x in range(0,10):
    print ("{:>7}".format(x),end='')

for x in range(0,10):
    a=x*10
    print ("\n")
    print ("{:>8}".format(str(x)+"?"),end='')
    for y in range(0+a,10+a):
        print("{0:>7}".format(phi(y)),end='')

print()
print()
#print("φ(100)=",phi(100))
print("{:>40}{:}".format("φ(100)=",phi(100)))

                0~100欧拉函数表（“x?”代表十位数，“x”代表个位数）              

   φ(n)      0      1      2      3      4      5      6      7      8      9

      0?      0      1      1      2      2      4      2      6      4      6

      1?      4     10      4     12      6      8      8     16      6     18

      2?      8     12     10     22      8     20     12     18     12     28

      3?      8     30     16     20     16     24     12     36     18     24

      4?     16     40     12     42     20     24     22     46     16     42

      5?     20     32     24     52     18     40     24     36     28     58

      6?     16     60     30     36     32     48     20     66     32     44

      7?     24     70     24     72     36     40     36     60     24     78

      8?     32     54     40     82     24     64     42     56     40     88

      9?     24     72     44     60     46     72     32     96     42     60

                                 φ(100)=40

五、欧拉函数相关定理以及证明

（一）定理1：缩系与欧拉函数的关系

模数m的一组缩系含有φ(m)个数。

（二）定理2：缩系的充要条件

若a₁，…，a_φ(m)是φ(m)个与m互素的整数，则a₁，…，a_φ(m)是模数m的一组缩系的充要条件是它们两两对模数m不同余。

定理1和定理2，根据缩系和欧拉函数的定义显然成立。

（三）定理3：缩系拓展

若(a,m)=1,x通过模数m的缩系，则ax也通过模数m的缩系。

证：当x通过模数m的缩系，则ax通过φ(m)个整数，由于(a,m)=1，(x,m)=1，故(ax,m)=1。若ax₁≡ax₂(mod m)，可得x₁≡x₂(mod m)，与所设x通过模数m的缩系矛盾，故ax通过模数m的缩系。
证完

特别说明：根据定理：整数a,b对模数m同余的充分必要条件是m|a-b.
易得，ax₁≡ax₂(mod m)的充分必要条件是m|ax₁-ax₂=a(x₁-x₂)，
又因为，(ax,m)=1，所有当且仅当，x₁≡x₂(mod m)，结论成立。

1. 简单证明：(a,m)=1，(x,m)=1，故(ax,m)=1。

①：当m=0时，a=±1,结论成立。
②：当a=0时，m=±1，且(0,m)=(0,m)，结论成立。
③：当am≠0时，(a,m)=(a(x,m),m)=((ax,am),m)=(ax,m(a,1))=(ax,m)，结论成立。
证完

（四）定理4：设m＞1，(a,m)=1,则a^φ(m)≡1(mod m).

证： 设 r₁，r₂，…，r_φ(m)是模数m的一组缩系，则由定理3，ar₁，ar₂，…，ar_φ(m)也是模数m的一组缩系，故
（ar₁)(ar₂)…(ar_φ(m))≡r₁r₂…r_φ(m)(mod m)，
即
a^φ(m)r₁r₂…r_φ(m)≡r₁r₂…r_φ(m)(mod m) ①
由于
（r_i,m)=1，i=1,2,…,φ(m),
故
(r₁r₂…r_φ(m)，m)=1. ②
根据定理：若ac≡bc(mod m),且若(m,c)则a≡b(mod m/d). 再由②和①得
a^φ(m)≡1(mod m).
证完

1. 若ac≡bc(mod m),且若(m,c)则a≡b(mod m/d).

简单证明：
因为m|c(a-b)，故m/d|c/d(a-b),又因（m/d,c/d)=1,便知m/d|(a-b).
证完

（五）定理5：若p是素数，则对于每个整数a，有a^p≡a(mod p).

由定理4立刻推得定理5，它通常叫做费马小定理。

简单证明：
①：若a不是p的倍数，又因p为素数，则有(a,p)=1,
则由欧拉定理可得，也即定理4，a^φ(m)≡1(mod m)，
又根据性质1，得到φ§=p-1，所以a^p-1≡1(mod p),
等式两边乘以a，可得a^p≡a(mod p).
②：若a是p的倍数，也即不互质，a(mod p)≡a^p(mod p)≡0,
可以表示为：a^p≡a(mod p).
证完

（六）定理6：设m₁＞0，m₂＞0，(m₁,m₂)=1，x₁,x₂分别通过模数m₁,m₂的缩系，则m₂x₁+m₁x₂通过模数m₁m₂的缩系.

证： 首先证明（m₂x₁+m₁x₂,m₁m₂)=1。否则，有素数p，p|m₂x₁+m₁x₂，p|m₁m₂。如p|m₁,则p|m₂x₁,而p∤x₁，故p|m₂，此与（m₁,m₂)=1矛盾；如p|m₂，可得出相同的矛盾。这就证明x₁,x₂分别通过模数m₁和m₂的缩系时，φ(m₁)* φ(m₂)个数m₂x1+m₁x₂均与m₁m₂互素。

反之，凡与m₁m₂互素之a有

a≡m₂x₁+m₁x₂(mod m₁m₂),(x₁,m₁)=(x₂,m₂)=1. ③

这是因为，由定理:设m₁＞0，m₂＞0，(m₁,m₂)=1，而x₁,x2分别通过模数m₁,m2的完全剩余系，则m₂x₁+m₁x₂通过模数m₁m₂的完全剩余系. 知有x₁和x₂使a≡m₂x₁+m₁x₂(mod m₁m₂)，所以只需证明当(a,m₁m₂)=1时，（x₁,m₁)=(x₂,m₂)=1。如果（x₁,m₁)>1，则有素数q，q|x₁，q|m₁。而a≡m₂x₁+m₁x₂(mod m₁m₂)，由此推出q|a，与(a,m₁m₂)=1矛盾，故（x₁,m₁)=1。同理可证(x₂,m₂)=1。

最后，再由设m₁＞0，m₂＞0，(m₁,m₂)=1，而x₁,x₂分别通过模数m₁,m₂的完全剩余系，则m₂x₁+m₁x₂通过模数m₁m₂的完全剩余系. 知m₂x₁+m₁x₂中任两个对模数m₁m₂不同余。
证完

由定理6，立得
推论: 若（m₁,m₂)=1,则φ(m₁m₂)=φ(m₁)φ(m₂).

（七）定理7：欧拉函数的一般计算方法

对于一个正整数n的素数幂分解n=P₁^q1P₂^q2…P_n^qn，其中，Pi为素数（1≤i≤n)，则φ(n)=n(1-1/P₁)…(1-1/P_n).

证明过程参考1.4.1以及定理6的推论。

六、欧拉函数的应用

（一）应用一：证明相关题目

证明：设n≥1，则有∑φ(n)=n，其中d|n，d＞0.

证：对于一个正整数n的素数幂分解n=P₁^q₁P₂^q₂…P_n^q_n，其中，Pi为素数（1≤i≤n)，d|n。

d=∑∑…∑P₁^x₁P₂^x₂…P_n^x_n(0≤x₁≤q₁,0≤x₂≤q₂,…,0≤x_n≤q_n)

所以，∑φ(n)=∑∑…∑φ(P₁^x₁P₂^x₂…P_n^x_n)(0≤x₁≤q₁,0≤x₂≤q₂,…,0≤x_n≤q_n)

根据推论6可得
∑φ(n)=∑φ(P₁^x₁) ∑φP₂^x₂) … ∑φ(P_n^x_n) (0≤x₁≤q₁,0≤x₂≤q₂,…,0≤x_n≤q_n)

根据1.4.1展开得

=[1+(P₁ -1)+(P₁²-P₁)…(P₁^q₁-P₁^q_1-1)]
[1+(P₂ -1)+(P₂²-P₂)…(P₂^q₂-P₂^q_2-1)]
…
[1+(P_n -1)+(P_n²-P_n)…(P_n^q_n-P_n^q_n-1)]
=P₁^q1P₂^q2…P_n^qn
=n
证完

（二）应用二：求原根个数以及全部原根

1. 原根个数

若模m有原根，则原根共有φ(φ(m))个。

2. 全部原根

特别地，若m=p为素数，则模p共有φ(p-1)个原根，并且若g为模p的一个原根，则模p的全部原根为{g^k|1≤k≤φ( p ),(φ( p ), k)=1}。

（三）应用三：RSA算法

RSA算法的具体描述如下：
（1）任意选取两个不同的大素数p和q计算乘积n=pq,φ(n)=(p-1)(q-1) ；

（2）任意选取一个大整数e，满足gcd(e,φ(n))=1 ，整数e用做加密钥（注意：e的选取是很容易的，例如，所有大于p和q的素数都可用）；

（3）确定的解密钥d，满足 (de)modφ(n)=1，即de=kφ(n)+1,k≥1 是一个任意的整数；所以，若知道e和φ(n)，则很容易计算出d；

（4）公开整数n和e，秘密保存d；

（5）将明文m（m<n是一个整数）加密成密文c，加密算法为

c=E(m)=m^emodn

（6）将密文c解密为明文m，解密算法为

m=D( c )=c^dmodn

  然而只根据n和e（注意：不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密 。

测试

（一）termcolor库的使用

import termcolor

dir(termcolor)

['ATTRIBUTES',
 'COLORS',
 'HIGHLIGHTS',
 'RESET',
 'VERSION',
 '__ALL__',
 '__builtins__',
 '__cached__',
 '__doc__',
 '__file__',
 '__loader__',
 '__name__',
 '__package__',
 '__spec__',
 'colored',
 'cprint',
 'os',
 'print_function']

help(termcolor)

Help on module termcolor:

NAME
    termcolor - ANSII Color formatting for output in terminal.

FUNCTIONS
    colored(text, color=None, on_color=None, attrs=None)
        Colorize text.
        
        Available text colors:
            red, green, yellow, blue, magenta, cyan, white.
        
        Available text highlights:
            on_red, on_green, on_yellow, on_blue, on_magenta, on_cyan, on_white.
        
        Available attributes:
            bold, dark, underline, blink, reverse, concealed.
        
        Example:
            colored('Hello, World!', 'red', 'on_grey', ['blue', 'blink'])
            colored('Hello, World!', 'green')
    
    cprint(text, color=None, on_color=None, attrs=None, **kwargs)
        Print colorize text.
        
        It accepts arguments of print function.

DATA
    ATTRIBUTES = {'blink': 5, 'bold': 1, 'concealed': 8, 'dark': 2, 'rever...
    COLORS = {'blue': 34, 'cyan': 36, 'green': 32, 'grey': 30, 'magenta': ...
    HIGHLIGHTS = {'on_blue': 44, 'on_cyan': 46, 'on_green': 42, 'on_grey':...
    RESET = '\x1b[0m'
    VERSION = (1, 1, 0)
    __ALL__ = ['colored', 'cprint']
    print_function = _Feature((2, 6, 0, 'alpha', 2), (3, 0, 0, 'alpha', 0)...

​
​

print(termcolor.colored("error","red"))

[31merror[0m

print(termcolor.colored("error","red",'on_red',['red', 'bold']))

---------------------------------------------------------------------------

KeyError                                  Traceback (most recent call last)

<ipython-input-125-7c06270d31d5> in <module>
----> 1 print(termcolor.colored("error","red",'on_red',['red', 'bold']))


c:\users\tianjie\test1\lib\site-packages\termcolor.py in colored(text, color, on_color, attrs)
    110         if attrs is not None:
    111             for attr in attrs:
--> 112                 text = fmt_str % (ATTRIBUTES[attr], text)
    113 
    114         text += RESET


KeyError: 'red'

from termcolor import colored, cprint

text = colored('Hello, World!', 'white','on_red',attrs=['reverse', 'bold'])
print(text)
cprint('Hello, World!', 'green', 'on_red')

[1m[7m[41m[37mHello, World![0m
[41m[32mHello, World![0m

（二）全局变量和局部变量

声明和定义不能同时进行

a=2
#print(a)
def sum(b):
    #print(a) #会报错
    #global a=3 #会报错
    global a  #声明
    a=3
    print(a)
    
print(a)

sum(5)

sum(6)

2
3
3

a=2
print(a)
def sum(b):
    #print(a) #会报错
    #global a=3 #会报错
    global a  #声明
    a=3
    print(a)
    
print(a)  #调用前 
sum(5)    
print(a)  #调用后



sum(6)

2
2
3
3
3