Online Course Discussion Forum
MCII-B Number Theory 5.16
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?
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.
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...
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.
Social networks