Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$.

share|improve this question
add comment

3 Answers 3

up vote -1 down vote accepted

Yes, it is...but $\,1/140=1/2=2\pmod 3\,$....:)

share|improve this answer
    
How is 2 mod 3 = 1/2? Now I think I'm missing something very basic.. –  James Oct 23 '12 at 4:57
    
$a/b\equiv c\pmod d$ is taken to mean $a\equiv bc\pmod d$. –  Gerry Myerson Oct 23 '12 at 4:58
    
I see. How do you get 1/140$\equiv$1/2 (mod 3)? –  James Oct 23 '12 at 5:03
    
$$140=2\pmod 3\Longrightarrow \frac{1}{140}=\frac{1}{2}=2^{-1}=2\pmod 3$$ –  DonAntonio Oct 23 '12 at 10:46
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.