Online Course Discussion Forum
MC II-A Number Theory 5.19
For this question, I understand how to get the modular multiplicative inverse of gcd (5,12)=1, which is 5, but I don't quite fathom how it is useful for obtaining the answer to the variable m in 14≡2 (mod m), which is clearly 12. Thanks!
Just another quick note: For 5.20, I believe that the answer explanation should began with gcd (2, 12)=2 instead of gcd (5,12)=2, which is from the previous question 5.19. I think it's just some typo stuff that isn't a big deal.
First off, thanks for pointing on 5.20, that should be fixed now.
For your question, you're correct that both 5.19 and 5.20 can be answered without looking at the gcds.
We want the largest m that is a factor of 12 so that $14\equiv 2 \pmod{m}$ in 5.19 (which is m=12) and so that $35\equiv 5 \pmod{m}$ in 5.20 (which is m = 6).
However, it is good to understand the connection of these problems to the idea of mod. multiplicative inverses and the question "when can we dividing using mods?". As mentioned in the chapter, we need to be careful with division, and typically want to think of "multiplying by the mod. multiplicative inverse" instead of dividing. This inverse exists when the gcd is 1. Hence,
- In 5.19, since gcd(5,12)=1, we're allowed to "divide by 5" so clearly the statement is still true when m=12.
- In 5.20, since gcd(2,12) is not 1, we're not allowed to "divide by 2" so we know the answer cannot be m=12.
Hope this helps!
社交网络