بزرگترین ماشین حسابِ عامل مشترک
قبل از پرداختن به تعریف مفهوم بزرگترین مقسوم علیه مشترک (GCD)، لازم است بدانیم که مقسوم علیه مشترک به طور کلی چیست.
مشخص است که یک عدد صحیح می تواند چندین مقسوم علیه داشته باشد. ما علاقه مند به دسترسی همزمان چندین عدد صحیح به آنها هستیم. ما مقسوم علیه مشترک چند اعداد صحیح را عددی در نظر می گیریم که می تواند برای هر عدد از سری مشخص شده به عنوان مقسوم علیه عمل کند.
به عنوان مثال، اعداد 8 و 12 دارای مقسومگیرندههای مشترک زیر هستند: 1 و 4. این را میتوان به راحتی با نوشتن عبارات ریاضی تأیید کرد: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.
لازم به ذکر است که هر عدد در ابتدا دارای حداقل دو مقسوم علیه مشترک است: هر عددی بدون باقیمانده بر خود بخش پذیر است و همچنین بر 1 بخش پذیر است.
تعیین بزرگترین مقسوم علیه مشترک
بزرگترین مقسوم علیه مشترک (GCD) دو عدد طبیعی بزرگترین اعداد طبیعی است که می توانیم دو عدد از اعداد خود را بر آن تقسیم کنیم. اگر مقدار بزرگترین مقسوم علیه مشترک دو عدد طبیعی 1 باشد، این اعداد را coprime می نامیم.
برای دو عدد a و b، بزرگترین مقسوم علیه مشترک عددی است که می توان a و b را بدون باقیمانده بر آن تقسیم کرد. این عبارت به صورت زیر نوشته شده است: gcd (a, b) = c.
روش دیگری برای نوشتن GCD: (a, b) = c. با این حال، در بیشتر موارد، اولین گزینه استفاده می شود.
بنابراین، برای مثال، اعداد 4 و 16 بزرگترین مقسوم علیه مشترک را برابر با 4 دارند. بیایید بنویسیم: gcd (4، 16) = 4.
بیایید توضیح دهیم که چگونه به این نتیجه رسیدیم:
- همه مقسوم علیه های عدد 4 را نوشتیم. به دست آوردیم: 4، 2، 1.
- بعد، همه مقسومکنندههای 16 را نقاشی کردیم. به دست آمد: 16، 8، 4، 2، 1.
- ما مقسومگیرندههایی را انتخاب کردیم که برای 4 و 16 مشترک هستند. به دست آوردیم: 4، 2، 1.
- از میان مقسومگیرندههای مشترک حاصل، بزرگترین مورد انتخاب شد. این 4 است.
- ما پاسخ را دریافت می کنیم: برای اعداد 4 و 16 GCD برابر 4 است.
به طور مشابه، می توانید GCD را برای سه یا چند عدد صحیح پیدا کنید. در این صورت، بزرگترین عدد صحیحی خواهد بود که می توانید تمام اعداد سری پیشنهادی را با آن تقسیم کنید.
بنابراین، برای مثال، بزرگترین مقسوم علیه اعداد صحیح 6، 12، 18، 42 عدد 6 خواهد بود، یعنی gcd (6، 12، 18، 42) = 6. پاسخ با استفاده از یک الگوریتم به دست آمد. مشابه آنچه در بالا توضیح داده شد - برای اعداد یک سری، همه مقسومگیرندهها به ترتیب نوشته میشوند و پس از آن بزرگترین آنها انتخاب میشوند.
ویژگی های GCD
بزرگترین مقسوم علیه مشترک دارای تعدادی ویژگی است که برای GCD اعداد صحیح مثبت با مقسوم علیه بزرگتر از صفر مرتبط خواهد بود.
ویژگی 1
از تغییر مکان اعداد، مقدار نهایی GCD تغییر نخواهد کرد. می توانید این عبارت را به این صورت بنویسید:
- gcd(a, b) = gcd(b, a).
ویژگی 2
اگر a بر b بخش پذیر باشد، مجموعه مقسوم علیه های مشترک a و b با مجموعه مقسوم علیه های b یکی است. اینطور نوشته شده:
- gcd(a, b) = b.
از خاصیت اثبات شده بزرگترین مقسوم علیه می توان برای یافتن gcd دو عدد زمانی که یکی از آنها بر دیگری بخش پذیر است استفاده کرد. در این حالت، GCD برابر با یکی از این اعداد است که عدد دیگری بر آن بخش پذیر است.
به عنوان مثال:
- gcd(12، 4) = 4.
مشابه:
- gcd(10, 1) = 1.
ویژگی 3
اگر a = bq + c، که در آن a، b، c و q اعداد صحیح هستند، مجموعه مقسوم علیه های مشترک a و b با مجموعه مقسوم علیه های مشترک b و c یکسان است.
برابری gcd (a, b) = gcd (b, c) معتبر میشود.
ویژگی 4
عبارت gcd(ma, mb) = m ⋅ gcd(a, b) درست است به شرطی که m هر عدد طبیعی باشد.
ویژگی 5
فرض کنید 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) همزمان هستند.
ویژگی 6
هر دو عدد حداقل یک مقسوم علیه مشترک دارند - این عدد 1 است.
آگاهی از مبانی نظری مفهوم GCD و همچنین مهارت های عملی در تعریف آن برای کار با کسرهای معمولی ضروری است. علاوه بر این، GCD ارتباط نزدیکی با واحد ریاضی دیگری دارد - کمترین تقسیم کننده رایج. هر دو تعریف معمولاً به عنوان بخشی از برنامه درسی استاندارد مدرسه مورد مطالعه قرار می گیرند.