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

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

بیایید بزرگترین مقسوم علیه اعداد 24 و 35 را پیدا کنیم.
مقسوم علیه های 24 اعداد 1، 2، 3، 4، 6، 8، 12، 24 و مقسوم علیه های 35 اعداد 1، 5، 7، 35 خواهند بود.
می بینیم که اعداد 24 و 35 فقط یک مقسوم علیه مشترک دارند - عدد 1. چنین اعدادی نامیده می شوند. coprime.

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

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

با فاکتور گیری اعداد 48 و 36 به دست می آید:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
از عواملی که در بسط اعداد اول گنجانده شده است، مواردی را که در بسط عدد دوم گنجانده نشده اند (یعنی دو دس) حذف می کنیم.
ضرایب 2 * 2 * 3 باقی می مانند. حاصلضرب آنها 12 است. این عدد بزرگترین مقسوم علیه مشترک اعداد 48 و 36 است. بزرگترین مقسوم علیه مشترک سه عدد یا بیشتر نیز یافت می شود.

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

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

اگر همه اعداد داده شده بر یکی از آنها بخش پذیر باشند، این عدد است بزرگترین مقسوم علیه مشترکاعداد داده شده
به عنوان مثال، بزرگترین مقسوم علیه مشترک 15، 45، 75 و 180، 15 است، زیرا همه اعداد دیگر را تقسیم می کند: 45، 75، و 180.

کمترین مضرب مشترک (LCM)

تعریف. کمترین مضرب مشترک (LCM)اعداد طبیعی a و b کوچکترین عدد طبیعی است که مضرب هر دو a و b است. کمترین مضرب مشترک (LCM) اعداد 75 و 60 را می توان بدون نوشتن مضرب این اعداد در یک ردیف پیدا کرد. برای انجام این کار ، 75 و 60 را به عوامل ساده تجزیه می کنیم: 75 \u003d 3 * 5 * 5 و 60 \u003d 2 * 2 * 3 * 5.
فاکتورهای موجود در بسط اعداد اول را می نویسیم و فاکتورهای گمشده 2 و 2 را از بسط عدد دوم به آنها اضافه می کنیم (یعنی عوامل را با هم ترکیب می کنیم).
پنج عامل 2 * 2 * 3 * 5 * 5 بدست می آوریم که حاصل ضرب آنها 300 می شود. این عدد کمترین مضرب مشترک اعداد 75 و 60 است.

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

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

توجه داشته باشید که اگر یکی از این اعداد بر همه اعداد دیگر بخش پذیر باشد، این عدد کمترین مضرب مشترک این اعداد است.
برای مثال، کمترین مضرب مشترک 12، 15، 20 و 60 60 خواهد بود، زیرا بر همه اعداد داده شده بخش پذیر است.

فیثاغورث (قرن ششم قبل از میلاد) و شاگردانش موضوع تقسیم پذیری اعداد را مطالعه کردند. عددی برابر مجموع همه مقسوم علیه های آن (بدون خود عدد) عدد کامل را می گفتند. به عنوان مثال، اعداد 6 (6 = 1 + 2 + 3)، 28 (28 = 1 + 2 + 4 + 7 + 14) کامل هستند. اعداد کامل بعدی 496، 8128، 33،550،336 هستند. فیثاغورثی ها فقط سه عدد کامل اول را می دانستند. چهارم - 8128 - در قرن اول شناخته شد. n ه. پنجم - 33 550 336 - در قرن 15 یافت شد. تا سال 1983، 27 عدد کامل از قبل شناخته شده بود. اما تا به حال، دانشمندان نمی دانند که آیا اعداد کامل فرد وجود دارد یا خیر، آیا بزرگترین عدد کامل وجود دارد یا خیر.
علاقه ریاضیدانان باستانی به اعداد اول به این دلیل است که هر عددی یا اول است یا می توان آن را به عنوان حاصلضرب اعداد اول نشان داد، یعنی اعداد اول مانند آجرهایی هستند که بقیه اعداد طبیعی از آن ساخته شده اند.
احتمالاً متوجه شده اید که اعداد اول در سری اعداد طبیعی به طور ناهموار رخ می دهند - در برخی از قسمت های سری تعداد آنها بیشتر است، در برخی دیگر - کمتر. اما هر چه بیشتر در امتداد سری اعداد حرکت کنیم، اعداد اول نادرتر می شوند. این سوال مطرح می شود: آیا آخرین (بزرگترین) عدد اول وجود دارد؟ ریاضیدان یونانی باستان اقلیدس (قرن سوم قبل از میلاد) در کتاب خود "آغاز" که برای دو هزار سال کتاب اصلی ریاضیات بود، ثابت کرد که بی نهایت اعداد اول وجود دارد، یعنی پشت هر عدد اول یک عدد زوج وجود دارد. عدد اول بزرگتر
برای یافتن اعداد اول، یکی دیگر از ریاضیدانان یونانی در همان زمان، اراتوستنس، چنین روشی را ارائه کرد. او همه اعداد را از 1 تا فلان عدد یادداشت کرد و سپس واحد را که نه عدد اول است و نه ترکیبی خط کشید، سپس تمام اعداد بعد از 2 را از طریق یک خط زد (اعدادی که مضرب 2 هستند، یعنی 4، 6، 8، و غیره). اولین عدد باقیمانده بعد از 2، 3 بود. سپس، پس از دو، تمام اعداد بعد از 3 خط زده شدند (اعدادی که مضرب 3 هستند، یعنی 6، 9، 12 و غیره). در پایان، فقط اعداد اول بدون خط باقی ماندند.

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

