elementary number theory - Showing that these two definitions of $gcd(a,b)$ are equivalent

So far I have encountered with two definitions of the GCD of $a$ and $b$.

The first definition is:

$\gcd(a,b)$ is an integer that has the following properties:

1. $d>0$




2. $d\mid a$ and $d\mid b$




3. any common divisor $u$ of $a$ and $b$ also divides $d$

The second definition I saw is:

The greatest common divisor of two integers $a$ and $b$ (not both zero) is the largest integer which
divides both of them.

Can someone please show me the equivalence of these two definitions without using any theorems. thanks!

Answer

For clarity, let's record these lemmas:

By definition, $x\mid y\iff y=kx$ for some integer $k$.

• If $y>0$, then it is impossible to have $0\mid y$.


• If $y>0$ and $x<0$ then certainly $y\geq x$.


• If $y>0$ and $x>0$, then we must have $k>0$, hence $k\geq 1$ (because there are no integers between $0$ and $1$), so that $y=kx \geq x$.

Thus, if $x$ and $y$ are integers such that $x\mid y$ and $y>0$, then $y\geq x$.

---

Suppose that $x\mid z$ and $y\mid z$. Then by definition $z$ is a common multiple of $x$ and $y$, hence $|z|$ is a common multiple of $x$ and $y$, so that in fact the integers
$$|z|,\qquad |z|-\mathrm{lcm}(x,y),\qquad |z|-2\mathrm{lcm}(x,y),\qquad \ldots$$
are all common multiples of $x$ and $y$. On this strictly decreasing list of integers, starting with the positive integer $|z|$, there must be a smallest positive entry; that entry can't be smaller than $\mathrm{lcm}(x,y)$ because that would contradict the definition of $\mathrm{lcm}$, and it can't be larger than $\mathrm{lcm}(x,y)$ because then $\mathrm{lcm}(x,y)$ would be a positive entry on the list smaller than it. Therefore $|z|-k\mathrm{lcm}(x,y)=\mathrm{lcm}(x,y)$ for some integer $k$, i.e. $z=\pm(k+1)\mathrm{lcm}(x,y)$ for some integer $k$.

Thus, we have shown that if $x\mid z$ and $y\mid z$, then $\mathrm{lcm}(x,y)\mid z$.

Now, let $a$ and $b$ be integers, and let $d$ be an integer such that $d\mid a$ and $d\mid b$.

Suppose that $d>0$ and that $d$ satisfies $u\mid d$ for any other integer $u$ with $u\mid a$ and $u\mid b$. Then by our first lemma, $d$ satisfies $d\geq u$ for any integer $u$ with $u\mid a$ and $u\mid b$.

Conversely, suppose that $d$ satisfies $d\geq u$ for any integer $u$ with $u\mid a$ and $u\mid b$. Then in particular $d\geq -d$ which means that $d>0$. If $u$ is any integer with $u\mid a$ and $u\mid b$, then each of $a$ and $b$ are a common multiple of $u$ and $d$, so that $\mathrm{lcm}(u,d)\mid a$ and $\mathrm{lcm}(u,d)\mid b$ by our second lemma. Therefore, by our assumption about $d$, we have that $d\geq \mathrm{lcm}(u,d)$ for any $u$ with $u\mid a$ and $u\mid b$, which implies that $u\mid d$ for any $u$ with $u\mid a$ and $u\mid b$.