同余关系
定义
数学中同余关系是一种等价关系。当两个整数a, b除以同一个正整数n,若得到相同的余数,则这两个整数同余。记做
性质
整除性:a,b相减能被n整除
传递性:等价关系的共有特性
保持基本运算:(加减乘)
可进一步写成:
放大缩小底数:(对底数加减模数的倍数均可)
k为整数,n为正整数,
放大缩小模数:(对模数和等式两边的数同乘k)
还有几个性质,懒得码了,详见wiki:同余
欧拉函数
对正整数
欧拉定理
若
一般的证明中会用到“所有与 (开始后悔近世代数没认真学)
费马小定理
当n为素数的时候,,则
模逆元
整数 a 对模数 n 之模逆元存在的充分必要条件是 a 和 n 互素
如何求a 对模数 n 之模逆元?
由于a与n互质,所以可用欧拉定理,即
特别的,当n为质数时,根据费马小定理,a对模数n的模逆元是
还有个小trick:
求X的模MOD逆元时,若
v1.5.2