Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

فرض کنید a1,a2,,an اعدادی صحیح و نا صفر باشند. عدد صحیح k را مضرب مشترکی از a1,a2,,an می‌نامیم، به شرطی که k همه‌ی a1 تا an را بشمارد.

مثلاً اگر t عددی صحیح باشد t.a1,a2,,an مضرب مشترکی از a1,a2,,an است؛ بنابراین، تعداد مضرب‌های مشترک a1,a2,,an نامتناهی است.

در میان مضرب‌های مشترک مثبت a1,a2,,an کوچکترین عدد را (که بنا بر اصل خوش ترتیبی وجود دارد.) کوچکترین مضرب مشترک a1,a2,,an می‌نامیم و آن را با ‍[a1,a2,,an] d یا lcm(a1,a2,,an) نشان می‌دهیم.

محاسبه ک.م.م

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

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

برای مثال: 18=2.32 و 84=22.3.7 پس [84,18]=22.32.7=252

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

برای دو عدد a و b رابطه زیر بر قرار است. [a, b] = 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))


ابزار صفحه