# 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. Jul 11, 2015 at 9:47

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$ Jul 11, 2015 at 10:27
• Yup, that's right (it follows that $m=1$). Jul 11, 2015 at 10:28
• thank you very much for your detailed explanation! Jul 11, 2015 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$ Jul 11, 2015 at 9:58
• @dorsh605, Zev posted an excellent explanation in his answer. Jul 11, 2015 at 10:00