0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.