2. همه عوامل اول مشترک را در بسط های به دست آمده بیابید (زیر خط بکشید).

3. حاصل ضرب عوامل اول مشترک را بیابید.

برای پیدا کردن LCM (کمترین مضرب مشترک) دو عدد، شما نیاز دارید:

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

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

3. حاصل ضرب عوامل به دست آمده را محاسبه کنید.

پیدا کردن GCD

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

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

• عوامل مشترک هر دو عدد را تعیین کنید.
• محصول عوامل مشترک را بیابید.

نمونه ای از یافتن GCD:

GCD اعداد 315 و 245 را پیدا کنید.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

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

3. حاصل ضرب عوامل مشترک را بیابید:

gcd(315; 245) = 5 * 7 = 35.

پاسخ: GCD(315; 245) = 35.

پیدا کردن NOC

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

برای پیدا کردن کوچکترین مضرب مشترک چند عدد:

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

نمونه ای از یافتن NOC:

LCM اعداد 236 و 328 را پیدا کنید:

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

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

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

2; 2; 59; 2; 41.

3. حاصل ضرب عوامل حاصل را بیابید:

LCM(236؛ 328) = 2 * 2 * 59 * 2 * 41 = 19352.

پاسخ: LCM(236؛ 328) = 19352.

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

NOD چیست؟

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

چگونه NOD را پیدا کنیم؟

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

آنها فرمول خاصی برای این کار ارائه نکردند، اما یک الگوریتم محاسبه وجود دارد.

بیایید مثالی از پیدا کردن بزرگترین مقسوم علیه دو عدد طبیعی بزنیم: 540 و 252. بیایید 640 را به ضرایب اول تجزیه کنیم. ترتیب اقدامات به شرح زیر است:

• عدد را بر کوچکترین عدد اول ممکن تقسیم می کنیم. یعنی اگر بتوان عدد را بر 2، 3 یا 5 تقسیم کرد، ابتدا باید بر 5 تقسیم کرد. فقط برای اینکه گیج نشوید.
• نتیجه حاصل بر کوچکترین عدد اول ممکن تقسیم می شود.
• تقسیم هر نتیجه به دست آمده را آنقدر تکرار می کنیم تا یک عدد اول بدست آوریم.

حالا ما همین رویه را در عمل انجام خواهیم داد.

• 540: 2=270
• 270:2=135
• 135: 3 =45
• 45: 3=15
• 15: 5 = 3

بیایید نتیجه را به صورت معادله بنویسیم 540=2*2*3*3*3*5. برای نوشتن نتیجه، باید آخرین عدد حاصل را در همه مقسوم‌گیرنده‌ها ضرب کنید.

بیایید همین کار را با عدد 252 انجام دهیم:

• 252: 2=126
• 126: 2=63
• 63: 3=21
• 21: 3 = 7

بیایید نتیجه را یادداشت کنیم: 252=2*2*3*3*7.

هر بسط اعداد یکسانی دارد. بیایید آنها را پیدا کنیم، اینها دو عدد 2 و دو عدد 3 هستند. فقط 7 و 3 * 5 متفاوت هستند.

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

