Online Course Discussion Forum

MC II-A Number Theory 5.16

 
 
Picture of Zeyin Wu
MC II-A Number Theory 5.16
by Zeyin Wu - Thursday, August 18, 2022, 1:19 AM
 

For this question I don't get why we need M bigger or equal to 5 and M=8=5+3. It looks confusing. Could you please offer some additional explanation? Thanks.

 
Picture of John Lensmire
Re: MC II-A Number Theory 5.16
by John Lensmire - Thursday, August 18, 2022, 10:02 AM
 

The basic idea is we want to test $N\geq 500$ until we get the smallest $N$ so that $N^2 \equiv 1 \pmod{9}$.

The key idea of modular arithmetic, however, is that we can always replace numbers by their remainders to make our life easier. Hence,

  • $500^2 \equiv 5^2 \equiv 7 \pmod{9}$
  • $501^2 \equiv 6^2 \equiv 0 \pmod{9}$
  • $502^2 \equiv 7^2 \equiv 4 \pmod{9}$
  • $503^2 \equiv 8^2 \equiv 1 \pmod{9}$

(Check these calculations yourself to make sure they make sense!)

Taking a step back, once we know that $500\equiv 5 \pmod{9}$, we can just work with the $5$, $6$, $7$, $8$ to find the square that is $1$ mod $9$. That's what the solution idea is talking about with the $M$ values.

Hope this helps!

Picture of Zeyin Wu
回复: Re: MC II-A Number Theory 5.16
by Zeyin Wu - Thursday, August 18, 2022, 5:36 PM
 

Think I got it, thank you Mr. Lensmire.