برای یادگیری نحوه یافتن بزرگترین مقسوم علیه مشترک دو یا چند عدد، باید بدانید اعداد طبیعی، اول و مختلط چیست.

عدد طبیعی هر عددی است که برای شمارش اعداد صحیح استفاده می شود.

اگر یک عدد طبیعی را فقط بر خودش و یک تقسیم کرد، آن را اول می نامند.

همه اعداد طبیعی را می توان بر خود و یک تقسیم کرد، اما تنها عدد اول زوج 2 است، همه اعداد اول دیگر را می توان بر دو تقسیم کرد. بنابراین فقط اعداد فرد می توانند اول باشند.

اعداد اول زیادی وجود دارد، لیست کاملی از آنها وجود ندارد. برای پیدا کردن GCD، استفاده از جداول ویژه با چنین اعدادی راحت است.

اکثر اعداد طبیعی را می توان نه تنها بر یک، بلکه بر اعداد دیگر نیز تقسیم کرد. به عنوان مثال، عدد 15 را می توان بر 3 و 5 تقسیم کرد که به همه آنها مقسوم علیه عدد 15 می گویند.

بنابراین مقسوم علیه هر A عددی است که می توان آن را بدون باقیمانده بر آن تقسیم کرد. اگر عددی بیش از دو مقسوم علیه طبیعی داشته باشد آن را مرکب می نامند.

عدد 30 دارای مقسوم علیه هایی مانند 1، 3، 5، 6، 15، 30 است.

می بینید که 15 و 30 مقسوم علیه های 1، 3، 5، 15 یکسان دارند. بزرگترین مقسوم علیه مشترک این دو عدد 15 است.

بنابراین، مقسوم علیه مشترک اعداد A و B عددی است که می توانید آنها را به طور کامل بر آن تقسیم کنید. حداکثر را می توان حداکثر تعداد کل در نظر گرفت که می توان آنها را بر آن تقسیم کرد.

برای حل مسائل از کتیبه اختصاری زیر استفاده می شود:

GCD (A; B).

به عنوان مثال، GCD (15؛ 30) = 30.

برای نوشتن تمام مقسوم علیه های اعداد طبیعی، از نماد استفاده می شود:

D(15) = (1، 3، 5، 15)

gcd (9؛ 15) = 1

در این مثال اعداد طبیعی فقط یک مقسوم علیه مشترک دارند. آنها به ترتیب coprime نامیده می شوند، واحد بزرگترین مقسوم علیه مشترک آنها است.

چگونه بزرگترین مقسوم علیه مشترک اعداد را پیدا کنیم

برای پیدا کردن GCD چندین اعداد، شما نیاز دارید:

همه مقسوم علیه های هر عدد طبیعی را به طور جداگانه بیابید، یعنی آنها را به عوامل (اعداد اول) تجزیه کنید.

همه عوامل مشابه را برای اعداد داده شده انتخاب کنید.

آنها را با هم ضرب کنید.

به عنوان مثال، برای محاسبه بزرگترین مقسوم علیه اعداد 30 و 56، باید موارد زیر را بنویسید:

برای اینکه با گیج نشوید، نوشتن ضرب کننده ها با استفاده از ستون های عمودی راحت است. در سمت چپ خط، شما باید سود سهام را قرار دهید، و در سمت راست - تقسیم کننده. در زیر سود سهام، باید ضریب حاصل را نشان دهید.

بنابراین، در ستون سمت راست تمام عوامل مورد نیاز برای حل وجود خواهد داشت.

برای راحتی می توان بر تقسیم کننده های یکسان (عوامل یافت شده) خط کشی کرد. آنها باید بازنویسی و ضرب شوند و بزرگترین مقسوم علیه مشترک نوشته شود.

GCD (30؛ 56) = 2 * 5 = 10

پیدا کردن بزرگترین مقسوم علیه مشترک اعداد واقعاً به همین راحتی است. با کمی تمرین می توانید این کار را تقریبا به صورت خودکار انجام دهید.

بزرگترین عدد طبیعی که اعداد a و b بدون باقی مانده بر آن بخش پذیرند نامیده می شود بزرگترین مقسوم علیه مشترکاین اعداد GCD (a, b) را نشان دهید.

پیدا کردن GCD را با استفاده از مثال دو عدد طبیعی 18 و 60 در نظر بگیرید:

1 بیایید اعداد را به عوامل اول تجزیه کنیم:
18 = 2×3×3
60 = 2×2×3×5

2 از بسط عدد اول تمام عواملی که در بسط عدد دوم گنجانده نشده اند را حذف می کنیم. 2×3×3 .

3 فاکتورهای اول باقیمانده را پس از خط زدن ضرب می کنیم و بزرگترین مقسوم علیه مشترک اعداد را بدست می آوریم: gcd ( 18 , 60 )=2×3= 6 .

4 توجه داشته باشید که از شماره اول یا دوم که فاکتورها را خط می زنیم مهم نیست، نتیجه یکسان خواهد بود:
18 = 2×3×3
60 = 2×2×3×5

324 , 111 و 432

بیایید اعداد را به عوامل اول تجزیه کنیم:

324 = 2×2×3×3×3×3

111 = 3×37

432 = 2×2×2×2×3×3×3

حذف از عدد اول که فاکتورهای آن در اعداد دوم و سوم نیست به دست می آید:

2 x 2 x 2 x 2 x 3 x 3 x 3 = 3

در نتیجه GCD( 324 , 111 , 432 )=3

یافتن GCD با الگوریتم اقلیدس

راه دوم برای پیدا کردن بزرگترین مقسوم علیه مشترک با استفاده از الگوریتم اقلیدس. الگوریتم اقلیدس کارآمدترین راه برای یافتن است GCD، با استفاده از آن باید دائماً باقیمانده تقسیم اعداد را پیدا کنید و اعمال کنید فرمول مکرر.

فرمول مکرربرای GCD، gcd(a, b)=gcd(b, a mod b)، که در آن a mod b باقیمانده تقسیم a بر b است.

الگوریتم اقلیدس

مثال بزرگترین مقسوم علیه اعداد را پیدا کنید 7920 و 594

بیایید GCD را پیدا کنیم( 7920 , 594 ) با استفاده از الگوریتم اقلیدس، باقیمانده تقسیم را با استفاده از ماشین حساب محاسبه می کنیم.

GCD( 7920 , 594 )

GCD( 594 , 7920 مد 594 ) = gcd( 594 , 198 )

GCD( 198 , 594 مد 198 ) = gcd( 198 , 0 )

GCD( 198 , 0 ) = 198

• 7920 mod 594 = 7920 - 13 × 594 = 198
• 594 mod 198 = 594 - 3 × 198 = 0

در نتیجه، GCD ( 7920 , 594 ) = 198

کمترین مضرب مشترک

برای یافتن مخرج مشترک هنگام جمع و تفریق کسری با مخرج های مختلف، باید بدانید و بتوانید محاسبه کنید. حداقل مضرب مشترک(NOC).

مضرب عدد "الف" عددی است که خود بدون باقیمانده بر عدد "الف" بخش پذیر است.

اعداد مضرب 8 (یعنی این اعداد بدون باقیمانده بر 8 تقسیم می شوند): اینها اعداد 16، 24، 32 هستند ...

مضرب 9: 18، 27، 36، 45…

بی نهایت مضرب یک عدد معین a وجود دارد، برخلاف مقسوم علیه های همان عدد. مقسوم علیه - یک عدد محدود.

مضرب مشترک دو عدد طبیعی عددی است که به طور مساوی بر هر دوی این اعداد بخش پذیر باشد..

کمترین مضرب مشترک(LCM) دو یا چند عدد طبیعی کوچکترین عدد طبیعی است که خود بر هر یک از این اعداد بخش پذیر است.

نحوه پیدا کردن NOC

LCM را می توان به دو صورت یافت و نوشت.

اولین راه برای پیدا کردن LCM

این روش معمولا برای اعداد کم استفاده می شود.

1. مضرب هر یک از اعداد را در یک خط می نویسیم تا زمانی که مضربی برای هر دو عدد یکسان باشد.
2. مضرب عدد "a" با حرف بزرگ "K" نشان داده می شود.

مثال. LCM 6 و 8 را پیدا کنید.

راه دوم برای پیدا کردن LCM

استفاده از این روش برای یافتن LCM برای سه عدد یا بیشتر راحت است.

تعداد عوامل یکسان در بسط اعداد می تواند متفاوت باشد.