GCD=2*2*3*3=36

چطو میتواند استفاده شود؟

وظیفه: کسری $252\over540$$ را کاهش دهید.

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

صورت و مخرج کسر را 36 کم می کنیم و جواب می گیریم.

$$(252\over540) =(7\over15)$$ - برای کاهش سریع، فقط به گسترش اعداد نگاه کنید.

اگر 540=2*2*3*3*3*5 و GCD=36=2*2*3*3، 540 = 36*3*5. و اگر 540 را بر 36 تقسیم کنیم 3*5=15 به دست می آید.

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

ما چه آموخته ایم؟

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

مسابقه موضوع

رتبه بندی مقاله

میانگین امتیاز: 4.3. مجموع امتیازهای دریافتی: 204.

یکی از کارهایی که برای دانش‌آموزان مدرن که عادت به استفاده از ماشین‌حساب‌های تعبیه‌شده در گجت‌ها در جای خود دارند، مشکل ایجاد می‌کند، یافتن بزرگترین مقسوم‌کننده مشترک (GCD) دو یا چند عدد است.

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

مفاهیم و تعاریف کلی

نیاز به دانستن:

1. اگر بتوان از عدد معینی برای شمردن اشیاء مختلف استفاده کرد، مثلاً نه ستون، شانزده خانه، طبیعی است. کوچکترین آنها یکی خواهد بود.
2. وقتی یک عدد طبیعی بر یک عدد طبیعی دیگر بخش پذیر باشد، عدد کوچکتر مقسوم علیه بزرگتر است.
3. اگر دو یا چند عدد مختلف بر یک عدد معین بدون باقیمانده بخش پذیر باشند، می گویند که دومی مقسوم علیه مشترک آنها (OD) خواهد بود.
4. بزرگ ترین OD ها بزرگترین مقسوم علیه مشترک (GCD) نامیده می شود.
5. در چنین حالتی وقتی عددی فقط دو مقسوم علیه طبیعی (خود و یک) داشته باشد، عدد اول نامیده می شود. کوچکترین در میان آنها دوس است، علاوه بر این، این تنها عدد زوج در سری آنها است.
6. اگر دو عدد دارای حداکثر مقسوم علیه مشترک یک باشند، آن‌ها هم اول خواهند بود.
7. عددی که بیش از دو مقسوم علیه داشته باشد، عدد مرکب نامیده می شود.
8. فرآیندی که همه عوامل اول پیدا می‌شوند، که با ضرب در یکدیگر، مقدار اولیه حاصل در ریاضیات را به دست می‌دهند، تجزیه به عوامل اول نامیده می‌شود. علاوه بر این، عوامل مشابه در گسترش می تواند بیش از یک بار رخ دهد.

در ریاضیات، نمادهای زیر پذیرفته می شوند:

1. مقسوم علیه D (45) = (1؛ 3؛ 5؛ 9؛ 45).
2. OD (8;18) = (1;2).
3. GCD (8; 18) = 2.

راه های مختلف برای یافتن GCD

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

به عنوان مثال، GCD (15;45) = 15، GCD (48;24) = 24.

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

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

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

مثال 1

نحوه یافتن GCD 36 و 90 را در نظر بگیرید:

1. 36 = 1*2*2*3*3;
2. 90 = 1*2*3*3*5;

GCD (36;90) = 1*2*3*3 = 18.

حالا بیایید ببینیم چگونه همان را پیدا کنیم در صورت سه عددبرای مثال 54 را در نظر بگیرید. 162; 42.

ما قبلاً می دانیم که چگونه 36 را تجزیه کنیم، بیایید به بقیه بپردازیم:

1. 162 = 1*2*3*3*3*3;
2. 42 = 1*2*3*7;

بنابراین، GCD (36; 162; 42) = 1 * 2 * 3 = 6.

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

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

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

1. 36 / 2 ما به روند تقسیم خود ادامه خواهیم داد.
2. 18/2 بیشتر؛
3. 9/3 و دوباره؛
4. 3/3 اکنون کاملاً ابتدایی است.
5. 1 - نتیجه آماده است.

36 \u003d 2 * 2 * 3 * 3 مورد نظر.

راه اقلیدسی

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

بیایید مثالی از استفاده از این الگوریتم بزنیم:

