回 帖 发 新 帖 刷新版面

主题:[讨论]大家告诉我一下求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

求大家帮帮忙吧
给个详细的步骤 
小弟谢谢了

回复列表 (共4个回复)

沙发

我没有学过离散,但是学过数论,可以给你讲一下
35=2+3*11
3=2*1+1
所以35=2+(2*1+1)*11
展开就得1=3*12-35   我觉得这种方法有点麻烦

还可以给你第二种方法,就是用解一次同余的方法,不知道你看过没有。
可以看做解一次同余35x=1(mod 3)   (同余符号我用等号代替,打不出来)
解这个就好了。

板凳

谢谢了
我看的就是线性同余
解一次同余35x=1(mod 3)
我是想问解这个的过程。
书上没写过程  就直接给了答案2.

3 楼


一般的话解线性同余有三种方法,一般的数论书上都有的,你先找下哈,找不到的话我再给你讲。

4 楼

恩  谢谢了.

我来回复

您尚未登录,请登录后再回复。点此登录或注册