For natural numbers $a$ and $b$, show that $a \Bbb Z + b \Bbb Z = \gcd(a, b)\Bbb Z $ [duplicate]

For natural numbers $a$ and $b$, show that $a \Bbb Z + b \Bbb Z = \gcd(a, b)\Bbb Z $

I just basically said that the gcd of a and b { written as C } obviously divides aZ and bZ, therefore it can be rewritten as

CdZ + CeZ -> C[dZ + eZ] -> CZ[d+e] where Cd=a and Ce=b.

if a and b and C are natural numbers, then so are d and e. the sum of d and e is an integer, that when multiplied by an integer produces an integer. therefore

CZ[d+e] = CZ, so aZ + bZ = GCD(a,b)Z

{ Where C is the gcd(a,b) }

Solution 1:

You know that $a\Bbb Z+b\Bbb Z=\{ax+by:x,y\in\Bbb Z\}$. Let $d$ be the minimum positive integer in this set. By the Euclidean algorithm, we can write $a=qd+r$ and $b=q'd+r'$, with $r=0$ or $0<r<d$ and $r'=0$ or $0<r'<d$. We cannot have $0<r<d$ since else $r=a-qd$ is again in $a\Bbb Z+b\Bbb Z$ and is positive, which contradicts our choice of $d$ as the smallest positive integer in $a\Bbb Z+b\Bbb Z$. Thus $r=0$. By the same reasoning, $r'=0$. Thus $d\mid a,b$, so $d$ is a common divisor. But $d=ax'+by'$ for some integers $x',y'$, so if $f\mid a,b$ then $f\mid ax'+by'=d$. Thus $d$ is the greatest common divisor. Since $d\mid a,b$, it follows that $d\mid ax+by$ for any choice of $x,y$ integers, so every element in $a\Bbb Z+b\Bbb Z$ is a multiple of $d=(a,b)$, thus $a\Bbb Z+b\Bbb Z\subseteq(a,b)\Bbb Z$. But $a\Bbb Z+b\Bbb Z$ is closed under addition and subtraction, so all integer multiples of $(a,b)$ are in $a\Bbb Z+b\Bbb Z$, that is $a\Bbb Z+b\Bbb Z\supseteq (a,b)\Bbb Z$. Thus $a\Bbb Z+b\Bbb Z=(a,b)\Bbb Z$

Given any ideal $(x_1,\ldots,x_n)$ in $\Bbb Z$, there exists a least positive element in it, call it $d$. Dividing each $x_i$ by $d$ one gets $x_i=q_id+r_i$. Since $r_i=0$ or $r_i<d$, you get $r_i=0$ by $d$ being minimum. Thus $d\mid x_i$ for each $i$. This means $(d)\supseteq (x_1,\ldots,x_n)$. Since $(d)$ is trivially contained in $(x_1,\ldots,x_n)$, you get $(x_1,\ldots,x_n)=(d)$. It is not difficult to check that $d=\gcd(x_1,\ldots,x_n)$. We've already shown $d$ is a common divisor. But since $d=\sum a_ix_i$ for some integers $a_i$, any common divisor of the $x_i$ divides $d$. Thus $d$ is, being positive, the greatest common divisor of the $x_i$.