当前位置:主页 > 生活经验 > 正文

求逆元的方法及例题

逆元是指一个数的乘法逆元,它的定义是:如果一个数 $a$ 在模 $m$ 意义下存在乘法逆元 $b$,则有 $ab \\equiv 1 \\pmod m$在模意义下的逆元可以用于求解不定方程组、求解同。求逆元的方法及例题?更多详情请大家跟着小编一起来看看吧!

求逆元的方法及例题(1)

求逆元的方法及例题(1)

逆元是指一个数的乘法逆元,它的定义是:如果一个数 $a$ 在模 $m$ 意义下存在乘法逆元 $b$,则有 $ab \\equiv 1 \\pmod m$。

在模意义下的逆元可以用于求解不定方程组、求解同余方程组、解决线性同余方程、求模意义下的阶等问题。

求逆元的方法有如下几种:

先求出最大公约数,如果最大公约数为 $1$,则有逆元,否则无逆元。

扩展欧几里得算法,求出模意义下的逆元。

使用扩展欧几里得算法求出模意义下的逆元的迭代过程。

例题:

求解下列同余方程组:

$\\begin{cases} 2x \\equiv 3 \\pmod 5 \\ 3x \\equiv 2 \\pmod 7 \\end{cases}$

解:

根据求逆元的方法,我们可以求出 $2$ 在模 $5$ 意义下的逆元为 $3$,$3$ 在模 $7$ 意义下的逆元为 $5$。

于是,我们可以得到如下同余方程组:

$\\begin{cases} 2 \\cdot 3x \\equiv 3 \\cdot 3 \\pmod 5 \\ 3 \\cdot 5x \\equiv 2 \\cdot 5 \\pmod 7 \\end{cases}$

移项得到:

$\\begin{cases} 6x \\equiv 9 \\pmod 5 \\ 15x \\equiv 10 \\pmod 7 \\end{cases}$

猜你还喜欢的

Copyright © 2022 读周刊 All Rights Reserved
声明:本站部分内容来源于网络,如涉及侵权,请与我们联系,请发邮件"duzhoukan@foxmail.com"进行处理,谢谢合作!
渝ICP备2021012918号-4|