0%

几个重要数论结论的总结

同余关系

定义

数学中同余关系是一种等价关系。当两个整数a, b除以同一个正整数n,若得到相同的余数,则这两个整数同余。记做ab  (modn).

性质

整除性:a,b相减能被n整除

传递性:等价关系的共有特性

ab(modm)bc(modm)}ac(modm)

保持基本运算:(加减乘)

ab(modm)cd(modm)}{a±cb±d(modm)acbd(modm)

可进一步写成:

ab(modm){anbn(modm),nZanbn(modm),nN0

放大缩小底数:(对底数加减模数的倍数均可)

k为整数,n为正整数,(km±a)n(±a)n(modm)

放大缩小模数:(对模数和等式两边的数同乘k)

k为正整数,ab(modm),当且仅当kakb(modkm)

还有几个性质,懒得码了,详见wiki:同余

欧拉函数

对正整数n,欧拉函数φ(n)为小于等于n的正整数中,与n互质的数的个数。

欧拉定理

n,a为正整数,且n,a互素(即gcd(n,a)=1) ,则a(n).

一般的证明中会用到“所有与 n互质的同余类构成一个”的性质,也就是说,设 {a1,a2,,aφ(n)}是比 n 小的正整数中所有与n互素的数对应的同余类组成的集合(这个集合也称为模n简化剩余系)。这些同余类构成一个群,称为整数模n乘法群。因为此群阶为φ(n),所以 a(n)(开始后悔近世代数没认真学)

费马小定理

当n为素数的时候,,则φ(n)=n1,即an11  (modn).

模逆元

整数a对同余n的模逆元是指满足ab1 (modn)的整数 b。

整数 a 对模数 n 之模逆元存在的充分必要条件是 a 和 n 互素

如何求a 对模数 n 之模逆元?

由于a与n互质,所以可用欧拉定理,即aφ(n)=aaφ(n)11  (modn),即a对模数n的模逆元是aφ(n)1

特别的,当n为质数时,根据费马小定理,a对模数n的模逆元是an2。(这样就可使用快速幂在log(n)时间求出a的逆元)

还有个小trick:

求X的模MOD逆元时,若X | (MOD+1),则X的模逆元可表示成MOD+1X。比如当MOD为奇数时,2的逆元是MOD+12

来发评论吧~
Powered By Valine
v1.5.2