Proving gcd($a,b$)lcm($a,b$) = $|ab|$

Question

Let $a$ and $b$ be two integers. Prove that $$ dm = \left|ab\right| ,$$ where $d = \gcd\left(a,b\right)$ and $m = \operatorname{lcm}\left(a,b\right)$.

So I went about by saying that $a = p_1p_2...p_n$ where each $p_n$ is a prime. Same applies to $b = q_1q_2 ... q_c$. So then $m = (u_1u_2...)(p_1p_2...p_n)$ and $m = (t_1t_2...)(q_1q_2...q_c)$ since $a|m$ and $b|m$. $m$ has a unique factorization, so the primes $(u_1u_2...)(p_1p_2...p_n) = (t_1t_2...)(q_1q_2...q_n)$ and the gcd(a,b) = $(p_1p_2...p_n) \cap (q_1q_2...q_n)$ (I know this is not mathematically correct, so is there a correct way to express this?).

So $dm = |ab| \iff d= \frac{|ab|}{m}$. And by the definition above, $\frac{ab}{(t_1t_2...)b} = \frac{a}{(t_1t_2...)}$. And this is where I get stuck. Is my proof right? Am I going in the right direction?

Thanks

PS. I am trying to do this using only the prime factorization theorem and the definitions of the gcd and the lcm.

Answer 1

WLOG $a$ and $b$ are positive integers (as the remaining cases are easily reduced to this one).

Let $d = \gcd(a,b)$ and $l=\operatorname{lcm}(a,b)$. Notice that $\frac{ab}{d}$ is a common multiple of $a$ and $b$, since $\frac{a}{d}$ and $\frac{b}{d}$ are integers, by definition. By Euclidean algorithm, $\frac{a}{d}$, $\frac{b}{d}$ are relatively prime. Now assume $n$ is a common multiple of $a$ and $b$; then we can find integers $k$ and $k'$ such that $n=ka$ and $n=k'b$, so $ka=k'b$. We divide both sides by $d$ (we remain in integers!) to get $k'\frac{b}{d}=k\frac{a}{d}$. Hence $\frac{a}{d}$ divides $\frac{b}{d} k'$ and since $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime then $\frac{a}{d}$ divides $k'$. Hence $n=k'b=q\frac{ab}{d}$ for some integer $q$. So $\frac{ab}{d} $ divides $n$. Hence $\operatorname{lcm}(a,b) = \frac{ab}{d} = \frac{ab}{\gcd(a,b)}$.

Answer 2

The main hint is $\max\{x_i,y_i\} + \min\{x_i,y_i\} = x_i + y_i$.

Hence, if $a=\prod_{i=1}^np_i^{x_i}$ and $b=\prod_{i=1}^np_i^{y_i}$, where $x_i,y_i \in \mathbb{Z}^+ \cup \{0\}$, then $$\gcd(a,b) = \prod_{i=1}^np_i^{\min\{x_i,y_i\}} \text{ and }\text{lcm}(a,b) = \prod_{i=1}^np_i^{\max\{x_i,y_i\}}$$

Answer 3

If $a=b=0$, then any integer is a common divisor of $a$ and $b$.
So, there is no greatest common divisor of $a$ and $b$.
So we don't consider the case in which $a=b=0$.

If $a=0$ and $b\neq 0$, then the set of the common divisors of $a$ and $b$ is equal to the set of divisors of $b$.
Obviously, the greatest divisor of $b$ is $|b|$.
So, $\gcd(a,b)=|b|$.
If $a=0$ and $b\neq 0$, the only common multiple of $a$ and $b$ is $0$ since the only multiple of $a$ is $0$ and $0$ is a multiple of $b$.
So, $\operatorname{lcm}(a,b)=0$.
Therefore, if $a=0$ and $b\neq 0$, then $\gcd(a, b)\cdot\operatorname{lcm}(a,b)=|b|\cdot 0=|a\cdot b|$.