در بسط عدد کوچکتر (اعداد کوچکتر)، زیر عواملی که در بسط عدد بزرگتر لحاظ نشده اند (در مثال ما 2 است) خط بکشید و این عوامل را به بسط عدد بزرگتر اضافه کنید.
LCM (24، 60) = 2 2 3 5 2

کار حاصل را در پاسخ ثبت کنید.
پاسخ: LCM (24، 60) = 120

همچنین می توانید یافتن کمترین مضرب مشترک (LCM) را به صورت زیر رسمی کنید. بیایید LCM (12، 16، 24) را پیدا کنیم.

24 = 2 2 2 3

همانطور که از بسط اعداد می بینیم، همه عوامل 12 در بسط 24 (بزرگترین اعداد) گنجانده شده اند، بنابراین فقط یک 2 از بسط عدد 16 به LCM اضافه می کنیم.

LCM (12، 16، 24) = 2 2 2 3 2 = 48

پاسخ: LCM (12، 16، 24) = 48

موارد خاص یافتن NOCs

اگر یکی از اعداد به طور مساوی بر اعداد دیگر بخش پذیر باشد، کمترین مضرب مشترک این اعداد برابر با این عدد است.

به عنوان مثال، LCM(60، 15) = 60
از آنجایی که اعداد هم اول هیچ مقسوم علیه اول مشترکی ندارند، حداقل مضرب مشترک آنها برابر حاصلضرب این اعداد است.

در سایت ما، می‌توانید از یک ماشین‌حساب مخصوص برای یافتن کمترین مضرب آنلاین برای بررسی محاسبات خود استفاده کنید.

اگر یک عدد طبیعی فقط بر 1 و خودش بخش پذیر باشد، آن را اول می گویند.

هر عدد طبیعی همیشه بر 1 و خودش بخش پذیر است.

عدد 2 کوچکترین عدد اول است. این تنها عدد اول زوج است، بقیه اعداد اول فرد هستند.

اعداد اول زیادی وجود دارد و اولین عدد در میان آنها عدد 2 است. با این حال، آخرین عدد اول وجود ندارد. در قسمت "برای مطالعه" می توانید جدول اعداد اول تا 997 را دانلود کنید.

اما بسیاری از اعداد طبیعی به طور مساوی بر سایر اعداد طبیعی بخش پذیرند.

• عدد 12 بر 1، بر 2، بر 3، بر 4، بر 6، بر 12 بخش پذیر است.
• 36 بر 1، بر 2، بر 3، بر 4، بر 6، بر 12، بر 18، بر 36 بخش پذیر است.

اعدادی که عدد بر آنها به طور مساوی بخش پذیر است (برای 12 اینها 1، 2، 3، 4، 6 و 12 هستند) مقسوم علیه اعداد نامیده می شوند.

مقسوم علیه یک عدد طبیعی a عددی طبیعی است که عدد داده شده "a" را بدون باقیمانده تقسیم می کند.

عدد طبیعی که بیش از دو عامل داشته باشد، عدد مرکب نامیده می شود.

توجه داشته باشید که اعداد 12 و 36 مقسوم علیه مشترک دارند. اینها اعداد هستند: 1، 2، 3، 4، 6، 12. بزرگترین مقسوم علیه این اعداد 12 است.

مقسوم علیه مشترک دو عدد داده شده "الف" و "ب" عددی است که هر دو عدد "الف" و "ب" بدون باقی مانده بر آن تقسیم می شوند.

بزرگترین مقسوم علیه مشترک(GCD) دو عدد داده شده "a" و "b" بزرگترین عددی است که هر دو عدد "a" و "b" بدون باقی مانده بر آن بخش پذیر هستند.

به طور خلاصه بزرگترین مقسوم علیه مشترک اعداد "الف" و "ب" به صورت زیر نوشته می شود:

مثال: gcd (12; 36) = 12.

مقسوم علیه اعداد در رکورد حل با حرف بزرگ "D" نشان داده می شود.

اعداد 7 و 9 فقط یک مقسوم علیه مشترک دارند - عدد 1. چنین اعدادی نامیده می شوند اعداد همزمان اول.

اعداد همزمان اولاعداد طبیعی هستند که فقط یک مقسوم علیه مشترک دارند - عدد 1. GCD آنها 1 است.

چگونه بزرگترین مقسوم علیه مشترک را پیدا کنیم

برای پیدا کردن gcd دو یا چند عدد طبیعی نیاز دارید:

• تقسیم کننده های اعداد را به ضرایب اول تجزیه کنید.

محاسبات به راحتی با استفاده از یک نوار عمودی نوشته می شوند. در سمت چپ خط، ابتدا سود سهام را یادداشت کنید، در سمت راست - تقسیم کننده. در ادامه در ستون سمت چپ مقادیر private را یادداشت می کنیم.

بیایید بلافاصله با یک مثال توضیح دهیم. بیایید اعداد 28 و 64 را به فاکتورهای اول فاکتور کنیم.

زیر عوامل اول یکسان در هر دو عدد خط بکشید.
28 = 2 2 7

64 = 2 2 2 2 2 2
حاصل ضرب عوامل اول یکسان را پیدا کرده و پاسخ را یادداشت می کنیم.
GCD (28؛ 64) = 2 2 = 4

پاسخ: GCD (28؛ 64) = 4

می توانید مکان GCD را به دو روش ترتیب دهید: در یک ستون (همانطور که در بالا انجام شد) یا "در یک خط".

اولین راه برای نوشتن GCD

GCD 48 و 36 را پیدا کنید.

GCD (48؛ 36) = 2 2 3 = 12

روش دوم برای نوشتن GCD

حالا بیایید راه حل جستجوی GCD را در یک خط بنویسیم. GCD 10 و 15 را پیدا کنید.

در سایت اطلاعات ما، همچنین می توانید بزرگترین مقسوم علیه مشترک را به صورت آنلاین با استفاده از برنامه Helper برای بررسی محاسبات خود بیابید.

یافتن کمترین مضرب مشترک، روش ها، نمونه هایی برای یافتن LCM.

مطالب ارائه شده در زیر ادامه منطقی نظریه از مقاله تحت عنوان LCM - حداقل چندگانه مشترک، تعریف، مثال ها، رابطه بین LCM و GCD است. در اینجا ما در مورد صحبت خواهیم کرد یافتن کمترین مضرب مشترک (LCM)، و به حل مثال ها توجه ویژه ای داشته باشید. اجازه دهید ابتدا نشان دهیم که چگونه LCM دو عدد بر حسب GCD این اعداد محاسبه می شود. در مرحله بعد، یافتن کمترین مضرب مشترک را با فاکتورگیری اعداد در ضرایب اول در نظر بگیرید. پس از آن بر روی یافتن LCM سه یا چند عدد تمرکز می کنیم و همچنین به محاسبه LCM اعداد منفی می پردازیم.

پیمایش صفحه.

محاسبه کمترین مضرب مشترک (LCM) از طریق gcd

یکی از راه های یافتن کمترین مضرب مشترک بر اساس رابطه بین LCM و GCD است. رابطه موجود بین LCM و GCD به شما امکان می دهد حداقل مضرب مشترک دو عدد صحیح مثبت را از طریق بزرگترین مقسوم علیه مشترک شناخته شده محاسبه کنید. فرمول مربوطه دارای فرم است LCM(a, b)=a b: GCM(a, b). نمونه هایی از یافتن LCM را طبق فرمول بالا در نظر بگیرید.

کوچکترین مضرب مشترک دو عدد 126 و 70 را پیدا کنید.

در این مثال a=126، b=70. بیایید از پیوند LCM با GCD استفاده کنیم که با فرمول LCM(a, b)=a b: GCM(a, b) بیان می شود. یعنی ابتدا باید بزرگترین مقسوم علیه اعداد 70 و 126 را پیدا کنیم و بعد از آن می توانیم LCM این اعداد را طبق فرمول نوشته شده محاسبه کنیم.

gcd(126, 70) را با استفاده از الگوریتم اقلیدس پیدا کنید: 126=70 1+56، 70=56 1+14، 56=14 4، از این رو gcd(126، 70)=14.

اکنون حداقل مضرب مشترک مورد نیاز را پیدا می کنیم: LCM(126, 70)=126 70:GCD(126, 70)= 126 70:14=630.

LCM(68, 34) چیست؟

از آنجایی که 68 به طور مساوی بر 34 بخش پذیر است، پس gcd(68, 34)=34. اکنون کمترین مضرب مشترک را محاسبه می کنیم: LCM(68, 34)=68 34:GCD(68, 34)= 68 34:34=68.

