المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:کوچکترین مضرب مشترک

کوچک‌ترین مضرب مشترک

فرض کنید $a_1,a_2,\cdots,a_n$ اعدادی صحیح و نا صفر باشند. عدد صحیح k را مضرب مشترکی از $a_1,a_2,\cdots,a_n$ می‌نامیم، به شرطی که k همه‌ی $a_1$ تا $a_n$ را بشمارد.

مثلاً اگر t عددی صحیح باشد $t.a_1,a_2,\cdots,a_n$ مضرب مشترکی از $a_1,a_2,\cdots,a_n$ است؛ بنابراین، تعداد مضرب‌های مشترک $a_1,a_2,\cdots,a_n$ نامتناهی است.

در میان مضرب‌های مشترک مثبت $a_1,a_2,\cdots,a_n$ کوچکترین عدد را (که بنا بر اصل خوش ترتیبی وجود دارد.) کوچکترین مضرب مشترک $a_1,a_2,\cdots,a_n$ می‌نامیم و آن را با ‍[$a_1,a_2,\cdots,a_n$] d یا $lcm(a_1,a_2,\cdots,a_n)$ نشان می‌دهیم.

محاسبه ک.م.م

روش تجزیه به عوامل اول

برای محاسبه ک.م.م می‌توان همه اعداد را به عوامل اول تجزیه کرد. ک.م.م برابر حاصل ضرب عوامل مشترک با توان بزرگتر و عوامل غیر مشترک می‌شود.

برای مثال: $18=2.3^2$ و $84=2^2.3.7$ پس $[84, 18]= 2^2.3^2.7= 252$

با استفاده از ب.م.م

برای دو عدد a و b رابطه زیر بر قرار است. [a, b] = $\frac{a.b}{(a, b)}$

خواص ب.م.م و ک.م.م

۱. $lcm(a, b) = lcm(b, a)$

۲. $gcd(a, b) = gcd(b, a)$

۳. $lcm(a, lcm(b, c)) = lcm(lcm(a, b), c)$

۴. $gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)$

۵. $lcm(a, gcd(a, b)) = a$

۶. $gcd(a, lcm(a, b)) = a$

۷. $lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))$

۸. $gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))$


ابزار صفحه