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

We assume $a$ and $b$ to be positive (the remaining cases are easily reduced to this).

Apply prime factorization/decomposition of $a$ and $b$:

$$ a = p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_s^{\alpha_s}, \qquad \alpha_j\ge 0 \quad (j=1,2,\ldots,s); $$$$ b = p_1^{\beta_1} p_2^{\beta_2}\cdots p_s^{\beta_s}, \qquad \beta_j\ge 0 \quad (j=1,2,\ldots,s). $$ ($p_j$ are prime factors of $a$ and/or $b$. That's why zero-powers are allowed here).

Then $$ GCD(a,b) = p_1^{\min\{\alpha_1,\beta_1\}}p_2^{\min\{\alpha_2,\beta_2\}}\cdots p_s^{\min\{\alpha_s,\beta_s\}}, $$ $$ LCM(a,b) = p_1^{\max\{\alpha_1,\beta_1\}}p_2^{\max\{\alpha_2,\beta_2\}}\cdots p_s^{\max\{\alpha_s,\beta_s\}}, $$ hence $$ GCD(a,b)\cdot LCM(a,b) = p_1^{\max\{\alpha_1,\beta_1\}+\min\{\alpha_1,\beta_1\}} p_2^{\max\{\alpha_2,\beta_2\}+\min\{\alpha_2,\beta_2\}} \cdots p_s^{\max\{\alpha_s,\beta_s\}+\min\{\alpha_s,\beta_s\}}; $$

but $$ \max\{\alpha,\beta\}+\min\{\alpha,\beta\} = \alpha+\beta. $$

So, $$ GCD(a,b)\cdot LCM(a,b) = p_1^{\alpha_1+\beta_1} p_2^{\alpha_2+\beta_2} \cdots p_s^{\alpha_s+\beta_s} = \ldots . $$

Answer 3

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 4

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

Answer 5

I have tryed to re think this question from the beginning and this is what I get. I hope that it is correct.

1-
$GCD(a;b)=d \Rightarrow a=dx, b=dy$ with $x,y,d \in \mathbb{N}$ and $GCD(x;y)=1$
More over we can writte$\frac{ab}{d}=ay=bx$ so it cames that the integer $ay=bx$ is a commom multiple of $a$ and $b$ by definition.

2-
Now let note $m=LCM(a;b) \Rightarrow \exists k,l \in \mathbb{N} $ s.t. $ m = ak = bl \Rightarrow \frac{m}{d}=\frac{xdk}{d}=\frac{ydl}{d}=xk=yl \in \mathbb{N}$

3-
Reminder: Gauss lemma: If $a,b,c$ are three integers such that $a$ and $b$ are coprime and $a$ divides $bc$ then $a$ divises $c$.
We take $x,y$ two coprime integers and $l$. As we wrotte above $xk=yl \Rightarrow \frac{yl}{x}=k \in \mathbb{N}$ so $x$ divides $yl=\frac{m}{d}$. Hence by the Gauss lemma we get that $x$ divides $l$. Equivalently we get by the same justification that $y$ divides $k$.
So we can writte: $m=bl=dyl=dyxl'$ with $l=xl'$ and on the other side $m=ak=dxk=dxyk'$ with $k=xk'$

4-
From "-3" we got that $dyxl'= m = dxyk'\Rightarrow l'=k'$. But $m$ is by def the smallest commom multiplier so $l'=1=k'$ and we get that $LCM(a;b)=dxy$.
Rem: Indeed $dxy$ is all ready by def a commom multiplier of $a$ and $b$ because $dxy$ is all ready a multiple of $a$ and $b$ as it is divisible by them!

5-
So: $GCD(a;b)LCM(a;b)=ddxy=d^2xy$ while $ab=dxdy=d^2xy$
Q.E.D.