Suppose that $a$ is not coprime to $b$. Show that there exists $d\in\mathbb{N}$ such that $a\mid d$ and $b\mid d$, but $ab\not\mid d$.

Question

Let $a,b\in\mathbb{N}$. Suppose that $a$ is not coprime to $b$. Show that there exists $d\in\mathbb{N}$ such that $a\mid d$ and $b\mid d$, but $ab\not\mid d$.

I imagine that Bezout’s Lemma will come into play somewhere, but I can’t see where.

Answer 1

Sketch:

Let $\gcd(a,b)=c>1$. Then we have $a=cA$ and $b=cB$ with $\gcd(A,B)=1$. Then let $d=cAB$.

Answer 2

If $a|d$ and $b|d$ then $d$ must but a common multiple of $a$ and $b$. So $\operatorname{lcm}(a,b)$ must divide $d$.

So just let $d = \operatorname{lcm}(a,b)$.

That is to say:

========

If $a,b$ are not co-prime then there exist an $h\ne 1$ that is the $\gcd(a,b)$.

And as $h|a$ and $h|b$ we can have $d = \frac ah*b = \frac bh*a$.

So $d = a*\frac bh$ and $\frac bh$ is an integer so $a|d$. And $d = b\frac ah$ and $\frac ah$ is an integer so $b|d$.

But $ab = \frac ahb*h = \frac bha*h = d*h > d*1 = d$.

So $ab\not \mid d$.

That's all.