1
$\begingroup$

Is $$d_1\mid n,d_2\mid n\iff [d_1,d_2]\mid n$$ true ? And if yes, how can I prove it ? I recall that $[d_1,d_2]$ is the least common multiple.

My tries

For the implication : Let $d_1\mid n$ and $d_2\mid n$. Then, $d_1d_2\mid n^2$. By the way, since $d_1,d_2\mid n$, we have that $(d_1,d_2)\mid n$ where $(d_1,d_2)=:\gcd(d_1,d_2)$ and thus $$[d_1,d_2](d_1,d_2)\mid n^2.$$

Question: How can I get $[d_1,d_2]\mid n$ from this?

For the converse, since $d_1,d_2\mid [d_1,d_2]\mid n$, the claim follow.

$\endgroup$
  • 2
    $\begingroup$ What is your definition of lcm?? $\endgroup$ – Riju Jun 14 '17 at 10:02
5
$\begingroup$

Let $a$ and $b$ be integers such that $ad_1=bd_2=n$. By Bézout's theorem, there are integers $\alpha$ and $\beta$ such that $\alpha d_1+\beta d_2=(d_1,d_2)$. Therefore,$$(d_1,d_2)n=\alpha d_1n+\beta d_2n=\alpha d_1bd_2+\beta d_2ad_1=d_1d_2(\alpha b+\beta a).$$But this is the same thing as saying that $\frac{d_1d_2}{(d_1,d_2)}(\alpha b+\beta a)=n$. Since $\frac{d_1d_2}{(d_1,d_2)}=[d_1,d_2]$, this number divides $n$.

$\endgroup$
3
$\begingroup$

Theorem $\,\ a,b\mid m\iff {\rm lcm}(a,b)\mid m\quad$ [Universal Property of LCM]

Proof $\,\ $ $(\Leftarrow)\,$ Notice $\,{\rm lcm}(a,b)\,$ is a common multiple of $\,a,b\,$ by definition, therefore $$\ a,b\mid {\rm lcm}(a,b)\mid m\,\Rightarrow\, a,b\mid m\quad\text{by}\, {\it transitivity}\text{ of divisibility}$$

$(\Rightarrow)\ \ $ This has a natural conceptual proof by Euclidean descent as follows.

The set $M$ of all positive common multiples of all $\,a,b\,$ is closed under positive subtraction, i.e. $\,m> n\in M$ $\Rightarrow$ $\,a,b\mid m,n\,\Rightarrow\, a,b\mid m\!-\!n\,\Rightarrow\,m\!-\!n\in M.\,$ Thus $\,M\,$ is also closed under mod, i.e. remainder, by $\ m\ {\rm mod}\ n\, =\, m-qn = ((m-n)-n)-\cdots-n\,$ (= repeated subtraction). Thus the least $\,\ell\in M\,$ divides every $\,m\in M,\,$ else $\ 0\ne m\ {\rm mod}\ \ell\in M\,$ and is smaller than $\,\ell.\,$ Note that $\,M\,$ is nonempty since $\,|ab|\in M$.

Remark $ $ The above means lcm is a divisibility-least common multiple, i.e. it is least in the divisibility order $\, a\prec b\!\! \overset{\rm def}\iff\! a\mid b.\ $ This is the (universal) definition of lcm used in general rings (which may lack any other way to measure "least"). See here for more on the general viewpoint.

Note that the proof used only that $M$ is a nonempty set of integers closed under subtraction, so it holds more generally for any such set of integers, i.e. every element is a multiple of the least positive element (if $M\neq \{0\}$).

That innate structure of the set of common multiples will be clarified when one studies ideal theory in abstract algebra, viz. a set of common multiples is a prototypical example of an ideal, and the above proof is a special case of: ideals in Euclidean domains (those enjoying Division with smaller Remainder) are necessarily principal - being the set of all multiplies of any "least" element, i.e. Euclidean domains are PIDs. The proof is exactly the same as above by Euclidean descent using the division algorithm, i.e. directly using remainder as the descent step (which in more general rings cannot be obtained by repeated subtraction as in $\Bbb Z$).

$\endgroup$
0
$\begingroup$

I think that the definition of LCM is as follows: m is said to be the lcm of $d_{1}$ and $d_{2}$ if

(1) $d_{1} |n, d_{2} |n$

(2) if $d_{1}|n$ and $d_{2}|n \implies m|n$

So, one side of the implication is just definition. And the reverse inclusion is also trivial. because $d_{1}|[d_{1} d_{2}]$ and so does $d_{2}$

$\endgroup$
  • $\begingroup$ Said equivalently: $\,m\,$ is an lcm of $\,d_1,d_2\,$ if $\ d_1,d_2\mid n\iff m\mid n.\,$ That is the definition of lcm used in general domains, where we may have no notion of size so we measure "least" in terms of the divisibility partial order. However, that's not the definition used in most elementary number theory textbooks. Rather, it is usually defined as the least common multiple (in $\Bbb N)$, and we have to prove that the two definitions are equivalent, e.g. as in my answer. $\endgroup$ – Bill Dubuque Sep 30 '20 at 18:32
0
$\begingroup$

Hint

If $n=p_1^{k_1}\cdot ...\cdot p_n^{k_n}$, then any divisor is of the form $$p_1^{\ell_1}\cdot ...\cdot p_n^{\ell_n},$$ with $0\leq \ell_i\leq k_i$. Ans if $d_1,d_2$ are two divisors, i.e.

$$d_1=p_1^{\ell_1^1}\cdot ...\cdot p_n^{\ell_n^1}\quad \text{and}\quad d_2=p_1^{\ell_1^2}\cdot ...\cdot p_n^{\ell_n^2} $$ then $$[d_1,d_2]=p_1^{\ell_1^1\wedge \ell_1^2}\cdot ...\cdot p_n^{\ell_n^1\wedge \ell_n^2},$$ where $a\wedge b$ mean the minimum of $a$ and $b$.

With this, the claim almost follow.

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