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