Show that $\exists a, b$ where $\gcd(a,b) = d$ and $\operatorname{lcm}(a,b) = e$ iff $d \mid e$

69 Views Asked by At

I want to show, given the natural numbers $d$ and $e$:

$$\exists a, b \in \mathbb{N}$$ such that $$ \gcd(a, b) = d$$ and $$\operatorname{lcm}(a, b) = e$$ if and only if $$d \mid e$$

I think I have managed to show it one way, but not the other.

If $a$ and $b$ are defined as above I know that

$$\gcd(a,b) \cdot \operatorname{lcm}(a,b) = de = ab$$

and that $d$ divides both $a$ and $b$. So for some natural numbers $q$ and $s$:

$de = ab = ds\cdot dq \Leftrightarrow e = dsq \Rightarrow d \mid e$

I'm sorry if that was messy to read. Anyway, I wonder if what I did was ok so far, if there is a better way, and also I wonder how to show that $d \mid e$ implies $a$ and $b$ exists. Hints are good but if you wanna write the full answer that's also fine. Thanks! (Also if someone wants to edit my post to improve my notation I'll be happy to see it thanks)

2

There are 2 best solutions below

1
On BEST ANSWER

For the other direction, if $d\vert e$, simply take $a:=d$ and $b:=e$, their gcd is $d$ and lcm is $e$ then.

0
On

You can divide everybody by $d$, then your problem is to find $$x, y \in \mathbb{N}$$ such that $$ \gcd(x, y) = 1$$ and $$lcm(x, y) = e/d$$ and the solutions of your problem are parametrized as $(a,b)=(xd,yd)$. For existence, as you can always write $e/d=1*e/d$ you always have the solution $(x,y)=(1,e/d)$ and then $(a,b)=(d,e)$.