توجه داشته باشید که مثال قبلی با قانون زیر برای یافتن LCM برای اعداد صحیح مثبت a و b مطابقت دارد: اگر عدد a بر b بخش پذیر باشد، کمترین مضرب مشترک این اعداد a است.

یافتن LCM با فاکتورسازی اعداد به فاکتورهای اولیه

راه دیگر برای یافتن کمترین مضرب مشترک بر اساس فاکتورگیری اعداد به ضرایب اول است. اگر از تمام ضرایب اول این اعداد حاصل ضربی بسازیم، پس از آن، همه ضرایب اول مشترکی را که در بسط این اعداد وجود دارند از این حاصلضرب حذف کنیم، حاصل ضرب حاصل برابر با کمترین مضرب مشترک این اعداد خواهد بود.

قانون اعلام شده برای یافتن LCM از برابری LCM(a, b)=a b: GCM(a, b) ناشی می شود. در واقع، حاصل ضرب اعداد a و b برابر است با حاصلضرب همه عوامل دخیل در بسط اعداد a و b. به نوبه خود، gcd(a, b) برابر است با حاصلضرب همه عوامل اولی که به طور همزمان در بسط اعداد a و b وجود دارند (که در بخش یافتن gcd با استفاده از تجزیه اعداد به ضرایب اول توضیح داده شده است. ).

بیایید یک مثال بزنیم. بگذارید بدانیم که 75=3 5 5 و 210=2 3 5 7 . حاصل ضرب همه عوامل این بسط ها را بنویسید: 2 3 3 5 5 5 7 . حال تمام عواملی را که هم در بسط عدد 75 و هم در بسط عدد 210 وجود دارد را از این محصول حذف می کنیم (این گونه عوامل 3 و 5 هستند)، سپس حاصلضرب به شکل 2 3 5 5 7 خواهد بود. مقدار این حاصلضرب برابر است با کمترین مضرب مشترک 75 و 210 یعنی LCM(75, 210)= 2 3 5 5 7=1 050 .

بعد از اینکه اعداد 441 و 700 را در ضرایب اول قرار دادید، کمترین مضرب مشترک این اعداد را پیدا کنید.

بیایید اعداد 441 و 700 را به عوامل اول تجزیه کنیم:

441=3 3 7 7 و 700 = 2 2 5 5 7 بدست می آوریم.

حال بیایید از همه عوامل دخیل در بسط این اعداد حاصل ضرب کنیم: 2 2 3 3 5 5 7 7 7 . اجازه دهید همه عواملی را که به طور همزمان در هر دو بسط وجود دارند از این محصول حذف کنیم (فقط یک عامل وجود دارد - این عدد 7 است): 2 2 3 3 5 5 7 7 . بنابراین LCM(441, 700)=2 2 3 3 5 5 7 7 = 44 100 .

LCM(441، 700)= 44 100 .

قانون برای یافتن LCM با استفاده از تجزیه اعداد به عوامل اول را می توان کمی متفاوت فرموله کرد. اگر عوامل گمشده از بسط عدد b را به عوامل حاصل از بسط عدد a اضافه کنیم، مقدار حاصلضرب برابر با کمترین مضرب مشترک اعداد a و b خواهد بود.

به عنوان مثال، بیایید همه اعداد یکسان 75 و 210 را در نظر بگیریم، بسط آنها به ضرایب اول به صورت زیر است: 75=3 5 5 و 210=2 3 5 7 . به فاکتورهای 3، 5 و 5 از تجزیه عدد 75، فاکتورهای گمشده 2 و 7 را از تجزیه عدد 210 اضافه می کنیم، حاصل ضرب 2 3 5 5 7 را به دست می آوریم که مقدار آن LCM (75) است. ، 210).

کوچکترین مضرب مشترک 84 و 648 را پیدا کنید.

ابتدا تجزیه اعداد 84 و 648 را به عوامل اول بدست می آوریم. آنها شبیه 84=2 2 3 7 و 648=2 2 2 3 3 3 3 هستند. به فاکتورهای 2، 2، 3 و 7 از تجزیه عدد 84، فاکتورهای گمشده 2، 3، 3 و 3 را از تجزیه عدد 648 اضافه می کنیم، حاصل ضرب 2 2 2 3 3 3 3 7 را به دست می آوریم. که برابر با 4 536 است. بنابراین حداقل مضرب مشترک مورد نظر اعداد 84 و 648 4536 است.

یافتن LCM سه یا چند عدد

کمترین مضرب مشترک سه یا چند عدد را می توان با یافتن متوالی LCM دو عدد پیدا کرد. قضیه مربوطه را به یاد بیاورید که راهی برای یافتن LCM سه یا چند عدد می دهد.

اجازه دهید اعداد صحیح مثبت a 1 , a 2 , ..., a k داده شوند، کمترین مضرب مشترک m k این اعداد در محاسبه ترتیبی یافت می شود m 2 = LCM (a 1 , a 2 ), m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , a k) .

کاربرد این قضیه را در مثال یافتن مضرب مشترک چهار عدد در نظر بگیرید.

LCM چهار عدد 140، 9، 54 و 250 را بیابید.

ابتدا m 2 = LCM (a 1 , a 2) = LCM (140, 9) را پیدا می کنیم. برای انجام این کار، با استفاده از الگوریتم اقلیدسی، gcd(140, 9) را تعیین می کنیم، 140=9 15+5، 9=5 1+4، 5=4 1+1، 4=1 4 داریم، بنابراین، gcd( 140، 9)=1، از آنجا LCM(140، 9)=140 9: GCD(140، 9)= 140 9:1=1 260. یعنی m 2 = 1 260 .

اکنون m 3 = LCM (m 2 , a 3) = LCM (1 260, 54) را پیدا می کنیم. بیایید آن را از طریق gcd(1 260, 54) محاسبه کنیم که توسط الگوریتم اقلیدس نیز تعیین می شود: 1 260=54 23+18 , 54=18 3 . سپس gcd(1 260, 54)=18، از آنجا LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . یعنی m 3 \u003d 3 780.

