Problem 1 (#3.5.32).
Show that if $a, b$, and $m$ are integers such that $m \geq 2$ and
$a \equiv b \pmod {m}$, then $\gcd(a, m) = gcd(b, m)$.
Proof.
Let $d = \gcd(a, m)$
Then $d \mid a$ and $d \mid m$
,
so for some $k,l \in \mathbb{Z}$, $a = kd$ and $m = ld$
Since $a \equiv b \pmod {m}$, for some $r \in \mathbb{Z}$, $a − b = rm$.
Substituting in, $kd − b = rld$, so $b = d(k − rl)$.
Thus $d \mid b$. Since the gcd of $a$ and $m$ divides $b$, it’s a common divisor of $b$ and $m$, so $\gcd(a, m) \leq \gcd(b, m)$.
By an analogous argument, the greatest common divisor of $b$ and $m$ is a common divisor of $a$ and $m$, so $\gcd(a, m) \geq gcd(b, m)$. Thus $\gcd(a, m) = gcd(b, m)$ as desired.
Can someone explain this proof to me? I was okay with it until the "substituting in, $kd -b$… " step. How did they get rid of the mod operator between those steps? The next steps might click after that one, but an explanation on them would be much appreciated (just in case!).
Edit: Thank you so much!!
Best Answer
$$a \equiv b \pmod{m} \iff m \mid a-b$$
and $m \mid a-b \implies \color{red}{mr = a-b}$ for some integer $r$
Now since we already know that $dk=a,dl=m$
Now we substitute $dk$ for $a$ and $dl$ for $m$ in the above $\color{red}{red \space equation}$ to get $$dlr = dk -b$$ now we add $b$ to both sides of the equation and subtract $dlr$ from both sides to get $$\color{blue}{b = d(k -lr)}$$ and so $d \mid b$ because $k-lr$ is an integer
Now you already know that $\gcd(a,m)=d$ and we already showed that $d \mid b$ and so $d$ is a common divisor of $b$ and $m$.
so the $$\gcd(b,m) \geq d = \gcd(a,m)$$
Now to prove equality you need to show that $\gcd(b,m) \leq d$
$\textbf{Here is how} $
Let $g =\gcd(b,m)$ then $g \mid b$ and $g \mid m$ and so there exists integers $s,t$ such that $gs = b$ and $gt = m$
Now since we are given that $$a \equiv b \pmod{m}$$ then we know $m \mid a-b$ and so there exists integer $q$ such that $$ \color{brown}{mq = a-b}$$
now we substitute $m=gt,b=gs$ in the above $\color{brown}{brown \space equation}$ to get $$gtq = a-gs$$
Now we add $gs$ to both sides of the equation and subtract to get $$gtq +gs = a$$ and so $$g(tq + s) = a$$
Hence $g \mid a$ because $tq + s$ is an integer.
Now this means that $g$ is a common divisor of $a$ and $m$ and hence $$\gcd(a,m) \geq gcd(b,m)$$
Now since we showed that $$\gcd(a,m) \geq \gcd(b,m)$$ and $$\gcd(a,m) \leq \gcd(b,m)$$ then this implies that $$\color{green}{\gcd(a,m) = \gcd(b,m)}$$