If $a\neq 0$ and $b=0$, then by symmetry, $\gcd(a, b)\cdot\operatorname{lcm}(a,b)=|a|\cdot 0=|a\cdot b|$.

Let $a>0$ and $b>0$.
Obviously, $a\cdot b$ is a positive common multiple of $a$ and $b$.
So, the least common multiple of $a$ and $b$ exists, and it's positive.
Let $M$ be any common multiple of $a$ and $b$.
Let $M=q\cdot\operatorname{lcm}(a,b)+r,\,\, 0\leq r<\operatorname{lcm}(a,b)$.
Then, obviously, $r=M-q\cdot\operatorname{lcm}(a,b)$ is a common multiple of $a$ and $b$.
If $0<r<\operatorname{lcm}(a,b)$, then $r$ is smaller than $\operatorname{lcm}(a,b)$.
This is a contradiction.
So, $r=0$.
So, $M=q\cdot\operatorname{lcm}(a,b)$.
So, any common multiple of $a$ and $b$ is a multiple of $\operatorname{lcm}(a,b)$.
Since $a\cdot b$ is a positive common multiple of $a$ and $b$, so we can write $a\cdot b=D\cdot \operatorname{lcm}(a,b)$ for some positive integer $D$.
Let $\operatorname{lcm}(a,b)=a\cdot a^{'}$ and $\operatorname{lcm}(a,b)=b\cdot b^{'}$.
Then, $a\cdot b=D\cdot\operatorname{lcm}(a,b)=D\cdot a\cdot a^{'}=D\cdot b\cdot b^{'}$.
So, $b=D\cdot a^{'}$ and $a=D\cdot b^{'}$.
So, $D$ is a common divisor of $a$ and $b$.
Assume that there exists a common divisor $D^{'}$ of $a$ and $b$ which is larger than $D$.
Then, $M^{'}:=a\cdot\frac{b}{D^{'}}=\frac{a}{D^{'}}\cdot b$ is a positive common multiple of $a$ and $b$.
Then, $0<M^{'}=a\cdot\frac{b}{D^{'}}=\frac{a}{D^{'}}\cdot b<\frac{a\cdot b}{D}=\operatorname{lcm}(a,b)$.
This is a contradiction.
So, $D$ is the greatest common divisor of $a$ and $b$.
So, $\gcd(a, b)\cdot\operatorname{lcm}(a,b)=a\cdot b=|a\cdot b|$.

If $a>0$ and $b<0$, then $\gcd(a, -b)\cdot\operatorname{lcm}(a,-b)=|a\cdot(-b)|=|a\cdot b|$.
Obviously, the set of the common divisors of $a$ and $b$ is equal to the set of the common divisors of $a$ and $-b$.
So, $\gcd(a,b)=\gcd(a,-b)$.
Obviously, the set of the common multiples of $a$ and $b$ is equal to the set of the common multiples of $a$ and $-b$.
So, $\operatorname{lcm}(a,b)=\operatorname{lcm}(a,-b)$.
So, $\gcd(a, b)\cdot\operatorname{lcm}(a,b)=|a\cdot b|$.

If $a<0$ and $b>0$, then, by symmetry, $\gcd(a, b)\cdot\operatorname{lcm}(a,b)=|a\cdot b|$.

If $a<0$ and $b<0$, then $\gcd(-a, -b)\cdot\operatorname{lcm}(-a,-b)=|(-a)\cdot(-b)|=|a\cdot b|$.
Obviously, the set of the common divisors of $a$ and $b$ is equal to the set of the common divisors of $-a$ and $-b$.
So, $\gcd(a,b)=\gcd(-a,-b)$.
Obviously, the set of the common multiples of $a$ and $b$ is equal to the set of the common multiples of $-a$ and $-b$.
So, $\operatorname{lcm}(a,b)=\operatorname{lcm}(-a,-b)$.
So, $\gcd(a, b)\cdot\operatorname{lcm}(a,b)=|a\cdot b|$.