باقی مانده است که m 4 = LCM (m 3 , a 4) = LCM (3 780, 250) را پیدا کنید. برای انجام این کار، GCD(3 780, 250) را با استفاده از الگوریتم اقلیدس پیدا می کنیم: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . بنابراین، gcd(3 780, 250)=10، از این رو LCM(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . یعنی m 4 \u003d 94 500.

بنابراین کمترین مضرب مشترک چهار عدد اصلی 94500 است.

LCM(140، 9، 54، 250)=94500.

در بسیاری از موارد، کمترین مضرب مشترک سه یا چند اعداد به راحتی با استفاده از فاکتورسازی اول اعداد داده شده پیدا می شود. در این صورت باید از قانون زیر پیروی کرد. کمترین مضرب مشترک چند عدد برابر با حاصلضرب است که به صورت زیر تشکیل می شود: عوامل مفقود شده از بسط عدد دوم به همه عوامل از بسط عدد اول اضافه می شوند، عوامل مفقود از بسط عدد اول اضافه می شوند. عدد سوم به فاکتورهای بدست آمده اضافه می شود و غیره.

مثالی از یافتن کمترین مضرب مشترک با استفاده از تجزیه اعداد به عوامل اول را در نظر بگیرید.

کوچکترین مضرب مشترک پنج عدد 84، 6، 48، 7، 143 را بیابید.

ابتدا تجزیه این اعداد را به ضرایب اول به دست می آوریم: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 (7 عدد اول است، منطبق بر تجزیه آن به عوامل اول است) و 143=11 13.

برای یافتن LCM این اعداد، به فاکتورهای عدد اول 84 (آنها 2، 2، 3 و 7 هستند) باید فاکتورهای گمشده از تجزیه عدد دوم 6 را اضافه کنید. بسط عدد 6 شامل عوامل گمشده نیست، زیرا 2 و 3 در بسط اولین عدد 84 وجود دارند. علاوه بر فاکتورهای 2، 2، 3 و 7، فاکتورهای گمشده 2 و 2 را از بسط عدد سوم 48 جمع می کنیم، مجموعه ای از عوامل 2، 2، 2، 2، 3 و 7 را به دست می آوریم. در مرحله بعد نیازی به افزودن فاکتورها به این مجموعه نیست، زیرا 7 قبلاً در آن موجود است. در نهایت به فاکتورهای 2، 2، 2، 2، 3 و 7 فاکتورهای گمشده 11 و 13 را از بسط عدد 143 اضافه می کنیم. حاصل ضرب 2 2 2 2 3 7 11 13 را بدست می آوریم که برابر با 48 048 است.

بنابراین، LCM(84, 6, 48, 7, 143)=48048.

LCM(84، 6، 48، 7، 143)=48048.

یافتن کمترین مضرب مشترک اعداد منفی

گاهی اوقات کارهایی وجود دارد که در آنها باید کمترین مضرب مشترک اعداد را پیدا کنید که در میان آنها یک، چند یا همه اعداد منفی هستند. در این موارد، همه اعداد منفی باید با اعداد مخالف خود جایگزین شوند و پس از آن باید LCM اعداد مثبت را پیدا کرد. این راهی برای پیدا کردن LCM اعداد منفی است. برای مثال، LCM(54، -34)=LCM(54، 34) و LCM(-622، -46، -54، -888) = LCM(622، 46، 54، 888).

ما می توانیم این کار را انجام دهیم زیرا مجموعه مضرب a با مجموعه مضرب a -a یکسان است (a و -a اعداد متضاد هستند). در واقع، فرض کنید b مضرب a باشد، سپس b بر a بخش پذیر است، و مفهوم بخش پذیری وجود چنین عدد صحیح q را تایید می کند که b=a q . اما برابری b=(−a)·(−q) نیز صادق خواهد بود، که به موجب همان مفهوم تقسیم پذیری، به این معنی است که b بر −a بخش پذیر است، یعنی b مضرب −a است. عبارت معکوس نیز درست است: اگر b مضرب −a باشد، b نیز مضرب a است.

کوچکترین مضرب مشترک اعداد منفی -145 و -45 را پیدا کنید.

بیایید اعداد منفی -145 و -45 را با اعداد مقابل آنها 145 و 45 جایگزین کنیم. ما LCM(-145، -45)=LCM(145، 45) داریم. با تعیین gcd(145, 45)=5 (مثلاً با استفاده از الگوریتم اقلیدس)، LCM(145, 45)=145 45:gcd(145, 45)= 145 45:5=1 305 را محاسبه می کنیم. بنابراین، کمترین مضرب مشترک اعداد صحیح منفی -145 و -45 1305 است.

www.cleverstudents.ru

ما به مطالعه تقسیم بندی ادامه می دهیم. در این درس به مفاهیمی مانند GCDو NOC.

GCDبزرگترین مقسوم علیه مشترک است.

NOCکمترین مضرب مشترک است.

موضوع نسبتا خسته کننده است، اما درک آن ضروری است. بدون درک این موضوع، نمی توانید به طور موثر با کسری که یک مانع واقعی در ریاضیات است کار کنید.

بزرگترین مقسوم علیه مشترک

تعریف. بزرگترین مقسوم علیه اعداد آو ب آو ببدون باقیمانده تقسیم می شود

برای اینکه این تعریف را به خوبی درک کنیم، به جای متغیرها را جایگزین می کنیم آو ببه عنوان مثال، به جای یک متغیر، هر دو عدد آعدد 12 را جایگزین کنید و به جای متغیر بشماره 9. حال بیایید سعی کنیم این تعریف را بخوانیم:

بزرگترین مقسوم علیه اعداد 12 و 9 بزرگترین عددی است که توسط آن 12 و 9 بدون باقیمانده تقسیم می شود

از تعریف مشخص می شود که ما در مورد مقسوم علیه مشترک اعداد 12 و 9 صحبت می کنیم و این مقسوم علیه بزرگترین مقسوم علیه موجود است. این بزرگترین مقسوم علیه مشترک (gcd) باید پیدا شود.

برای یافتن بزرگترین مقسوم علیه مشترک دو عدد از سه روش استفاده می شود. روش اول کاملاً وقت گیر است، اما به شما امکان می دهد ماهیت موضوع را به خوبی درک کنید و کل معنای آن را احساس کنید.

روش دوم و سوم بسیار ساده است و یافتن سریع GCD را امکان پذیر می کند. ما هر سه روش را در نظر خواهیم گرفت. و چه چیزی را در عمل اعمال کنید - شما انتخاب می کنید.

راه اول این است که همه مقسوم علیه های ممکن دو عدد را پیدا کنید و بزرگترین آنها را انتخاب کنید. بیایید این روش را در مثال زیر در نظر بگیریم: بزرگترین مقسوم علیه مشترک اعداد 12 و 9 را پیدا کنید.

ابتدا همه مقسوم علیه های ممکن عدد 12 را پیدا می کنیم. برای این کار، 12 را به همه مقسوم علیه های 1 تا 12 تقسیم می کنیم. اگر مقسوم علیه به ما اجازه دهد که 12 را بدون باقی مانده تقسیم کنیم، آن را با رنگ آبی برجسته می کنیم و در داخل پرانتز توضیح مناسب بدهید.

12: 1 = 12
(12 تقسیم بر 1 بدون باقی مانده، بنابراین 1 مقسوم علیه 12 است)

12: 2 = 6
(12 تقسیم بر 2 بدون باقی مانده، بنابراین 2 مقسوم علیه 12 است)

12: 3 = 4
(12 تقسیم بر 3 بدون باقی مانده، بنابراین 3 مقسوم علیه 12 است)

12: 4 = 3
(12 تقسیم بر 4 بدون باقی مانده، بنابراین 4 مقسوم علیه 12 است)

12:5 = 2 (2 باقی مانده)
(12 بدون باقیمانده بر 5 تقسیم نمی شود، بنابراین 5 مقسوم علیه 12 نیست)

12: 6 = 2
(12 تقسیم بر 6 بدون باقی مانده، بنابراین 6 مقسوم علیه 12 است)

12: 7 = 1 (5 باقی مانده)
(12 بدون باقی مانده بر 7 تقسیم نمی شود، بنابراین 7 مقسوم علیه 12 نیست)

12: 8 = 1 (4 باقی مانده)
(12 بدون باقیمانده بر 8 تقسیم نمی شود، بنابراین 8 مقسوم علیه 12 نیست)

12:9 = 1 (3 باقی مانده)
(12 بدون باقی مانده بر 9 تقسیم نمی شود، بنابراین 9 مقسوم علیه 12 نیست)

12: 10 = 1 (2 باقی مانده)
(12 بدون باقی مانده بر 10 تقسیم نمی شود، بنابراین 10 مقسوم علیه 12 نیست)

12:11 = 1 (1 باقی مانده)
(12 بدون باقی مانده بر 11 تقسیم نمی شود، بنابراین 11 مقسوم علیه 12 نیست)

12: 12 = 1
(12 تقسیم بر 12 بدون باقی مانده، بنابراین 12 مقسوم علیه 12 است)

حال بیایید مقسوم علیه های عدد 9 را پیدا کنیم. برای این کار، تمام مقسوم علیه های 1 تا 9 را بررسی کنید.

9: 1 = 9
(9 تقسیم بر 1 بدون باقی مانده، بنابراین 1 مقسوم علیه 9 است)

9: 2 = 4 (1 باقی مانده)
(9 بدون باقی مانده بر 2 تقسیم نمی شود، بنابراین 2 مقسوم علیه 9 نیست)

9: 3 = 3
(9 تقسیم بر 3 بدون باقی مانده، بنابراین 3 مقسوم علیه 9 است)

9: 4 = 2 (1 باقی مانده)
(9 بدون باقی مانده بر 4 تقسیم نمی شود، بنابراین 4 مقسوم علیه 9 نیست)

9:5 = 1 (4 باقی مانده)
(9 بدون باقی مانده بر 5 تقسیم نمی شود، بنابراین 5 مقسوم علیه 9 نیست)

9: 6 = 1 (3 باقی مانده)
(9 بدون باقی مانده بر 6 تقسیم نمی شود، بنابراین 6 مقسوم علیه 9 نیست)

9:7 = 1 (2 باقی مانده)
(9 بدون باقی مانده بر 7 تقسیم نمی شود، بنابراین 7 مقسوم علیه 9 نیست)

9:8 = 1 (1 باقی مانده)
(9 بدون باقی مانده بر 8 تقسیم نمی شود، بنابراین 8 مقسوم علیه 9 نیست)

9: 9 = 1
(9 تقسیم بر 9 بدون باقی مانده، بنابراین 9 مقسوم علیه 9 است)

حال مقسوم علیه هر دو عدد را بنویسید. اعدادی که با رنگ آبی مشخص شده اند مقسوم علیه هستند. بیایید آنها را بنویسیم:

با نوشتن مقسوم‌گیرنده‌ها، می‌توانید فوراً تعیین کنید که کدام بزرگ‌ترین و رایج‌ترین است.

طبق تعریف، بزرگترین مقسوم علیه 12 و 9 عددی است که 12 و 9 بر آن به طور مساوی بخش پذیر باشند. بزرگترین و مشترک اعداد 12 و 9 عدد 3 است

هر دو عدد 12 و عدد 9 بدون باقی مانده بر 3 بخش پذیرند:

بنابراین gcd (12 و 9) = 3

راه دوم برای پیدا کردن GCD

اکنون راه دوم را برای یافتن بزرگترین مقسوم علیه مشترک در نظر بگیرید. ماهیت این روش تجزیه هر دو اعداد به ضرایب اول و ضرب اعداد مشترک است.

مثال 1. GCD اعداد 24 و 18 را پیدا کنید

ابتدا، بیایید هر دو عدد را به عوامل اول فاکتور کنیم:

حال عوامل مشترک آنها را ضرب می کنیم. برای اینکه گیج نشوید، می توان بر عوامل رایج زیر خط کشید.

ما به تجزیه عدد 24 نگاه می کنیم اولین عامل آن 2 است. ما در تجزیه عدد 18 به دنبال همان عامل هستیم و می بینیم که آن هم وجود دارد. هر دو مورد را زیر خط می کشیم:

مجدداً به تجزیه عدد 24 نگاه می کنیم. عامل دوم آن نیز 2 است. ما در تجزیه عدد 18 به دنبال همان عامل هستیم و می بینیم که برای بار دوم وجود ندارد. سپس ما چیزی را برجسته نمی کنیم.

دو مورد بعدی در بسط عدد 24 نیز در بسط عدد 18 وجود ندارد.

به آخرین عامل در تجزیه عدد 24 می گذریم. این ضریب 3 است. ما در تجزیه عدد 18 به دنبال همان عامل هستیم و می بینیم که آن هم وجود دارد. ما بر هر سه مورد تأکید می کنیم:

بنابراین، فاکتورهای مشترک اعداد 24 و 18، فاکتورهای 2 و 3 هستند. برای بدست آوردن GCD باید این عوامل را ضرب کرد:

بنابراین gcd (24 و 18) = 6

راه سوم برای یافتن GCD

حال سومین راه را برای یافتن بزرگترین مقسوم علیه مشترک در نظر بگیرید. ماهیت این روش در این واقعیت نهفته است که اعداد مورد جستجو برای بزرگترین مقسوم علیه مشترک به ضرایب اول تجزیه می شوند. سپس از تجزیه عدد اول عواملی که در تجزیه عدد دوم لحاظ نشده اند حذف می شوند. اعداد باقی مانده در بسط اول ضرب می شوند و GCD بدست می آید.

برای مثال بیایید GCD اعداد 28 و 16 را به این ترتیب پیدا کنیم. اول از همه، این اعداد را به عوامل اول تجزیه می کنیم:

ما دو بسط گرفتیم: و

حال از بسط عدد اول عواملی را که در بسط عدد دوم نمی گنجد حذف می کنیم. بسط عدد دوم شامل هفت نمی شود. ما آن را از اولین بسط حذف خواهیم کرد:

حالا فاکتورهای باقی مانده را ضرب می کنیم و GCD را می گیریم:

عدد 4 بزرگترین مقسوم علیه اعداد 28 و 16 است. هر دوی این اعداد بدون باقی مانده بر 4 بخش پذیرند:

مثال 2 GCD اعداد 100 و 40 را پیدا کنید

فاکتور گرفتن عدد 100

فاکتور گرفتن عدد 40

ما دو بسط گرفتیم:

حال از بسط عدد اول عواملی را که در بسط عدد دوم نمی گنجد حذف می کنیم. بسط عدد دوم شامل یک پنج نیست (فقط یک پنج وجود دارد). ما آن را از اولین تجزیه حذف می کنیم

اعداد باقیمانده را ضرب کنید:

به جواب 20 رسیدیم. پس عدد 20 بزرگترین مقسوم علیه اعداد 100 و 40 است. این دو عدد بدون باقی مانده بر 20 بخش پذیرند:

GCD (100 و 40) = 20.

مثال 3 gcd اعداد 72 و 128 را پیدا کنید

فاکتور گرفتن از عدد 72

فاکتور گرفتن عدد 128

2×2×2×2×2×2×2

حال از بسط عدد اول عواملی را که در بسط عدد دوم نمی گنجد حذف می کنیم. بسط عدد دوم شامل دو سه قلو نمی شود (اصلاً وجود ندارد). ما آنها را از اولین بسط حذف می کنیم:

به جواب 8 رسیدیم. پس عدد 8 بزرگترین مقسوم علیه اعداد 72 و 128 است. این دو عدد بدون باقی مانده بر 8 بخش پذیرند:

GCD (72 و 128) = 8

پیدا کردن GCD برای اعداد چندگانه

بزرگترین مقسوم علیه مشترک را می توان برای چندین عدد و نه فقط برای دو پیدا کرد. برای این کار، اعدادی که باید برای بزرگترین مقسوم علیه مشترک جستجو شوند، به ضرایب اول تجزیه می شوند، سپس حاصل ضرب ضرایب اول مشترک این اعداد پیدا می شود.

به عنوان مثال، بیایید GCD را برای اعداد 18، 24 و 36 پیدا کنیم

فاکتورگیری عدد 18

فاکتورگیری عدد 24

فاکتورگیری عدد 36

ما سه بسط گرفتیم:

حال عوامل رایج در این اعداد را انتخاب کرده و زیر آنها خط می زنیم. عوامل مشترک باید در هر سه عدد گنجانده شود:

می بینیم که فاکتورهای مشترک اعداد 18، 24 و 36 فاکتورهای 2 و 3 هستند. با ضرب این عوامل، GCD مورد نظر را به دست می آوریم:

ما جواب 6 را گرفتیم. بنابراین عدد 6 بزرگترین مقسوم علیه اعداد 18، 24 و 36 است. این سه عدد بدون باقی مانده بر 6 بخش پذیرند:

GCD (18، 24 و 36) = 6

مثال 2 gcd را برای اعداد 12، 24، 36 و 42 پیدا کنید

بیایید هر عدد را فاکتورسازی کنیم. سپس حاصل ضرب عوامل مشترک این اعداد را می یابیم.

فاکتورگیری عدد 12

فاکتورگیری عدد 42

ما چهار بسط گرفتیم:

حال عوامل رایج در این اعداد را انتخاب کرده و زیر آنها خط می زنیم. عوامل مشترک باید در هر چهار عدد گنجانده شود:

می بینیم که فاکتورهای مشترک برای اعداد 12، 24، 36 و 42، فاکتورهای 2 و 3 هستند. با ضرب این عوامل، GCD مورد نظر را به دست می آوریم:

ما جواب 6 را گرفتیم. بنابراین عدد 6 بزرگترین مقسوم علیه اعداد 12، 24، 36 و 42 است. این اعداد بدون باقی مانده بر 6 بخش پذیر هستند:

gcd(12، 24، 36 و 42) = 6

از درس قبل می دانیم که اگر عددی بدون باقی مانده بر عدد دیگری تقسیم شود، مضرب این عدد نامیده می شود.

معلوم می شود که یک مضرب می تواند با چندین عدد مشترک باشد. و اکنون ما به مضربی از دو عدد علاقه مند خواهیم بود، در حالی که باید تا حد امکان کوچک باشد.

تعریف. حداقل مضرب مشترک (LCM) اعداد آو ب- آو ب آو شماره ب.

تعریف شامل دو متغیر است آو ب. بیایید هر دو عدد را جایگزین این متغیرها کنیم. به عنوان مثال، به جای یک متغیر آعدد 9 را جایگزین کنید و به جای متغیر ببیایید عدد 12 را جایگزین کنیم. حالا بیایید سعی کنیم تعریف را بخوانیم:

حداقل مضرب مشترک (LCM) اعداد 9 و 12 - کوچکترین عددی است که مضرب است 9 و 12 . به عبارت دیگر، عدد بسیار کوچکی است که بدون باقیمانده بر عدد بخش پذیر است 9 و روی شماره 12 .

از تعریف مشخص است که LCM کوچکترین عددی است که بدون باقیمانده بر 9 و 12 بخش پذیر است. این LCM باید پیدا شود.

دو راه برای یافتن کمترین مضرب مشترک (LCM) وجود دارد. راه اول این است که می توانید مضرب های اول دو عدد را یادداشت کنید و سپس از بین این مضرب ها عددی را انتخاب کنید که برای هر دو عدد مشترک و کوچک باشد. بیایید این روش را اعمال کنیم.

اول از همه، بیایید اولین مضرب های عدد 9 را پیدا کنیم. برای پیدا کردن مضرب های 9، باید این نه را در اعداد 1 تا 9 ضرب کنید. بیا شروع کنیم. چندتایی با رنگ قرمز برجسته خواهند شد:

حالا مضرب عدد 12 را پیدا می کنیم. برای این کار عدد 12 را به ترتیب در تمام اعداد 1 تا 12 ضرب می کنیم.

دو راه برای یافتن بزرگترین مقسوم علیه مشترک در نظر بگیرید.

یافتن با فاکتورینگ

راه اول یافتن بزرگترین مقسوم علیه مشترک با فاکتورگیری اعداد داده شده به ضرایب اول است.

برای یافتن GCD چندین اعداد، کافی است آنها را به ضرایب اول تجزیه کرده و آنهایی را که در همه اعداد داده شده مشترک هستند، در بین خود ضرب کنیم.

مثال 1بیایید GCD را پیدا کنیم (84، 90).

اعداد 84 و 90 را به فاکتورهای اول تجزیه می کنیم:

بنابراین، ما زیر تمام عوامل اول مشترک خط کشیده ایم، باقی می ماند که آنها را در بین خود ضرب کنیم: 1 2 3 = 6.

بنابراین gcd(84، 90) = 6.

مثال 2بیایید GCD را پیدا کنیم (15، 28).

ما 15 و 28 را به عوامل اول تجزیه می کنیم:

اعداد 15 و 28 هم اول هستند زیرا بزرگترین مقسوم علیه مشترک آنها یک است.

gcd (15، 28) = 1.

الگوریتم اقلیدس

روش دوم (که روش دیگر اقلیدس نامیده می شود) یافتن GCD با تقسیم متوالی است.

ابتدا به این روش نگاه می کنیم که فقط برای دو عدد داده شده اعمال می شود و سپس نحوه اعمال آن را برای سه یا چند عدد مشخص می کنیم.

اگر بزرگتر از دو عدد داده شده بر کوچکتر بخش پذیر باشد، عددی که کوچکتر است بزرگترین مقسوم علیه مشترک آنها خواهد بود.

مثال 1دو عدد 27 و 9 را در نظر بگیرید. از آنجایی که 27 بر 9 بخش پذیر است و 9 بر 9 بخش پذیر است، پس 9 مقسوم علیه مشترک اعداد 27 و 9 است. از 9. بنابراین، gcd (27، 9) = 9.

در موارد دیگر، برای یافتن بزرگترین مقسوم علیه مشترک دو عدد، از روش زیر استفاده می شود:

1. از دو عدد داده شده، عدد بزرگتر بر عدد کوچکتر تقسیم می شود.
2. سپس عدد کوچکتر بر باقی مانده حاصل از تقسیم عدد بزرگتر بر عدد کوچکتر تقسیم می شود.
3. علاوه بر این، باقیمانده اول بر باقیمانده دوم تقسیم می شود که از تقسیم عدد کوچکتر بر باقی مانده اول به دست می آید.
4. باقیمانده دوم بر سومی تقسیم می شود که از تقسیم باقی مانده اول بر دومی به دست می آید و به همین ترتیب.
5. بنابراین، تقسیم تا زمانی ادامه می یابد که باقیمانده صفر شود. آخرین مقسوم علیه بزرگترین مقسوم علیه مشترک خواهد بود.

مثال 2بیایید بزرگترین مقسوم علیه اعداد 140 و 96 را پیدا کنیم:

1) 140: 96 = 1 (باقيمانده 44)

