- Thread starter
- #1

- Apr 14, 2013

- 4,106

The greatest common divisor of $a$ and $b$ can be written as a linear combination of $a$ and $b$.

Let the set $D=\{xa+yb|x,y \in Z\}$.

**a)**$D$ contains non-zero elements.

**b)**$D$ contains also positive numbers.

**c)**The set of positive numbers of $D$ (let $D^+$) is $ \neq \varnothing$, so it has a minimum element. Let $d$ be the minimum element of $D^+ \subset D$

Consider that $d$ is the GCD of $a$,$b$.

First of all, since $d \in D$, $\exists x_1, y_1 \in Z$ so that $d=x_1 a+ y_1 b$

Consider that each element of $D$ is a multiple of $d$ and each multiple of $d$ belongs to $D$, so let's consider that $\{ax+by|x,y \in Z\}=D=dZ$

I haven't understood why we consider at

**c)**that $d$ is the GCD of $a$,$b$. Could you explain it to me??