بیایید سعی کنیم دریابیم کدام GCD برای 816 و 252:

1. 816 / 252 = 3 و باقیمانده 60 است. اکنون 252 را بر 60 تقسیم می کنیم.
2. 252 / 60 = 4 باقیمانده این بار 12 خواهد بود. بیایید روند دایره ای خود را ادامه دهیم، شصت را بر دوازده تقسیم کنیم.
3. 60 / 12 = 5. از آنجایی که این بار مابقی دریافت نکردیم، نتیجه را آماده کرده ایم، دوازده مقداری خواهد بود که به دنبال آن هستیم.

بنابراین، در پایان روند ما ما NOD دریافت کردیم (816;252) = 12.

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

ما قبلاً متوجه شده ایم که در صورت وجود دو عدد مختلف چه کاری انجام دهیم ، اکنون یاد خواهیم گرفت که در صورت وجود چگونه عمل کنیم. 3 یا بیشتر.

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

نتیجه

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

اگرچه هر دو روش کاملاً قابل قبول هستند، اما در یک مدرسه جامع روش اول بسیار رایج تر است.. این به دلیل این واقعیت است که هنگام مطالعه موضوع آموزشی بعدی - تعریف بزرگترین مضرب مشترک (LCM) به تجزیه به عوامل اول نیاز است. اما باز هم، شایان ذکر است - استفاده از الگوریتم اقلیدس به هیچ وجه نمی تواند اشتباه تلقی شود.

ویدیو

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

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

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

الگوریتم اقلیدس محاسبه بزرگترین مقسوم علیه مشترک دو عدد مثبت را آسان می کند. ما فرمول‌بندی‌ها و اثبات الگوریتم اقلیدس را در بخش Greatest Common Divisor: Determinant, Examples آورده‌ایم.

ماهیت الگوریتم این است که به طور مداوم تقسیم را با باقیمانده انجام دهد، که طی آن یک سری برابری های شکل به دست می آید:

a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

ما می توانیم تقسیم را در زمانی به پایان برسانیم rk + 1 = 0، که در آن r k = gcd (a، b).

مثال 1

64 و 48 .

راه حل

بیایید نماد را معرفی کنیم: a = 64 , b = 48.

بر اساس الگوریتم اقلیدس، تقسیم را انجام خواهیم داد 64 بر 48 .

ما 1 و بقیه 16 می گیریم. معلوم می شود که q 1 = 1، r 1 = 16.

مرحله دوم تقسیم است 48 در 16، ما 3 را دریافت می کنیم. به این معنا که q2 = 3، آ r 2 = 0.بنابراین، عدد 16 بزرگترین مقسوم علیه مشترک برای اعداد از شرط است.

پاسخ: gcd(64، 48) = 16.

مثال 2

GCD اعداد چیست؟ 111 و 432 ?

راه حل

تقسیم کنید 432 بر 111 . طبق الگوریتم اقلیدس، ما زنجیره برابری های 432 = 111 3 + 99، 111 = 99 1 + 12، 99 = 12 8 + 3، 12 = 3 4 را به دست می آوریم.

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

پاسخ: gcd (111، 432) = 3.

مثال 3

بزرگترین مقسوم علیه 661 و 113 را پیدا کنید.

راه حل

ما به ترتیب اعداد را تقسیم می کنیم و GCD را دریافت می کنیم (661 , 113) = 1 . این بدان معناست که 661 و 113 اعداد نسبتا اول هستند. اگر به جدول اعداد اول نگاه کنیم، می‌توانیم این را قبل از شروع محاسبات بفهمیم.

پاسخ: gcd(661، 113) = 1.

یافتن GCD با فاکتورگیری اعداد به فاکتورهای اولیه

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

مثال 4

اگر اعداد 220 و 600 را به ضرایب اول تجزیه کنیم، دو محصول بدست می آوریم: 220 = 2 2 5 11و 600 = 2 2 2 3 5 5. فاکتورهای مشترک در این دو محصول 2 , 2 و 5 خواهد بود . این به این معنی است که NOD (220، 600) = 2 2 5 = 20.

مثال 5

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

راه حل

همه عوامل اول اعداد را بیابید 72 و 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

فاکتورهای اول رایج برای دو عدد: 2، 2، 2 و 3. این به این معنی است که NOD (72، 96) = 2 2 2 3 = 24.

پاسخ: gcd(72، 96) = 24.

