Online Course Discussion Forum

MCII-B Number Theory 5.16

 
 
Picture of Daniel Zhang
MCII-B Number Theory 5.16
by Daniel Zhang - Tuesday, 20 August 2024, 6:08 PM
 

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?

 
Picture of John Lensmire
Re: MCII-B Number Theory 5.16
by John Lensmire - Wednesday, 21 August 2024, 8:40 AM
 

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.

Picture of Daniel Zhang
Re: MCII-B Number Theory 5.16
by Daniel Zhang - Wednesday, 21 August 2024, 7:49 PM
 
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...

Picture of John Lensmire
Re: MCII-B Number Theory 5.16
by John Lensmire - Thursday, 22 August 2024, 10:17 AM
 

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.