主题:[讨论]大家告诉我一下求35模3的逆的过程
小弟刚开始看离散数学。看的是《离散数学及其应用》(原书第5版)
现在学到离散数学第2章线性同余那节了。
但是对于模的逆运算还是没搞明白
对于35模3的逆还是没明白是怎么算的(书上答案是2)
书上说 如果a和m互为素数,m>1,则存在a的模m的逆。而且这个逆模m是唯一的。
一个在a和m互素的条件下求a的模m的方法:求a和m的线性组合使之等于1(按欧几里德算法步骤倒过来做即可);这一线性组合中a的系数就是a模m的一个逆
例题是求3模7的逆
解:由于gcd(3,7)=1,说明存在3模7的逆。若用欧几里德算法求3和7的最大公约数,算法很快结束: 7=2*3+1,从这一等式看到 -2*3+1*7=1。
这说明-2是3模7的一个逆。
我做35模3的逆
我只能分解成 35=3*11+2
2=-11*3+1*35
求大家帮帮忙吧
给个详细的步骤
小弟谢谢了
现在学到离散数学第2章线性同余那节了。
但是对于模的逆运算还是没搞明白
对于35模3的逆还是没明白是怎么算的(书上答案是2)
书上说 如果a和m互为素数,m>1,则存在a的模m的逆。而且这个逆模m是唯一的。
一个在a和m互素的条件下求a的模m的方法:求a和m的线性组合使之等于1(按欧几里德算法步骤倒过来做即可);这一线性组合中a的系数就是a模m的一个逆
例题是求3模7的逆
解:由于gcd(3,7)=1,说明存在3模7的逆。若用欧几里德算法求3和7的最大公约数,算法很快结束: 7=2*3+1,从这一等式看到 -2*3+1*7=1。
这说明-2是3模7的一个逆。
我做35模3的逆
我只能分解成 35=3*11+2
2=-11*3+1*35
求大家帮帮忙吧
给个详细的步骤
小弟谢谢了