同余

作者: dachengquan | 来源:发表于2020-08-04 20:30 被阅读0次

定义
若整数a和整数b，除以正整数m得到的余数相等，成a，b模m同余，记作 $a\equiv b \pmod m$ 。
费马小定理
若p是质数，gcd(a,p)=1,那么有 $a^{p-1}\equiv 1 \pmod p$
欧拉定理
若p是质数，gcd(a,n)=1,那么有 $a^{\varphi(n)} \equiv 1 \pmod n$
欧拉定理推论
若正整数a，n互质，则对于任意的 $a^b \equiv a^{b \pmod {\varphi(n)}} \pmod n$
当a，n不一定互质时 $b>\varphi(n)$ 也满足 $a^b \equiv a^{b \pmod {\varphi(n)}+\varphi(n)} \pmod n$ 原因在于指数循环节，第 $\varphi(n)$ 个往后一定会循环，
扩展欧几里得算法
对于任意整数a，b，存在一对整数x，y，满足ax+by=gcd(a,b)。
证明：
当b=0时显然x=1，y=0是一组解。
若b>0，则 $gcd(a,b)=gcd(b,a\pmod b)$ ,假设存在一对整数满足x，y满足 $b*x+(a\mod b)*y= gcd(b,a\mod b)$
$b*x + (a-b*\lfloor a/b \rfloor)y =gcd(b,a\mod b)$
$ay+b(x-\lfloor a/b \rfloor y)=gcd(b,a\mod b)$
令 $x' = y,y' = (x-\lfloor a/b \rfloor y)$ 就得到了
$a*x'+b*y' = gcd(a,b)$
对欧几里得算法的递归过程应用数学归纳法，显然成立。
这里求出的 $x_0，y_0$ 是一组特解。
d = gcd(a,b)
对于更为一般的方程：ax+by=c,它有解当且仅当 $d|c$
他的通解为
$x = \frac c d x_0 + k \frac b d,y = \frac c d y_0 - k \frac a d$
乘法逆元
若b，m互质，并且b|a,则存在一个整数x，使得 $a/b \equiv a*x \pmod m$ ,称x为b的模m乘法逆元，记为 $b^{-1} \pmod m$
$b*b{-1}\equiv 1 \pmod m$
如果m是质数根据费马小定理 $b*b^{p-2} \equiv 1 \pmod p$ ,显然 $b^{p-2} \mod p$ 是乘法逆元。
如何只满足b，m互质那么求解同余方程 $b*x\equiv 1\pmod m$
线性同余方程的求解
$a*x\equiv b \pmod m$
可以变为另一种形式， $a*x - m*y \equiv b$ 求解这个方程的方法在前面已经讲解过了。最后我们需要得到一个在区间0到m的逆元

a
a
a
a
a
a
a
a

同余

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读