分数 mod

同余的概念是数学王子高斯（Gauss，德国）给出的。两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余,记作 a ≡ b (mod m)

读作a同余于b模m

关于整数的mod问题很多人想必都知道了吧。但是有时我们也会遇到分数的mod 问题。

比如说：

1/2 mod 7 = 4；

1/3 mod 7= 5;

1/4 mod 7=2;

1/5 mod 7=3;

1/6 mod 7=6;

1/7 mod 7 软件会显示：" Error, the modular inverse does not exist "，也就是这个没有输出

而且我们还发现：2*4 mod 7 =1 ；3*5 mod 7=1；4*2 mod 7=1；5*3 mod 7=1；6*6 mod 7=1;

但是，我们找不到一个整数m使得 7*m mod 7=1; 所以上面才会显示 " Error, the modular inverse does not exist ".

对于整数m ，n，（m<n）要求 1/m mod n=？

步骤(1): 找到一个整数p使得 1/m +p=(1+p*m)/m，使得整数(1+p*m)是n的倍数 ,也即 (1+p*m) mod n=0;

(2):问题转化为1/m ≡ -p mod n ,此时只要求得-p mod n 的值就可以了

例:

1/3 mod 7= ?; 1/3+2=7/3; -2 mod 7=5, 也就是1/3 mod 7= 5;