قاعده یافتن بزرگترین مقسوم علیه مشترک دو عدد بر اساس ویژگی های بزرگترین مقسوم علیه مشترک است که طبق آن gcd (m a 1 , m b 1) = m gcd (a 1 , b 1) که m هر عدد صحیح مثبت است. .

یافتن GCD از سه عدد یا بیشتر

صرف نظر از تعداد اعدادی که برای آنها باید GCD را پیدا کنیم، از الگوریتم مشابهی پیروی می کنیم که شامل یافتن GCD دو عدد متوالی است. این الگوریتم مبتنی بر کاربرد قضیه زیر است: GCD چند اعداد a 1 , a 2 , … , a kبرابر عدد است dk، که در محاسبه متوالی 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 .

مثال 6

بزرگترین مقسوم علیه چهار عدد 78، 294، 570 و 36 .

راه حل

بیایید نماد را معرفی کنیم: a 1 = 78، a 2 = 294، a 3 = 570، a 4 = 36.

بیایید با پیدا کردن GCD اعداد 78 و 294 شروع کنیم: d2= GCD (78 , 294) = 6 .

اکنون بیایید شروع به یافتن d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) کنیم. طبق الگوریتم اقلیدس 570 = 6 95 .این به آن معنا است d 3 = GCD (6 , 570) = 6 .

d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) را پیدا کنید. 36 بدون باقی مانده بر 6 بخش پذیر است. این به ما اجازه می دهد که به دست آوریم d4= GCD (6 , 36) = 6 .

d4 = 6، یعنی GCD (78 , 294 , 570 , 36) = 6 .

پاسخ:

و اکنون بیایید به روش دیگری برای محاسبه GCD برای آن و تعداد بیشتر نگاه کنیم. ما می‌توانیم gcd را با ضرب همه ضرایب اول مشترک اعداد پیدا کنیم.

مثال 7

gcd اعداد 78، 294، 570 و را محاسبه کنید 36 .

راه حل

بیایید این اعداد را به عوامل اول تجزیه کنیم: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .

برای هر چهار عدد، ضرایب اول مشترک اعداد 2 و 3 خواهند بود.

معلوم می شود که NOD (78، 294، 570، 36) = 2 3 = 6.

پاسخ: gcd(78، 294، 570، 36) = 6.

پیدا کردن gcd اعداد منفی

اگر باید با اعداد منفی سر و کار داشته باشیم، می توانیم از ماژول های این اعداد برای یافتن بزرگترین مقسوم علیه مشترک استفاده کنیم. ما می توانیم این کار را با دانستن خاصیت اعداد با علائم متضاد انجام دهیم: اعداد nو -nتقسیم کننده های یکسانی دارند

مثال 8

gcd اعداد صحیح منفی را پیدا کنید − 231 و − 140 .

راه حل

برای انجام محاسبات، اجازه دهید ماژول هایی از اعداد داده شده در شرط را در نظر بگیریم. اینها اعداد 231 و 140 خواهند بود. بگذارید به طور خلاصه بگوییم: GCD (− 231 , − 140) = GCD (231، 140). حالا بیایید الگوریتم اقلیدس را برای یافتن ضرایب اول دو عدد اعمال کنیم: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 و 42 = 7 6. ما دریافت می کنیم که gcd (231، 140) = 7 .

و از آنجایی که NOD (− 231 , − 140) = GCD (231 , 140) ، سپس gcd اعداد − 231 و − 140 برابر است 7 .

پاسخ: gcd (- 231، 140-) = 7.

مثال 9

gcd سه عدد - 585، 81 و را تعیین کنید − 189 .

راه حل

بیایید اعداد منفی در لیست بالا را با مقادیر مطلق آنها جایگزین کنیم، GCD دریافت می کنیم (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . سپس همه اعداد داده شده را به عوامل اول تجزیه می کنیم: 585 = 3 3 5 13، 81 = 3 3 3 3 و 189 = 3 3 3 7. فاکتورهای اول 3 و 3 در سه عدد مشترک هستند. معلوم می شود که gcd (585، 81، 189) = gcd (- 585، 81، - 189) = 9.

پاسخ: GCD (- 585، 81، 189-) = 9.

اگر متوجه اشتباهی در متن شدید، لطفاً آن را برجسته کرده و Ctrl+Enter را فشار دهید