不是说————
用欧几里德算法求模的逆元：
同余方程ax≡b (mod n)，如果 gcd(a,n)== 1，则方程只有唯一解。
在这种情况下，如果 b== 1，同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。
这时称求出的 x 为 a 的对模 n 乘法的逆元。
对于同余方程 ax= 1(mod n )， gcd(a,n)= 1 的求解就是求解方程
ax+ ny= 1，x, y 为整数。这个可用扩展欧几里德算法求出，原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。
那么，b都已经为1了，为什么还会有最小正整数解？？
2 条评论
-
Souzou LV 9 @ 2016-11-18 10:01:23
注意，同余方程的解是指一个等价类。
-
@ 2016-11-10 14:13:11
同余方程ax≡b (mod n)，如果 gcd(a,n)== 1，则方程只有唯一解这句话似乎有问题吧……
扩展欧几里德算法只能求出这个方程的一组特解,用这组特解才可以得到通解……
所以才会要求最小正整数解-
@ 2016-11-11 15:14:16
那是不是就把同余方程看作ax-ny=b直接用扩展欧几米德去做？
-
@ 2016-11-11 23:00:02
是啊(其实减号可以写成加号)
-
@ 2016-11-12 00:11:03
谢谢
-
- 1
