Online Course Discussion Forum

MCII-B Number Theory 5.16

 
 
Picture of John Lensmire
Re: MCII-B Number Theory 5.16
by John Lensmire - Thursday, August 22, 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.