Read congruence in b module m
Many people must know the mod problem of integers. But sometimes we also encounter the mod problem of scores.
For example:
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 software will display: "Error, modulus inversion does not exist", that is, there is no output.
And we also found that: 2 * 4mod7 =1; 3 * 5 mod 7 = 1; 4 * 2 mod 7 = 1; 5 * 3 mod 7 = 1; 6 * 6 mod 7 = 1;
However, we can't find an integer m that makes 7 * m mod 7 =1; That's why we say "error, modular inversion does not exist".
For integers m, n, (m
Step (1): Find an integer p so that 1/m +p=( 1+p*m)/m, so that this integer (1+p*m) is a multiple of n, that is, (1+).
(2): The problem is transformed into 1/m ≡ -p mod n, and only the value of -p mod n needs to be obtained.
Example:
1/3 mod 7=? ; 1/3+2=7/3; -2 mod 7=5, which means1/3mod7 = 5;