Let $a,b \in \mathbb{Z}$ and let $d = gcd(a,b)$. Show that $\{ ka + lb: k,l \in \mathbb{Z}\} = \{md : m \in \mathbb{Z} \}$

Question

I know that given $d = gcd(a,b)$ that this also means $xa + yb = d$. Using this we get (showing from left to right side) $$xa + yb = d$$ $$m(xa + yb) = md$$ $$xma + ymb = md$$ Now I am unsure how to conclude this properly. Because I do not think that showing that $gcd(ma, mb) = md$ is enough to conclude that for $\{ ka + lb: k,l \in \mathbb{Z}\} = \{md : m \in \mathbb{Z} \}$, since $k, l$ are arbitrarily. Conversely, showing from right side to left side we get $$md = m*gcd(a,b)$$ $$md = m* (xa + yb)$$ $$md = xma + ymb$$ Again, I do not believe that it is enough to conclude that $\{md : m \in \mathbb{Z} \} = \{ ka + lb: k,l \in \mathbb{Z}\}$

Answer 1

Notice that $d$ divide $a$ and $b$. Therefore $$d\mathbb Z\supset a\mathbb Z+b\mathbb Z.$$

Moreover, $d$ is the "smallest" integer (up to a unit) with such property. Therefore, the equality follow (because $\mathbb Z$ is a PID).

Answer 2

I'm not sure where your doubts are. Anyway, there's no need to invoke $\gcd(ma,mb)=md$.

The Bézout identity tells you that $d=xa+yb$, so $$ d\mathbb{Z}\subseteq a\mathbb{Z}+b\mathbb{Z} $$ (I use a less heavy notation). Now you need to prove the converse: since $a=md$ and $b=nd$ for some integers $m,n$, you can write $$ ka+lb=kmd+lnd=(km+ln)d\in d\mathbb{Z} $$ so the converse inclusion is proved.