Namespaces
Variants
Actions

Difference between revisions of "Least common multiple"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (→‎Comments: link)
(Tex done)
 
Line 1: Line 1:
The smallest positive number among the common [[multiple]]s of a finite set of integers or, in particular, of natural numbers, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l0577501.png" />. The least common multiple of the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l0577502.png" /> exists if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l0577503.png" />. It is usually denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l0577504.png" />.
+
The smallest positive number among the common [[multiple]]s of a finite set of integers or, in particular, of [[natural number]]s, $a_1,\ldots,a_n$. The least common multiple of the numbers $a_1,\ldots,a_n$ exists if $a_1 \cdots a_n \neq 0$. It is usually denoted by $[a_1,\ldots,a_n]$.
  
 
Properties of the least common multiple are:
 
Properties of the least common multiple are:
  
1) the least common multiple of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l0577505.png" /> is a divisor of any other common multiple;
+
1) the least common multiple of $a_1,\ldots,a_n$ is a divisor of any other common multiple;
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l0577506.png" />;
+
2) $[a_1,\ldots,a_{n+1}] = [[a_1,\ldots,a_n],a_{n+1}]$;
  
3) if the integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l0577507.png" /> are expressed as
+
3) if the integers $a_1,\ldots,a_n$ are expressed as
 +
$$
 +
a_i = p_1^{e_{i1}} \cdots p_k^{e_{ik}}
 +
$$
 +
where $p_1,\ldots,p_k$ are distinct primes, $e_{ij} \ge 0$, $i=1,\ldots,n$, $j=1,\ldots,k$, and $f_j = \max\{e_{1j},\ldots,e_{nj} \}$, $j=1,\ldots,k$, then
 +
$$
 +
[a_1,\ldots,a_n] = p_1^{f_1} \cdots p_k^{f_k} \ ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l0577508.png" /></td> </tr></table>
+
4) if $ab > 0$, then $ab = [a,b](a,b)$, where $(a,b)$ is the [[greatest common divisor]] of $a,b$.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l0577509.png" /> are distinct primes, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775011.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775013.png" />, then
+
Thanks to the last property, the least common multiple of two numbers (and so by (2), of any finite set) can be found with the aid of the [[Euclidean algorithm]].  
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775014.png" /></td> </tr></table>
+
The concept of the least common multiple can be defined for elements of an [[integral domain]], and also for ideals of a commutative ring.  In a [[unique factorization domain]] least common multiples exist and are unique (up to units).
 
 
4) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775015.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775016.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775017.png" /> is the [[Greatest common divisor|greatest common divisor]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775019.png" />.
 
 
 
Thanks to the last property, the least common multiple of two numbers can be found with the aid of the [[Euclidean algorithm|Euclidean algorithm]]. The concept of the least common multiple can be defined for elements of an integral domain, and also for ideals of a commutative ring.
 
  
 
====References====
 
====References====
Line 29: Line 32:
  
 
====Comments====
 
====Comments====
Other frequently used notations for the least common multiple are: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057750/l05775022.png" />, etc. In a [[unique factorization domain]] least common multiples exist and are unique (up to units).
+
Other frequently used notations for the least common multiple are: $\text{lcm}(a_1,\ldots,a_n)$, $\text{LCM}(a_1,\ldots,a_n)$, $\text{l.c.m.}(a_1,\ldots,a_n)$, etc.  
 +
 
 +
 
 +
 
 +
{{TEX|done}}

Latest revision as of 20:19, 2 November 2016

The smallest positive number among the common multiples of a finite set of integers or, in particular, of natural numbers, $a_1,\ldots,a_n$. The least common multiple of the numbers $a_1,\ldots,a_n$ exists if $a_1 \cdots a_n \neq 0$. It is usually denoted by $[a_1,\ldots,a_n]$.

Properties of the least common multiple are:

1) the least common multiple of $a_1,\ldots,a_n$ is a divisor of any other common multiple;

2) $[a_1,\ldots,a_{n+1}] = [[a_1,\ldots,a_n],a_{n+1}]$;

3) if the integers $a_1,\ldots,a_n$ are expressed as $$ a_i = p_1^{e_{i1}} \cdots p_k^{e_{ik}} $$ where $p_1,\ldots,p_k$ are distinct primes, $e_{ij} \ge 0$, $i=1,\ldots,n$, $j=1,\ldots,k$, and $f_j = \max\{e_{1j},\ldots,e_{nj} \}$, $j=1,\ldots,k$, then $$ [a_1,\ldots,a_n] = p_1^{f_1} \cdots p_k^{f_k} \ ; $$

4) if $ab > 0$, then $ab = [a,b](a,b)$, where $(a,b)$ is the greatest common divisor of $a,b$.

Thanks to the last property, the least common multiple of two numbers (and so by (2), of any finite set) can be found with the aid of the Euclidean algorithm.

The concept of the least common multiple can be defined for elements of an integral domain, and also for ideals of a commutative ring. In a unique factorization domain least common multiples exist and are unique (up to units).

References

[1] I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)
[2] A.A. Bukhshtab, "Number theory" , Moscow (1966) (In Russian)
[3] R. Faure, A. Kaufman, M. Denis-Papin, "Mathématique nouvelles" , 1–2 , Dunod (1964)


Comments

Other frequently used notations for the least common multiple are: $\text{lcm}(a_1,\ldots,a_n)$, $\text{LCM}(a_1,\ldots,a_n)$, $\text{l.c.m.}(a_1,\ldots,a_n)$, etc.

How to Cite This Entry:
Least common multiple. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Least_common_multiple&oldid=37550
This article was adapted from an original article by V.I. NechaevA.A. Bukhshtab (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article