In the Chinese Remainder Thm., $y_i$ is the modular inverse of $\frac{P}{p_i}$, where $p_i$ is the $i$th modulus in a set of $n$ congruencies and $P$ is $\prod_{i=1}^np_i$ (right?). So if I calculated $P$ to be 420 and $p_1=3$, why is $y_1\equiv140^{-1}\mod3 = 2$? Is $140^{-1}$ in this case not $\frac{1}{140}$? I would think $140^{-1}\mod 3$ would be a non-integer, namely $\frac{1}{140}$.
Modulus of inverse of a number
3 Answers
Yes, it is...but $\,1/140=1/2=2\pmod 3\,$....:)
-
0$140=2\pmod 3\Longrightarrow \frac{1}{140}=\frac{1}{2}=2^{-1}=2\pmod 3$ – 2012-10-23
The notation $a^{-1}$ just means the multiplicative inverse, meaning a number such that if I multiply it by $a$ I will get the multiplicative identity. So in the real numbers $a^{-1}$ just happens to be $1/a$ so when I multiply $a$ with $1/a$ then I get 1. When doing modular arithmetic, the definition of $a^{-1}$ is the same but writing it as a fraction doesn't make sense. So working modulo 3, first note that $140=2$ so $140^{-1}=2^{-1}$ and which number multiplied by 2 gives you 1 mod 3? It is 2 because 2 is its own inverse mod 3.
So $140^{-1}=2^{-1}=2$ mod 3. Some people choose to give a meaningful interpretation to fraction in modular arithmetic too so you can say 1/2 mod 3 but remember that it really means $2^{-1}$. This is what Don Antonio is doing.
140−1mod3 is not to mean 1/140mod3. I mean it is not an arithmetic inverse. Instead it is a modulo inverse. Therefore to find the modulo inverse of a number you have to follow the following 2 steps:# step 1. Calculate A * B mod C for B values 0 through C-1 step 2. The modular inverse of A mod C is the B value that makes A * B mod C = 1 Note that the term B mod C can only have an integer value 0 through C-1, so testing larger values for B is redundant.