一、互质关系(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
- 2、如果 n是某质数的某次方,n = p ^ k (p为质数, k为大于等于 1 的整数)
- 3、如果 n 可以分解为两个互质的整数乘积
那么,积的欧拉函数 等于 各个因数的欧拉函数之积
- 4、如果 n可以分解为一系列质数的乘积
那么,
三、欧拉定理
定义
如果两个正整数 a 和 n 是互质关系,那么有下列恒等式
或
费马小定理
如果正整数 a 和 质数 p 是互质关系,那么 p 的欧拉函数的值等于 p - 1
四、模反元素
如果两个正整数 a 和 n 互质,那么一定可以找到整数 b,使得 (ab -1) 能够被 n 整除 或 ab被 n 整除的余数是1