2) 96: 44 = 2 (باقی مانده 8)

3) 44: 8 = 5 (بقیه 4)

آخرین مقسوم علیه 4 است که به معنای gcd(140, 96) = 4 است.

تقسیم ترتیبی را می توان در یک ستون نیز نوشت:

برای پیدا کردن بزرگترین مقسوم علیه مشترک سه عدد یا بیشتر، از روش زیر استفاده کنید:

1. ابتدا بزرگترین مقسوم علیه مشترک هر دو عدد را از مجموعه داده های متعدد پیدا کنید.
2. سپس GCD مقسوم علیه پیدا شده و یک عدد سوم داده شده را پیدا می کنیم.
3. سپس GCD آخرین مقسوم علیه پیدا شده و چهارمین عدد داده شده و غیره را پیدا می کنیم.

مثال 3بیایید بزرگترین مقسوم علیه اعداد 140، 96 و 48 را پیدا کنیم. قبلاً GCD اعداد 140 و 96 را در مثال قبلی پیدا کرده ایم (این عدد 4 است). باقی مانده است که بزرگترین مقسوم علیه عدد 4 و سومین عدد داده شده - 48 را پیدا کنیم:

عدد 48 بدون باقی مانده بر 4 بخش پذیر است. بنابراین gcd (140، 96، 48) = 4.

