首先引入互质关系：
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。其次引进缩系得概念：
在与模数m互素的全部剩余类中，各取一数所组成的集叫做模数m的一组缩系。在讨论缩系的过程中，需要引入一个常用的数论函数–欧拉函数φ(n)。
请思考以下问题： 任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。
特别的，φ(1)=1（和1互质的数(小于等于1)就是1本身）。 函数表：当p是素数时，φ§=p-1。
欧拉函数是积性函数,但不是完全积性函数。
当且只当n可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)
特别的，对于两个素数p,q， φ（pq）=(p-1)(q-1)。(RSA算法应用）
当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的质因数） 如： φ（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。
模数m的一组缩系含有φ(m)个数。
若a1，…，aφ(m)是φ(m)个与m互素的整数，则a1，…，aφ(m)是模数m的一组缩系的充要条件是它们两两对模数m不同余。
定理1和定理2，根据缩系和欧拉函数的定义显然成立。若(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)，结论成立。
①：当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)，结论成立。 证完
证： 设 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). 证完
简单证明： 因为m|c(a-b)，故m/d|c/d(a-b),又因（m/d,c/d)=1,便知m/d|(a-b). 证完
简单证明： ①：若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). 证完
证： 首先证明（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).
对于一个正整数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 证完
若模m有原根，则原根共有φ(φ(m))个。
特别地，若m=p为素数，则模p共有φ(p-1)个原根，并且若g为模p的一个原根，则模p的全部原根为{gk|1≤k≤φ( p ),(φ( p ), k)=1}。
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）才可对密文解密 。
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