一、互质关系（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

$$\phi(n) = n - 1$$

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

$$\phi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p}) = p^{k-1}(p+1)$$

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

$$n = p_1 \times p_2$$

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

$$\phi(n) = \phi(p_1p_2) = \phi(p_1)\phi(p_2)$$

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

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

那么，

$$\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^{\phi(n)} \equiv 1(mod\ n)$$

或

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

费马小定理

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

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

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

四、模反元素

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

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

# 欧拉定理 # RSA算法核心