یاد آوردن!

اگر یک عدد طبیعی فقط بر 1 و خودش بخش پذیر باشد، آن را اول می گویند.

هر عدد طبیعی همیشه بر 1 و خودش بخش پذیر است.

عدد 2 کوچکترین عدد اول است. این تنها عدد اول زوج است، بقیه اعداد اول فرد هستند.

اعداد اول زیادی وجود دارد و اولین عدد در میان آنها عدد 2 است. با این حال، آخرین عدد اول وجود ندارد. در قسمت "برای مطالعه" می توانید جدول اعداد اول تا 997 را دانلود کنید.

اما بسیاری از اعداد طبیعی به طور مساوی بر سایر اعداد طبیعی بخش پذیرند.

مثلا:

• عدد 12 بر 1، بر 2، بر 3، بر 4، بر 6، بر 12 بخش پذیر است.
• 36 بر 1، بر 2، بر 3، بر 4، بر 6، بر 12، بر 18، بر 36 بخش پذیر است.

اعدادی که عدد بر آنها به طور مساوی بخش پذیر است (برای 12 اینها 1، 2، 3، 4، 6 و 12 هستند) مقسوم علیه اعداد نامیده می شوند.

یاد آوردن!

مقسوم علیه یک عدد طبیعی a عددی طبیعی است که عدد داده شده "a" را بدون باقیمانده تقسیم می کند.

عدد طبیعی که بیش از دو عامل داشته باشد، عدد مرکب نامیده می شود.

توجه داشته باشید که اعداد 12 و 36 مقسوم علیه مشترک دارند. اینها اعداد هستند: 1، 2، 3، 4، 6، 12. بزرگترین مقسوم علیه این اعداد 12 است.

مقسوم علیه مشترک دو عدد داده شده "الف" و "ب" عددی است که هر دو عدد "الف" و "ب" بدون باقی مانده بر آن تقسیم می شوند.

یاد آوردن!

بزرگترین مقسوم علیه مشترک(GCD) از دو عدد داده شده "a" و "b" - این بزرگترین عددی است که هر دو اعداد "a" و "b" بدون باقی مانده بر آن تقسیم می شوند.

به طور خلاصه بزرگترین مقسوم علیه مشترک اعداد "الف" و "ب" به صورت زیر نوشته می شود:

gcd (الف؛ ب) .

مثال: gcd (12; 36) = 12.

مقسوم علیه اعداد در رکورد حل با حرف بزرگ "D" نشان داده می شود.

D(7) = (1، 7)

D(9) = (1، 9)

gcd (7؛ 9) = 1

اعداد 7 و 9 فقط یک مقسوم علیه مشترک دارند - عدد 1. چنین اعدادی نامیده می شوند اعداد همزمان اول.

یاد آوردن!

اعداد همزمان اولاعداد طبیعی هستند که فقط یک مقسوم علیه مشترک دارند - عدد 1. GCD آنها 1 است.

چگونه بزرگترین مقسوم علیه مشترک را پیدا کنیم

برای پیدا کردن gcd دو یا چند عدد طبیعی نیاز دارید:

1. تقسیم کننده های اعداد را به ضرایب اول تجزیه کنید.

محاسبات به راحتی با استفاده از یک نوار عمودی نوشته می شوند. در سمت چپ خط، ابتدا سود سهام را یادداشت کنید، در سمت راست - تقسیم کننده. در ادامه در ستون سمت چپ مقادیر private را یادداشت می کنیم.

