3
$\begingroup$

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!

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

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – dorsh605 Jul 11 '15 at 10:27
  • $\begingroup$ Yup, that's right (it follows that $m=1$). $\endgroup$ – Zev Chonoles Jul 11 '15 at 10:28
  • $\begingroup$ thank you very much for your detailed explanation! $\endgroup$ – dorsh605 Jul 11 '15 at 10:29
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.