Showing that these two definitions of $\gcd(a,b)$ are equivalent

Question

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 1

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$.

Answer 2

From the first definition, if every other common divisor divides $d$ then $d$ has to be the largest common divisor as specified in your second definition. So both definitions are saying that

1. $d > 0$
2. $d$ must divide both $a$ and $b$
3. $d$ must be the largest such number that does that. The third condition is written in two ways, the first way is that every other common divisor must divide $d$ as in the first definition and the second way is that $d$ is the largest such number as mentioned explicitly in the second definition.

---

To clarify:

(Any other common divisor divides $d$) $\equiv$ ($d$ is the largest common divisor.)