欧拉函数最全总结[通俗易懂]

欧拉函数最全总结[通俗易懂]文章目录欧拉函数的内容一、欧拉函数的引入二、欧拉函数的定义三、欧拉函数的性质四、欧拉函数的计算方法(一)素数分解法(二)编程思维1.求n以内的所有素数2.求φ(n)3.格式化输出0-100欧拉函数表(“x?”代表十位数,“x”代表个位数)五、欧拉函数相关定理以及证明(一)定理1:缩系与欧拉函数的关系(二)定理2:缩系的充要条件(三)定理3:缩系拓展1.简单证明:(a,m)=1,(x,m)=1,故(ax,m)=1。(四)定理4:设m>1,(a,m)=1,则aφ(m)≡1(modm).1.**若ac≡bc

欧拉函数的内容

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

一、欧拉函数的引入

首先引入互质关系:

如果两个正整数,除了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本身)。
  1. 函数表:

在这里插入图片描述

三、欧拉函数的性质

  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)=pk-pk-1=(p-1)pk-1
    当p为2时,pk-1必为偶数;
    当p>2时,(p-1)必为偶数。

四、欧拉函数的计算方法

(一)素数分解法

1.对于一个正整数N的素数幂分解N=P1q1P2q2…Pnqn,其中,Pi为素数(1≤i≤n)。

根据第二条性质得到:

φ(N)=φ(P1q1P2q2…Pnqn)=φ(P1q)φ(P2q2)…φ(Pnqn)

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

简单证明:φ(n)=pk-pk-1=(p-1)pk-1

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

(二)编程思维

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

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

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

亦即: φ ( N ) = N ∗ ∏ ( 1 − 1 / p ) ( P 是 数 N 的 质 因 数 ) φ(N)=N* ∏(1-1/p)(P是数N的质因数) φ(N)=N(11/p)PN
如:
φ(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):
    #判断如果x是素数,则打印,如果不是素数就跳过
        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:缩系的充要条件

若a1,…,aφ(m)是φ(m)个与m互素的整数,则a1,…,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。若ax1≡ax2(mod m),可得x1≡x2(mod m),与所设x通过模数m的缩系矛盾,故ax通过模数m的缩系。
证完

特别说明:根据定理:整数a,b对模数m同余的充分必要条件是m|a-b.
易得,ax1≡ax2(mod m)的充分必要条件是m|ax1-ax2=a(x1-x2),
又因为,(ax,m)=1,所有当且仅当,x1≡x2(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).

证: 设 r1,r2,…,rφ(m)是模数m的一组缩系,则由定理3,ar1,ar2,…,arφ(m)也是模数m的一组缩系,故
(ar1)(ar2)…(arφ(m))≡r1r2…rφ(m)(mod m),

aφ(m)r1r2…rφ(m)≡r1r2…rφ(m)(mod m) ①
由于
(ri,m)=1,i=1,2,…,φ(m),

(r1r2…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,有ap≡a(mod p).

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

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

(六)定理6:设m1>0,m2>0,(m1,m2)=1,x1,x2分别通过模数m1,m2的缩系,则m2x1+m1x2通过模数m1m2的缩系.

证: 首先证明(m2x1+m1x2,m1m2)=1。否则,有素数p,p|m2x1+m1x2,p|m1m2。如p|m1,则p|m2x1,而p∤x1,故p|m2,此与(m1,m2)=1矛盾;如p|m2,可得出相同的矛盾。这就证明x1,x2分别通过模数m1和m2的缩系时,φ(m1)* φ(m2)个数m2x1+m1x2均与m1m2互素。

反之,凡与m1m2互素之a有

a≡m2x1+m1x2(mod m1m2),(x1,m1)=(x2,m2)=1. ③

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

最后,再由设m1>0,m2>0,(m1,m2)=1,而x1,x2分别通过模数m1,m2的完全剩余系,则m2x1+m1x2通过模数m1m2的完全剩余系. 知m2x1+m1x2中任两个对模数m1m2不同余。
证完

由定理6,立得
推论: 若(m1,m2)=1,则φ(m1m2)=φ(m1)φ(m2).

(七)定理7:欧拉函数的一般计算方法

对于一个正整数n的素数幂分解n=P1q1P2q2…Pnqn,其中,Pi为素数(1≤i≤n),则φ(n)=n(1-1/P1)…(1-1/Pn).

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

六、欧拉函数的应用

(一)应用一:证明相关题目

证明:设n≥1,则有∑φ(n)=n,其中d|n,d>0.

证:对于一个正整数n的素数幂分解n=P1q1P2q2…Pnqn,其中,Pi为素数(1≤i≤n),d|n。

d=∑∑…∑P1x1P2x2…Pnxn(0≤x1≤q1,0≤x2≤q2,…,0≤xn≤qn)

所以,∑φ(n)=∑∑…∑φ(P1x1P2x2…Pnxn)(0≤x1≤q1,0≤x2≤q2,…,0≤xn≤qn)

根据推论6可得
∑φ(n)=∑φ(P1x1) ∑φP2x2) … ∑φ(Pnxn) (0≤x1≤q1,0≤x2≤q2,…,0≤xn≤qn)

根据1.4.1展开得

=[1+(P1 -1)+(P12-P1)…(P1q1-P1q1-1)]
[1+(P2 -1)+(P22-P2)…(P2q2-P2q2-1)]

[1+(Pn -1)+(Pn2-Pn)…(Pnqn-Pnqn-1)]
=P1q1P2q2…Pnqn
=n
证完

(二)应用二:求原根个数以及全部原根

1. 原根个数

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

2. 全部原根

特别地,若m=p为素数,则模p共有φ(p-1)个原根,并且若g为模p的一个原根,则模p的全部原根为{gk|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)=memodn

(6)将密文c解密为明文m,解密算法为

m=D( c )=cdmodn

  然而只根据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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/5939.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注