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$
  • $\begingroup$ What is your definition of lcm?? $\endgroup$ – Riju Jun 14 '17 at 10:02
4
$\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$
2
$\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.

That innate structure of the set of common multiples will be clarified when one studies ideal theory in abstract algebra, viz. the set of common multiples is a prototypical example of an ideal, and the above proof is a special case that ideals are principal in domains enjoying (Euclidean) Division with Remainder, i.e. Euclidean domains are PIDs. The proof is exactly the same as above, by Euclidean descent using the division algorithm.

$\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$ 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).\,$ $\endgroup$ – Bill Dubuque Apr 15 at 14:29
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.