# 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!

• Since d is the largest of all the common divisors, any other common divisors will divide d. – Bhaskar Jul 11 '15 at 9:47

## 2 Answers

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

• Just to check if I understood your last argument: $d\geq$lcm($u$,$d$) $\Longrightarrow$ $0<$lcm($u$,$d$)$=m\cdot d\leq d$ so $m$ must be 1 and lcm($u$,$d$)=$d$ thus lcm($u$,$d$)$=k\cdot u=d$ for some integer $k$ – dorsh605 Jul 11 '15 at 10:27
• Yup, that's right (it follows that $m=1$). – Zev Chonoles Jul 11 '15 at 10:28
• thank you very much for your detailed explanation! – dorsh605 Jul 11 '15 at 10:29

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

• can you explain the direction of: a common divisor $u$ of $a$ and $b$ is smaller than $d$ $\Longrightarrow$ $u|d$ – dorsh605 Jul 11 '15 at 9:58
• @dorsh605, Zev posted an excellent explanation in his answer. – Zain Patel Jul 11 '15 at 10:00