# Let $H$ be a group. Let $a, b$ be fixed positive integers and $H=\{ax+by\mid x,y\in \Bbb Z\}.$ Show that $d\mathbb Z =H$ where $d=\gcd(a,b)$.

Let $H$ be a group. Let $a, b$ be fixed positive integers and $$H=\{ax+by\mid x,y\in \Bbb Z\}.$$ Show that $d\mathbb Z =H$ where $d=\gcd(a,b)$.

Given $d=\gcd(a,b)$ then $d|a, ~d|b$ i.e. $d\alpha =a, ~d\beta =b$ for some integers $\alpha, \beta$.

Let $ax+by\in H$ then $ax+by=d(x\alpha + y\beta)\in d\Bbb Z$ i.e. $$H\subset d\Bbb Z ~~~~~~~~~~~~~(1)$$

We now show that $d \Bbb Z \subset H$.

By Euclidean algorithm, there exist $u, v$ such that $ua+vb=\gcd(a,b)=d$.

My Question

I would like to show that $$d\mathbb Z =H.$$ I have shown $$H\subset d\Bbb Z$$ and I am unable to show $$d \Bbb Z \subset H.$$ Please help me to show the desired part ($d \Bbb Z \subset H$).

• As you pointed out, $d$ is a linear combination of $a$ and $b$ and so any multiple of $d$ is a linear combination of $a$ and $b.$ – CIJ Sep 26 '15 at 4:56

By Euclidian algorithm, there exist $u, v$ such that $ua+vb=\gcd(a,b)=d$
so you're done since given $dz\in d\mathbb Z$,
$$dz=z(ua+vb)=a(zu)+b(zv)$$
which is a linear combination of $a$ and $b$, thus $dz\in H$. This proves $d \Bbb Z \subset H$.