بیایید بلافاصله با یک مثال توضیح دهیم. بیایید اعداد 28 و 64 را به فاکتورهای اول فاکتور کنیم.

1. زیر عوامل اول یکسان در هر دو عدد خط بکشید.
   28 = 2 2 7

   64 = 2 2 2 2 2 2

2. حاصل ضرب عوامل اول یکسان را پیدا کرده و پاسخ را یادداشت می کنیم.
   GCD (28؛ 64) = 2 2 = 4

   پاسخ: GCD (28؛ 64) = 4

می توانید مکان GCD را به دو روش ترتیب دهید: در یک ستون (همانطور که در بالا انجام شد) یا "در یک خط".

حال و در ادامه، حداقل یکی از این اعداد با صفر متفاوت است. اگر همه اعداد داده شده برابر با صفر باشند، مقسوم علیه مشترک آنها هر عدد صحیحی است و از آنجایی که تعداد بی نهایت اعداد صحیح وجود دارد، نمی توانیم در مورد بزرگترین آنها صحبت کنیم. بنابراین نمی توان از بزرگترین مقسوم علیه مشترک اعداد که هر کدام برابر با صفر است صحبت کرد.

حالا می توانیم بدهیم پیدا کردن بزرگترین مقسوم علیه مشترکدو عدد

تعریف.

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

مخفف GCD اغلب برای کوتاه کردن بزرگترین مقسوم علیه مشترک - Greatest Common Divisor استفاده می شود. همچنین بزرگترین مقسوم علیه مشترک دو عدد a و b اغلب با gcd(a,b) نشان داده می شود.

بیاوریم مثال بزرگترین مقسوم علیه مشترک (gcd).دو عدد صحیح بزرگترین مقسوم علیه 6 و −15 3 است. بیایید این را ثابت کنیم. بیایید تمام مقسوم علیه های عدد شش را بنویسیم: ± 6، ± 3، ± 1، و مقسوم علیه های عدد −15 اعداد 15±، 5±، 3± و 1± هستند. اکنون می توانید تمام مقسوم علیه های مشترک اعداد 6 و −15 را پیدا کنید، این اعداد −3، −1، 1 و 3 هستند. از 3-<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .

تعریف بزرگترین مقسوم علیه مشترک سه یا چند اعداد صحیح مشابه تعریف gcd از دو عدد است.

تعریف.

بزرگترین مقسوم علیه مشترکسه یا چند عدد صحیح بزرگترین عدد صحیحی است که به طور همزمان همه اعداد داده شده را تقسیم می کند.

بزرگترین مقسوم علیه مشترک n عدد صحیح a 1 , a 2 , …, a n را با gcd (a 1 , a 2 , …, a n) نشان خواهیم داد. اگر مقدار b بزرگترین مقسوم علیه مشترک این اعداد پیدا شود، می توانیم بنویسیم GCD(a 1 , a 2 ,…, a n)=b.

به عنوان مثال، با توجه به gcd چهار عدد صحیح −8، 52، 16 و −12، برابر با 4 است، یعنی gcd(−8, 52, 16, −12)=4. این را می توان با نوشتن تمام مقسوم علیه اعداد داده شده، انتخاب مقسوم علیه مشترک از آنها و تعیین بزرگترین مقسوم علیه مشترک بررسی کرد.

توجه داشته باشید که بزرگترین مقسوم علیه مشترک اعداد صحیح می تواند برابر با یکی از این اعداد باشد. این عبارت در صورتی درست است که همه اعداد داده شده بر یکی از آنها بخش پذیر باشند (اثبات در پاراگراف بعدی این مقاله آورده شده است). برای مثال، gcd(15، 60، -45)=15. این درست است زیرا 15 تقسیم کننده 15، 60 و −45 است و هیچ مقسوم علیه مشترکی برای 15، 60 و −45 وجود ندارد که بزرگتر از 15 باشد.

به‌اصطلاح اعداد نسبتاً اول، - چنین اعداد صحیحی که بزرگترین مقسوم‌گیرنده مشترک آن‌ها برابر با یک است، جالب توجه هستند.

بزرگترین خصوصیات مقسوم علیه، الگوریتم اقلیدس

بزرگترین مقسوم علیه مشترک تعدادی نتایج مشخص دارد، به عبارت دیگر، تعدادی ویژگی. اکنون موارد اصلی را فهرست می کنیم ویژگی های بزرگترین مقسوم علیه مشترک (gcd)، آنها را در قالب قضایا تنظیم می کنیم و بلافاصله برهان می دهیم.

ما تمام خصوصیات بزرگترین مقسوم علیه مشترک را برای اعداد صحیح مثبت فرموله می کنیم، در حالی که فقط مقسوم علیه های مثبت این اعداد را در نظر می گیریم.

بزرگترین مقسوم علیه مشترک a و b برابر است با بزرگترین مقسوم علیه مشترک b و a، یعنی gcd(a, b)=gcd(a, b).

این ویژگی GCD مستقیماً از تعریف بزرگترین مقسوم‌کننده مشترک پیروی می‌کند.

اگر a بر b بخش پذیر باشد، آنگاه مجموعه مقسوم علیه های مشترک a و b با مجموعه مقسوم علیه های b، به ویژه gcd(a, b)=b یکسان است.

اثبات

هر مقسوم علیه مشترک اعداد a و b مقسوم علیه هر یک از این اعداد از جمله عدد b است. از طرف دیگر، از آنجایی که a مضرب b است، پس هر مقسوم علیه عدد b نیز مقسوم علیه عدد a است، زیرا بخش پذیری دارای خاصیت گذر است، بنابراین، هر مقسوم علیه عدد b، a است. مقسوم علیه مشترک اعداد a و b این ثابت می کند که اگر a بر b بخش پذیر باشد، مجموعه مقسوم علیه های اعداد a و b با مجموعه مقسوم علیه های یک عدد b منطبق است. و چون بزرگترین مقسوم علیه عدد b خود عدد b است پس بزرگترین مقسوم علیه مشترک اعداد a و b نیز برابر b یعنی gcd(a, b)=b است.

به طور خاص، اگر اعداد a و b مساوی باشند، پس gcd(a, b)=gcd(a,a)=gcd(b,b)=a=b. برای مثال، gcd(132, 132)=132.

بزرگترین خاصیت مقسوم‌کننده به ما اجازه می‌دهد که gcd دو عدد را زمانی که یکی از آنها بر دیگری بخش‌پذیر است، پیدا کنیم. در این حالت GCD برابر با یکی از این اعداد است که عدد دیگری بر آن بخش پذیر است. به عنوان مثال، gcd(8, 24)=8 زیرا 24 مضرب هشت است.

اگر a=b q+c، که در آن a، b، c و q اعداد صحیح هستند، مجموعه مقسوم علیه های مشترک اعداد a و b با مجموعه مقسوم علیه های مشترک اعداد b و c، به ویژه gcd منطبق است. a, b)=gcd (b, c) .

اجازه دهید این ویژگی GCD را توجیه کنیم.

از آنجایی که تساوی a=b·q+c برقرار است، پس هر مقسوم علیه مشترک اعداد a و b نیز c را تقسیم می کند (این از ویژگی های بخش پذیری نتیجه می شود). به همین دلیل، هر مقسوم علیه مشترک b و c، a را تقسیم می کند. بنابراین مجموعه مقسوم علیه های مشترک اعداد a و b با مجموعه مقسوم علیه های مشترک اعداد b و c یکی است. به طور خاص، بزرگترین این مقسوم‌کننده‌های مشترک نیز باید مطابقت داشته باشد، یعنی تساوی زیر باید gcd(a, b)=gcd(b, c) درست باشد.

حال یک قضیه را فرموله و اثبات می کنیم که این است الگوریتم اقلیدس. الگوریتم اقلیدس به شما امکان می دهد GCD دو عدد را پیدا کنید (به یافتن GCD با استفاده از الگوریتم اقلیدس مراجعه کنید). علاوه بر این، الگوریتم اقلیدس به ما اجازه می‌دهد تا ویژگی‌های زیر را از بزرگترین مقسوم‌گیرنده مشترک ثابت کنیم.

قبل از بیان قضیه، توصیه می‌کنیم حافظه قضیه را از بخش تئوری تجدید کنید، که بیان می‌کند که سود سهام a را می‌توان به صورت b q + r نشان داد، جایی که b یک مقسوم‌کننده است، q عددی صحیح به نام ضریب جزئی است. و r یک عدد صحیح است که شرط را برآورده می کند که باقی مانده نامیده می شود.

