欧拉定理介绍

欧拉定理介绍

艾瑞斯胡 408 2022-01-16

一、互质关系(coprime)

定义

如果两个正整数,除了 1 外,没有其他的公因数,那么称这两个正整数是 互质关系

比如:18 和 29 没有公因数,它们是互质关系

推论

1、任意两个质数一定构成互质关系

比如:5 和 7

2、一个是质数,另一个只要不是前者的倍数,也一定构成互质关系

比如:5 和 11

3、两个数,较大的那个是质数,那两者也构成互质关系

比如:41 和 20

4、1和任何一个自然数都构成互质关系

5、如果 p是大于 1的正整数,那么 p 和 p -1 一定构成互质关系

6、如果 p 是大于1的正奇数,那么 p 和 p-2 一定构成互质关系

二、欧拉函数

定义

任意一个正整数 n,在小于等于它的正整数中,寻找与它构成互质关系的整数的个数,称为欧拉函数,用Φ(n)表示

比如:1到9中,与 9 形成互质关系的有1、2、4、5、7、8

推论

  • 1、如果 n是质数,那么它的互质整数个数为 n - 1

ϕ(n)=n1\phi(n) = n - 1

  • 2、如果 n是某质数的某次方,n = p ^ k (p为质数, k为大于等于 1 的整数)

ϕ(pk)=pkpk1=pk(11p)=pk1(p+1)\phi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p}) = p^{k-1}(p+1)

  • 3、如果 n 可以分解为两个互质的整数乘积

n=p1×p2n = p_1 \times p_2

那么,积的欧拉函数 等于 各个因数的欧拉函数之积

ϕ(n)=ϕ(p1p2)=ϕ(p1)ϕ(p2)\phi(n) = \phi(p_1p_2) = \phi(p_1)\phi(p_2)

  • 4、如果 n可以分解为一系列质数的乘积

n=p1k1p2k2...prkrn = {p_1^{k1}}{p_2^{k2}}...{p_r^{kr}}

那么,

ϕ(n)=ϕ(p1k1)ϕ(p2k2)...ϕ(prkr)=(p1k1p2k2...prkr)(11p1)(11p2)...(11pr)=n(11p1)(11p2)...(11pr)\phi(n)=\phi({p_1^{k1}})\phi({p_2^{k2}})...\phi({p_r^{kr}}) = ({p_1^{k1}}{p_2^{k2}}...{p_r^{kr}})(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r}) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r})

三、欧拉定理

定义

如果两个正整数 a 和 n 是互质关系,那么有下列恒等式

aϕ(n)1(mod n)a^{\phi(n)} \equiv 1(mod\ n)

aϕ(n)1kna^{\phi(n)} - 1 \equiv kn

费马小定理

如果正整数 a 和 质数 p 是互质关系,那么 p 的欧拉函数的值等于 p - 1

aϕ(p)=ap1a^{\phi(p)} = a^{p-1}

ap11(mod p)a^{p-1} \equiv 1(mod \ p)

四、模反元素

如果两个正整数 a 和 n 互质,那么一定可以找到整数 b,使得 (ab -1) 能够被 n 整除 或 ab被 n 整除的余数是1

ab1(mod n)ab \equiv 1(mod \ n)


# 欧拉定理 # RSA算法核心