分數mod

分數mod，是指高斯（Gauss，德國）給出的。兩個整數a，b，若它們除以整數m所得的餘數相等，則稱a，b對於模m同餘,記作 a ≡ b (mod m)。

基本介紹

• 中文名：分數mod
• 人物：高斯
• 國家：德國
• 公式： a ≡ b (mod m)

分數 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;