Online Course Discussion Forum

MC II-A Number Theory 5.19

Picture of Zeyin Wu
MC II-A Number Theory 5.19
by Zeyin Wu - Thursday, 18 August 2022, 5:57 PM

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 142 (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.

Picture of John Lensmire
Re: MC II-A Number Theory 5.19
by John Lensmire - Monday, 22 August 2022, 11:18 AM

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!