# Prove $a \mid m$ and $b \mid m \implies \frac{a \cdot b}{\text{gcd}(a, b)} \mid m$

I'm stuck at proving:

Let $a, b, c \in \mathbb{Z}, a\cdot b \neq 0$. Prove: $$a \mid m \hspace{15px}\text{and}\hspace{15px} b \mid m \implies \frac{a \cdot b}{\text{gcd}(a, b)} \mid m$$

My current attempt looks like this:

Let $t := \text{gcd}(a, b)$ donate the greatest common divisor of $a$ and $b$.

$$\implies\exists\, a', b': a = t\cdot a' \hspace{15px}\text{and}\hspace{15px} b = t \cdot b'$$

$$\implies \frac{a b}{\text{gcd}(a, b)} = \frac{a b}{t} = \frac{t a'b}{t} = a' b$$

I know that since b \mid m: $a'b \mid m$ iff $\text{gcd}(a', b) = 1$ and $a' \mid m$, but I'm not sure whether this is the right approach to this problem.

Currently I don't know about identities involving the least common multiple.

• "I know that..." this is false as written. – Andrés E. Caicedo Feb 3 '18 at 14:51
• – Dietrich Burde Feb 3 '18 at 14:58
• Also thus question, together with this question. – Dietrich Burde Feb 3 '18 at 14:59
• $m$ is a common multiple of $a$ and $b$. Also looks like the question expects you to know the fact that $\text{lcm}(a,b) = \frac{a\cdot b}{\gcd(a,b)}.$ Now lcm is the least of the common multiples. Hence lcm$(a,b)$ divides $m.$ – Bijesh K.S Feb 3 '18 at 15:01
• Please read what I actually wrote, and what you actually wrote. – Andrés E. Caicedo Feb 3 '18 at 15:13

By Bézout's lemma, there are integers $k$ and $l$ such that $\gcd(a,b)=ka+lb$. Therefore, $\gcd(a,b)m=kam+lbm$. Since $a\mid m$, $ab\mid lbm$ and since $b\mid m$, $ab\mid kam$. So, $ab\mid kam+lbm=\gcd(a,b)m$ and, since $\gcd(a,b)\mid ab$,$$ab\mid\gcd(a,b)m\iff\frac{ab}{\gcd(a,b)}\mid m.$$

• This is a really nice answer as well. Not involving the least common multiple! Thank you! – user7802048 Feb 3 '18 at 15:10
• @user7802048 I'm glad I could help. – José Carlos Santos Feb 3 '18 at 15:10

$a|m,b|m \implies \frac{ab}{gcd(a,b)}=lcm(a,b)|m$

and also the dual statement:

$m|a,m|b \impliedby m|\frac{ab}{lcm(a,b)}$

Intuition:

I) $Z=<\mathbb{Z}; \leq>$ is a poset which is a lattice. Now identify the two functions $sup,inf$ with the operations $\lor,\land$. So the algebra $Z^a=<\mathbb{Z}; \lor, \land>$ is a lattice.

II) Let the algebra $Z=<\mathbb{Z}; \lor, \land>$ be a lattice. Set $a \leq b$ if and only if $a \land b = a$. So $Z^p=<\mathbb{Z}; \leq>$ is a poset and as a poset and further more, a lattice.

III) $Z=<\mathbb{Z}; \leq>$ is a poset which is a lattice. So $(Z^{a})^p=Z$

IIII) $Z=<\mathbb{Z}; \lor, \land>$ is an algebra which is a lattice. So $(Z^{p})^a=Z$

You can freely use $|$ instead of $\leq$, $lcm,gcd$ instad of $\lor, \land$ and go back and forth back and forth.

I meant to link to the fundemental theorem of arithmetic... This is better.

Write $m=b\cdot c$. Now we have $a = a't\mid bc = b'tc$ so $a'\mid b'c$. Thus by Gauss lemma we have $a'\mid c$, and so $c=a'\cdot d$

Finally we have $$m = bc = ba'd = d\cdot {ba\over t}$$ and we are done.

• What does Gauß lemma say? $\text{gcd}(a, b) = 1, a \mid b \cdot c \implies a \mid c$? – user7802048 Feb 3 '18 at 14:40

Here's an approach:

Let $p$ be any prime number. Then $v_p(a)\le v_p(m)$, and $v_p(b)\le v_p(m)$. Let $d=\gcd(a,b)$, so $v_p(d)=\min\{v_p(a),v_p(b)\}$. Finally:

$$v_p\left(\frac{ab}{d}\right)=v_p(a)+v_p(b)-\min\{v_p(a),v_p(b)\}=\max\{v_p(a),v_p(b)\}\le v_p(m)$$

Since this is true for each prime, we have our result.

A related approach, that stays away from $p$-adic valuations:

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

and the expression on the right divides $\gcd(a,b)\cdot m$. Divide both sides by $\gcd(a,b)$, and voilà.