Online Course Discussion Forum

MC II-A Number Theory 5.19

 
 
Picture of John Lensmire
Re: MC II-A Number Theory 5.19
by John Lensmire - Monday, August 22, 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!