Online Course Discussion Forum

MC II-A Number Theory 5.16

 
 
WuZeyin的头像
MC II-A Number Theory 5.16
WuZeyin - 2022年08月18日 Thursday 01:19
 

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.

 
LensmireJohn的头像
Re: MC II-A Number Theory 5.16
LensmireJohn - 2022年08月18日 Thursday 10:02
 

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!

WuZeyin的头像
回复: Re: MC II-A Number Theory 5.16
WuZeyin - 2022年08月18日 Thursday 17:36
 

Think I got it, thank you Mr. Lensmire.