当前位置:婀娜女性网>美好生活>心理>

求逆元的方法及例题

心理 阅读(1.16W)
求逆元的方法及例题

逆元是指一个数的乘法逆元,它的定义是:如果一个数 $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}$