|
Trong [[số học]], '''bội số chung nhất nhất''' (hay còn gọi tắt là '''bội chung nhỏ nhất''', viết tắt là '''BCNN''', tiếng Anh: least common multiple hoặc lowest common multiple ('''lcm''') hoặc smallest common multiple) của hai số nguyên a và b là số nguyên dương nhỏ nhất chia hết cho cả ''a'' và ''b''. Tức là nó có thể chia cho ''a'' và ''b'' mà không để lại [[số dư]]. nếu ''a'' hoặc ''b'' là 0, thì không tồn tại số nguyên dương chia hết cho a và b, khi đó quy ước rằng lcm(''a'', ''b'') là 0.
{{Đang dịch 2 (nguồn)|ngày=19
|tháng=10
|năm=2009
|1 =
}}
Trong số học, '''bội số chung nhất nhất''' (hay còn gọi tắt là '''bội chung nhỏ nhất''', viết tắt là '''BCNN''', tiếng Anh: least common multiple hoặc lowest common multiple ('''lcm''') hoặc smallest common multiple) của hai số nguyên a và b là số nguyên dương nhỏ nhất chia hết cho cả ''a'' và ''b''. Tức là nó có thể chia cho ''a'' và ''b'' mà không để lại [[số dư]]. nếu ''a'' hoặc ''b'' là 0, thì không tồn tại số nguyên dương chia hết cho a và b, khi đó quy ước rằng lcm(''a'', ''b'') là 0.
Định nghĩa trên đôi khi được tổng quá hoát cho hơn hai số nguyên dương: Bội chung nhỏ nhất của ''a''<sub>1</sub>, ..., ''a<sub>n</sub>'' là số nguyên dương nhỏ nhất là bội số của ''a''<sub>1</sub>, ..., ''a<sub>n</sub>''.
==Kí hiệu==
Bội số chung của 2 số a và b được kí hiệu là ''(a,b), bcnn(a,b)'' hoặc ''lcm(a,b)''.
Kí hiệu tương tự cho bội số chung nhỏ nhất của ''a''<sub>1</sub>, ..., ''a<sub>n</sub>''.
== Ví dụ==
== Tính bội số chung nhỏ nhất ==
=== ReductionTính byqua the[[ước greatestsố commonchung divisorlớn nhất]] ===
Công thức dưới đây chuyển từ việc tính bội số chung nhỏ nhất sang tính [[ước số chung lớn nhất]] (GCD):
The following formula reduces the problem of computing the least common multiple to the problem of computing the [[greatest common divisor]] (GCD):
:<math>\operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)}.</math>
There are fast [[algorithm]]s for computing the GCD that do not require the numbers to be factored, such as the [[Euclidean algorithm]]. To return to the example above,
Có một [[thuật toán]] nhanh để tìm GCD mà không yêu cầu [[phần tích ra thừa số nguyên tố]], đó là [[thuật toán Euclid]].
Ví dụ:
:<math>\operatorname{lcm}(21,6)
={21\cdot 6\over 3}={126\over 3}=42.</math>
BecauseBởi gcd(''a'', ''b'') islà aước divisorsố ofcủa bothcả ''a'' andvà ''b'', it'snên moresẽ efficientthuật tolợi computehơn thenếu tính LCM bybằng dividingcách chia ''beforetrước khi'' multiplyingnhân:
:<math>\operatorname{lcm}(a,b)=\left({|a|\over\operatorname{gcd}(a,b)}\right)\cdot |b|=\left({|b|\over\operatorname{gcd}(a,b)}\right)\cdot |a|.</math>
Điều này làm giảm kích thước đầu vào, giảm bộ nhớ cho các giá trị trung gian. Làm theo cách này thì ví dụ trên trở thành:
This reduces the size of one input for both the division and the multiplication, and reduces the required storage needed for intermediate results. Done this way, the previous example becomes:
:<math>\operatorname{lcm}(21,6)={21\over\operatorname{gcd}(21,6)}\cdot6={21\over3}\cdot6=7\cdot6=42.</math>
===Tìm bội chung nhỏ nhất bằng cách phân tích ra thừa số nguyên tố ===
=== Finding least common multiples by prime factorization ===
[[Định lý cơ bản của số học]] nói rằng mọi số nguyên dương lớn hơn 1 có thể biểu diễn một cách duy nhất dạng tích các [[số nguyên tố]] (nếu không kể đến thứ tự của các thừa số). Như vậy các hợp số có thể coi như là các nguyên tố cấu thành [[hợp số]].
Ví dụ:
The [[fundamental theorem of arithmetic|unique factorization theorem]] says that every positive integer greater than 1 can be written in only one way as a product of [[prime number]]s. The prime numbers can be considered as the atomic elements which, when combined together, make up a [[composite number]].
For example:
:<math>90 = 2^1 \cdot 3^2 \cdot 5^1 = 2 \cdot 3 \cdot 3 \cdot 5. \,\!</math>
HereỞ weđây havechúng theta compositecó numberhợp số 90 madetạo upthành ofbởi onemột atomnguyên oftử the prime number '''2''', twohai atomsnguyên of the prime numbertử '''3''' and one atom ofvà themột primenguyên numbertử '''5'''.
Kiến thức này có thể giúp chúng ta tìm lcm của một tập hợp các số.
This knowledge can be used to find the lcm of a set of numbers.
ExampleVí dụ: FindTìm thegiá valuetrị ofcủa lcm(8,9,21).
Đầu tiên, ta phân tích từng số thành dạng tích lũy thừa các số nguyên tố.
First, factor out each number and express it as a product of prime number [[Power (mathematics)|powers]].
:<math>8\; \, \; \,= 2^3 \cdot 3^0 \cdot 5^0 \cdot 7^0 \,\!</math>
:<math>9\; \, \; \,= 2^0 \cdot 3^2 \cdot 5^0 \cdot 7^0 \,\!</math>
:<math>21\; \,= 2^0 \cdot 3^1 \cdot 5^0 \cdot 7^1. \,\!</math>
TheVới lcmmỗi willsố benguyên thetố, productchọn oflũy multiplyingthừa thecao highestnhất, powertích incủa eachchúng primecho factorta categorygiá together.trị Outlcm ofcần thetìm. 4bốn primethừa factorsố categoriesnguyên tố 2, 3, 5, andvà 7, thecó highestbậc powerscao fromnhất eachlần arelượt là 2<sup>3</sup>, 3<sup>2</sup>, 5<sup>0</sup>, andvà 7<sup>1</sup>. ThusDo đó,
:<math>\operatorname{lcm}(8,9,21) = 2^3 \cdot 3^2 \cdot 5^0 \cdot 7^1 = 8 \cdot 9 \cdot 1 \cdot 7 = 504. \,\!</math>
Thuật toán không thực sự hiệu quả bằng cách rút từ ước chung lớn nhất, bởi chưa có thuật toán hiệu quả để [[phân tích số nguyên]], nhưng nó hiệu quả trong việc minh họa khái niệm.
This method is not as efficient as reducing to the greatest common divisor, since there is no known general efficient algorithm for [[integer factorization]], but is useful in illustrating concepts.
This method can be illustrated using a [[Venn diagram]] as follows. Find the [[prime factorization]] of each of the two numbers. Put the prime factors into a Venn diagram with one circle for each of the two numbers, and ''all'' factors they share in common in the intersection. To find the LCM, just multiply all of the prime numbers in the diagram.
Here is an example:
: 48 = 2 × 2 × 2 × 2 × 3,
: 180 = 2 × 2 × 3 × 3 × 5,
and what they share in common is two "2"s and a "3":
:[[Image:least common multiple.svg|400px]]
: Least common multiple = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720
: Greatest common divisor = 2 × 2 × 3 = 12
This also works for the [[greatest common divisor]] (GCD), except that instead of multiplying all of the numbers in the Venn diagram, one multiplies only the prime factors that are in the intersection. Thus the GCD of 48 and 180 is 2 × 2 × 3 = 12.
===An algorithm-based method===
This method works as easily for finding the LCM of several integers.
Let there be a finite sequence of positive integers ''X'' = (''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub>), ''n'' > 1. The algorithm proceeds in steps as follows: on each step ''m'' it examines and updates the sequence ''X''<sup>(''m'')</sup> = (''x''<sub>1</sub><sup>(''m'')</sup>, ''x''<sub>2</sub><sup>(''m'')</sup>, ..., ''x''<sub>''n''</sub><sup>(m)</sup>), ''X''<sup>(1)</sup> = ''X''. The purpose of the examination is to pick up the least (perhaps, one of many) element of the sequence ''X''<sup>(''m'')</sup>. Assuming ''x''<sub>''k''<sub>0</sub></sub><sup>(''m'')</sup> is the selected element, the sequence ''X''<sup>(''m''+1)</sup> is defined as
: ''x''<sub>''k''</sub><sup>(''m''+1)</sup> = ''x''<sub>''k''</sub><sup>(''m'')</sup>, ''k'' ≠ ''k''<sub>0</sub>
: ''x''<sub>''k''<sub>0</sub></sub><sup>(''m''+1)</sup> = ''x''<sub>''k''<sub>0</sub></sub><sup>(''m'')</sup> + ''x''<sub>''k''<sub>0</sub></sub>.
In other words, the least element is increased by the corresponding ''x'' whereas the rest of the elements pass from ''X''<sup>(''m'')</sup> to ''X''<sup>(''m''+1)</sup> unchanged.
The algorithm stops when all elements in sequence ''X''<sup>(''m'')</sup> are equal. Their common value ''L'' is exactly LCM(''X''). (For a proof and an interactive simulation see reference below, ''Algorithm for Computing the LCM''.)
===A method using a table===
This method works for any number of factors. You begin by listing all of the numbers vertically in a table like this (We can try 4, 7, 12, 21, and 42):
4 <br>
7 <br>
12 <br>
21 <br>
42 <br>
The process begins by dividing all of the factors by 2. If any of them divide evenly, write 2 at the top of the table and the result of division by 2 of each factor in the space to the right of each factor and below the 2. If they do not divide evenly, just rewrite the number again. If 2 does not divide evenly into any of the numbers, try 3.
{| class="wikitable" border="1"
|-
! ''x''
! 2
|-
| 4
| 2
|-
| 7
| 7
|-
| 12
| 6
|-
| 21
| 21
|-
| 42
| 21
|}
Now, check if 2 divides again
{| class="wikitable" border="1"
|-
! ''x''
! 2
! 2
|-
| 4
| 2
| 1
|-
| 7
| 7
| 7
|-
| 12
| 6
| 3
|-
| 21
| 21
| 21
|-
| 42
| 21
| 21
|}
Once 2 no longer divides, divide by 3. If 3 no longer divides, try 5 and 7. keep going until all of the numbers have been reduced to 1.
{| class="wikitable" border="1"
|-
! ''x''
! 2
! 2
! 3
! 7
|-
| 4
| 2
| 1
| 1
| 1
|-
| 7
| 7
| 7
| 7
| 1
|-
| 12
| 6
| 3
| 1
| 1
|-
| 21
| 21
| 21
| 7
| 1
|-
| 42
| 21
| 21
| 7
| 1
|}
Now, multiply the numbers on the top and you have the LCM. In this case, it is 2 × 2 × 3 × 7 = 84. This is a variation on Euclid's algorithm, as common factors are essentially divided out along the way of dividing all of the numbers at once by each successive factor. You will get to the LCM the quickest if you use prime numbers and start from the lowest prime, 2.
== The LCM in commutative rings ==
The least common multiple can be defined generally over [[commutative ring]]s as follows: Let ''a'' and ''b'' be elements of a commutative ring ''R''. A common multiple of ''a'' and ''b'' is an element ''m'' of ''R'' such that both ''a'' and ''b'' divide ''m'' (i.e. there exist elements ''x'' and ''y'' of ''R'' such that ''ax'' = ''m'' and ''by'' = ''m''). A least common multiple of ''a'' and ''b'' is a common multiple that is minimal in the sense that for any other common multiple ''n'' of ''a'' and ''b'', ''m'' divides ''n''.
In general, two elements in a commutative ring can have no least common multiple or more than one. However, any two least common multiples of the same pair of elements are [[Unit (ring theory)|associates]]. In a [[unique factorization domain]], any two elements have a least common multiple. In a [[principal ideal domain]], the least common multiple of ''a'' and ''b'' can be characterised as a generator of the intersection of the ideals generated by ''a'' and ''b'' (the intersection of a collection of ideals is always an ideal). In [[principal ideal domain]]s, one can even talk about the least common multiple of arbitrary collections of elements: it is a generator of the intersection of the ideals generated by the elements of the collection.
== SeeXem alsothêm ==
*[[Ước số chung lớn nhất]]
*[[Greatest common divisor]]
*[[Giản ước dị thường]]
*[[Anomalous cancellation]]
*[[ChebyshevHàm functionChebyshev]]
==Liên kết ngoài==
==External links==
* [http://www.easycalculation.com/hcf.php Online LCM calculator]
* [http://mathworld.wolfram.com/LeastCommonMultiple.html Least Common Multiple from Wolfram MathWorld]
[[Category:elementarysố arithmetichọc]]
[[Category:arithmetic]]
[[ar:مضاعف مشترك أصغر]]
| 