Online Course Discussion Forum

MCII-B Number Theory 5.16

 
 
ZhangDaniel的头像
MCII-B Number Theory 5.16
ZhangDaniel - 2024年08月20日 Tuesday 18:08
 

I did guess and check for 5.15 and got the right answer, but I don't think that's how you're supposed to solve it, right? How would I ACTUALLY solve 5.15 and 5.16?

 
LensmireJohn的头像
Re: MCII-B Number Theory 5.16
LensmireJohn - 2024年08月21日 Wednesday 08:40
 

Depending on your point of view there is a little guessing and checking involved. However, this should be with N, not with N^2.

For example, in 5.15, for $N^2\equiv 1\pmod{3}$, we can check 0, 1, and 2 mod 3 to see that only 1 and 2 work. Hence, in 5.15 we want to look for the smallest $N\geq 500$ such that $N$ is either 1 or 2 mod 3.

For 5.16 we can do something similar. Start by asking the question, if $N^2 \equiv 1 \pmod{9}$, what is $N \pmod{9}$? Note the worst case here is we check 0, 1, 2, .up to 8, to see which ones work. Then once this question is answered we proceed similarly to 5.15.

ZhangDaniel的头像
Re: MCII-B Number Theory 5.16
ZhangDaniel - 2024年08月21日 Wednesday 19:49
 
Ohh, I see. Thank you so much!! 


I have another question: for 5.22, how would I solve it? I know that it's going to be a similar strategy to Example 5.2, but I'm sort of stuck...

LensmireJohn的头像
Re: MCII-B Number Theory 5.16
LensmireJohn - 2024年08月22日 Thursday 10:17
 

You're correct that 5.22 is similar to 5.2. I also wouldn't stress too much about this proof, but the idea is important.

For proofs like this, basically things just "work" once you write out what you know. However, it is sometimes tricky to write what you know in the right way for the proof to work. For this problem:

  • We know $a\equiv b \pmod{m}$ or in other words, $m | (a-b)$. Note we also know that $d | (a-b)$. Thus, if it helps, we can write $(a-b) = m\cdot k$ for an integer $k$, etc.
  • Our goal is to show that $a/d \equiv b/d \pmod{ m / \text{gcd}(d,m)}$, or in other words we want to show that $a/d - b/d$ is divisible by $m / \text{gcd}(d,m)$.
  • Last hint: How to think about gcd(d,m)? This means that if e = gcd(d,m), then we can write d = e*f for some integer f, with f relatively prime to m. Breaking it down this way will help us prove the result.