بنابراین، اجازه دهید برای دو عدد صحیح غیر صفر مثبت a و b، یک سری تساوی درست است

به پایان می رسد که rk + 1 = 0 (که اجتناب ناپذیر است، زیرا b>r 1 >r 2 >r 3 , ... یک سری اعداد صحیح کاهشی است، و این سری نمی تواند بیش از تعداد متناهی اعداد مثبت داشته باشد)، پس r k – بزرگترین مقسوم علیه a و b است، یعنی r k =gcd(a, b).

اثبات

اجازه دهید ابتدا ثابت کنیم r k مقسوم علیه مشترک اعداد a و b است، پس از آن نشان خواهیم داد که r k فقط یک مقسوم علیه نیست، بلکه بزرگترین مقسوم علیه مشترک اعداد a و b است.

در امتداد برابری های نوشته شده از پایین به بالا حرکت خواهیم کرد. از آخرین تساوی، می توان گفت که rk-1 بر r k بخش پذیر است. با توجه به این واقعیت، و همچنین ویژگی GCD قبلی، تساوی ماقبل آخر rk-2 =rk-1 qk +rk به ما امکان می دهد ادعا کنیم که rk-2 بر rk بخش پذیر است، زیرا rk-1 بر rk بخش پذیر است و rk قابل بخش است. توسط r k. بر اساس قیاس، از برابری سوم از پایین نتیجه می گیریم که rk-3 بر r k بخش پذیر است. و غیره. از تساوی دوم نتیجه می گیریم که b بر r k بخش پذیر است و از تساوی اول می گیریم که a بر r k بخش پذیر است. بنابراین r k مقسوم علیه مشترک a و b است.

باقی مانده است که ثابت کنیم r k =gcd(a, b) . برای نشان دادن اینکه هر مقسوم علیه مشترک اعداد a و b (آن را با r 0 نشان می دهیم) کافی است r k را تقسیم کند.

ما در امتداد برابری های اولیه از بالا به پایین حرکت خواهیم کرد. با توجه به ویژگی قبلی، از تساوی اول نتیجه می شود که r 1 بر r 0 بخش پذیر است. سپس از تساوی دوم دریافت می کنیم که r 2 بر r 0 بخش پذیر است. و غیره. از آخرین تساوی دریافتیم که r k بر r 0 بخش پذیر است. بنابراین r k =gcd(a,b).

از خاصیت در نظر گرفته شده بزرگترین مقسوم علیه مشترک چنین بر می آید که مجموعه مقسوم علیه های مشترک اعداد a و b با مجموعه مقسوم علیه های بزرگترین مقسوم علیه مشترک این اعداد منطبق است. این نتیجه از الگوریتم اقلیدس به ما اجازه می دهد تا همه مقسوم علیه های مشترک دو عدد را به عنوان مقسوم علیه gcd این اعداد پیدا کنیم.

فرض کنید a و b اعداد صحیحی باشند که به طور همزمان برابر با صفر نباشند، پس اعداد صحیح u 0 و v 0 وجود دارند، پس برابری gcd(a, b)=a u 0 +b v 0 معتبر است. آخرین تساوی یک نمایش خطی از بزرگترین مقسوم علیه مشترک اعداد a و b است، این تساوی را نسبت Bezout می نامند و اعداد u 0 و v 0 ضرایب Bezout هستند.

اثبات

با توجه به الگوریتم اقلیدس می توانیم برابری های زیر را بنویسیم



از تساوی اول داریم r 1 =a−b q 1 و با نشان دادن 1=s 1 و −q 1 =t 1 , این تساوی به شکل r 1 =s 1 a+t 1 b و اعداد s 1 می باشد. و t 1 اعداد صحیح هستند. سپس از برابری دوم r 2 =b−r 1 q 2 = بدست می آوریم b−(s 1 a+t 1 b) q 2 =−s 1 q 2 a+(1−t 1 q 2) b. با نشان دادن −s 1 q 2 =s 2 و 1−t 1 q 2 =t 2، آخرین تساوی را می توان به صورت r 2 =s 2 a+t 2 b نوشت و s 2 و t 2 اعداد صحیح هستند (زیرا مجموع ، تفاوت و حاصل ضرب اعداد صحیح یک عدد صحیح است). به همین ترتیب، از تساوی سوم، r 3 =s 3 ·a+t 3 ·b، از تساوی چهارم r 4 =s 4 ·a+t 4 ·b و به همین ترتیب به دست می آوریم. در نهایت، r k =s k ·a+t k ·b، که در آن s k و t k اعداد صحیح هستند. از آنجایی که r k =gcd(a,b) و نشان دهنده s k =u 0 و t k =v 0 است، یک نمایش خطی از gcd به شکل مورد نیاز بدست می آوریم: gcd(a, b)=a u 0 +b v 0.

اگر m هر عدد طبیعی باشد، پس gcd(m a, m b)=m gcd(a, b).

دلیل این خاصیت بزرگترین مقسوم علیه مشترک به شرح زیر است. اگر دو طرف هر یک از تساوی های الگوریتم اقلیدس را در m ضرب کنیم، به دست می آوریم که gcd(m a, m b)=m r k و r k gcd(a, b) است. در نتیجه، gcd(m a, m b)=m gcd(a, b).

این خاصیت بزرگترین مقسوم علیه مشترک مبنایی برای روش یافتن GCD با استفاده از فاکتورسازی اول است.

فرض کنید p هر مقسوم علیه مشترک اعداد a و b باشد، پس gcd(a:p، b:p)=gcd(a، b):p، به ویژه، اگر p=gcd(a, b) داشته باشیم gcd(a:gcd(a, b), b:gcd(a, b))=1یعنی اعداد a:gcd(a,b) و b:gcd(a,b) هم اول هستند.

از آنجایی که a=p (a:p) و b=p (b:p) و با توجه به خاصیت قبلی، می‌توانیم زنجیره‌ای از برابری‌های شکل بنویسیم. gcd(a, b)=gcd(p (a:p)، p (b:p))= p·gcd(a:p، b:p) ، که از آنجا برابری که باید ثابت شود به شرح زیر است.

بزرگترین خاصیت تقسیم کننده مشترک که به تازگی ثابت شده است زیربنای آن است.

حال بیایید ویژگی GCD را صدا کنیم، که مشکل یافتن بزرگترین مقسوم‌عام مشترک سه یا چند عدد را به یافتن متوالی GCD دو عدد کاهش می‌دهد.

بزرگترین مقسوم علیه مشترک اعداد a 1 , a 2 , ..., a k برابر است با عدد d k که در محاسبه ترتیبی GCD(a 1, a 2)=d 2 , GCD(d 2 , a یافت می شود. 3)=d 3، GCD(d 3، a 4)=d 4، …، GCD(d k-1، a k)=d k.

این اثبات بر اساس نتیجه ای از الگوریتم اقلیدس است. مقسوم علیه های مشترک اعداد a 1 و a 2 با مقسوم علیه های d 2 یکسان است. سپس مقسوم علیه های مشترک اعداد a 1، a 2 و a 3 با مقسوم علیه های مشترک اعداد d 2 و a 3 منطبق می شوند، بنابراین با مقسوم علیه های d 3 منطبق می شوند. مقسوم علیه های مشترک اعداد a 1 , a 2 , a 3 و a 4 با مقسوم علیه های مشترک d 3 و a 4 یکی هستند، از این رو با مقسوم علیه های d 4 یکسان هستند. و غیره. در نهایت، مقسوم علیه های مشترک اعداد a 1 , a 2 , …, a k با مقسوم علیه های d k منطبق است. و چون بزرگترین مقسوم علیه عدد d k خود عدد d k است، پس GCD(a 1 , a 2 , …, a k)=d k.

این بررسی ویژگی های اصلی بزرگترین مقسوم علیه مشترک را به پایان می رساند.

کتابشناسی - فهرست کتب.

• ویلنکین N.Ya. و غیره ریاضی. کلاس ششم: کتاب درسی برای مؤسسات آموزشی.
• وینوگرادوف I.M. مبانی نظریه اعداد.
• میخلوویچ ش.خ. نظریه اعداد
• کولیکوف ال.یا. مجموعه مسائل جبر و تئوری اعداد: کتاب درسی دانش آموزان رشته فیس. تخصص های موسسات آموزشی.