## 一、互质关系（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)
> $$
欧拉定理介绍
