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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

مقدمه[ویرایش]

بزرگترین مقسوم علیه مشترک میان دو عدد طبیعی a \! و b \! بصورت (a, b) \! یا gcd(a, b) \! یا hcf(a, b) \! نوشته می‌شود.

مثال: gcd(16, 24) = 8 \! و gcd(8, 9) = 1 \!

هرگاه ب.م.م دو عدد برابر ۱ باشد، آن دو عدد را نسبت به‌هم اول می‌گوئیم(هم اول).

مثال: دو عدد ۱۴ و ۵ نسبت به هم اول هستند، زیرا، داریم gcd(5, 14) = 1 \!

ب.م.م برای ساده تر کردن کسرها نیز مفید است. برای مثال:

{54 \over 81}={2 \cdot 27 \over 3 \cdot 27}={2 \over 3} \!

محاسبه ب.م.م[ویرایش]

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

اصولاً می‌توان ب.م.م دو عدد را با تجزیه عددها به فاکتورهای اولشان پیدا کرد. برای مثال:

۲٫۳۲=۱۸ و ۳٫۷.۲۲=۸۴

مشاهده می کنید که فاکتورهای مشترک این دو عدد ۲ و ۳ هستند پس: gcd(۸۴٬۱۸) = ۲٫۳ = ۶

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

روش اقلیدسی (تقسیم متوالی)[ویرایش]

یکی از بهترین روش‌ها برای محاسبهٔ ب.م.م الگوریتم اقلیدس است که از الگوریتم تقسیم استفاده می‌کند.

مثال: یافتن (۸۴٬۱۸)gcd

ابتدا ۸۴ را به ۱۸ تقسیم می کنیم؛ خارج قسمت تقسیم ۴ و باقی‌مانده ۱۲ بدست می‌آید.

سپس ۱۸ را بر ۱۲ تقسیم می کنیم؛ خارج قسمت ۱ و باقی‌مانده ۶ بدست می‌آید؛ مجدداً ۱۲ را بر ۶ تقسیم می‌کنیم؛ خارج قسمت ۲ و باقی‌مانده ۰ می‌شود. پس عدد ۶ ب.م.م دو عدد ۸۴ و ۱۸ است.

در روش اقلیدسی اصطلاحاً خارج قسمت را بطور متوالی می شکنیم تا به باقی‌مانده ۰ برسیم.

خاصیت‌های ب.م.م[ویرایش]

  • هر مقسوم علیه دو عدد a و b، مقسوم علیه (gcd(a،b نیز هست.
  • ب.م.م دو عدد a و ۰ برابر |a| است. |gcd(a،۰)=|a.
  • اگر a مقسوم علیه b.c باشد و داشته باشیم gcd(a، b) = d آنگاه a/d مقسوم علیه c است.
  • اگر m یک عدد نامنفی باشد آنگاه داریم: (gcd(m·a، m·b) = m·gcd(a، b.
  • اگر m یک عدد صحیح باشد آنگاه داریم: (gcd(a + m·b، b) = gcd(a، b.
  • اگر m مقسوم علیه مشترک غیر صفر a و b باشد آنگاه داریم: gcd(a/m، b/m) = gcd(a، b)/m
  • ب.م.م دارای خاصیت جابجایی است؛ (gcd(a، b) = gcd(b، a
  • ب.م.م دارای خاصیت شرکت‌پذیری است؛ (gcd(a، gcd(b، c)) = gcd(gcd(a، b)، c
  • ب.م.م دو عدد a و b وقتی که هیچ کدام ۰ نباشند، تعریف می‌شود: کوچکترین عدد مثبت d بشکلی که بتوان به فرم d = a·p + b·q نوشت که در آن p و q اعداد صحیح هستند.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  • Aufmann, R. N., Barker, V. C., Lockwood, J. Basic College Mathematics: An Applied Approach, Houghton Mifflin Company, 2006. ISBN 0-618-50305-6

پیوند به بیرون[ویرایش]

عملیات دوتایی
عددی تابعی مجموعه‌ای ساختاری
مقدماتی

+ جمع
تفریق
× ضرب
÷ تقسیم
^ توان

حسابی

div خارج قسمت اقلیدسی
mod باقیمانده اقلیدسی
بزرگترین مقسوم علیه مشترک
کوچکترین مضرب مشترک

ترکیباتی

( ) ضریب بینم
A جایگشت

ترکیب
کانولوشن
جبر مجموعه‌ها

اجتماع
\ مجموعه مکمل
اشتراک
Δ تفاضل متقارن

ترتیب کلی

min کمینه
max بیشینه

توری‌ها

کرانه تحتانی
کرانه فوقانی

مجموعه‌ها

× ضرب دکارتی
اجتماع منفصل
^ توان مجموعه‌ای

گروه‌ها

حاصل‌جمع مستقیم
حاصل ضرب آزاد
produit en couronne

مدول‌ها

ضرب تانسوری
Hom هومومورفیزم
Tor پیچش
Ext extensions

درخت‌ها

enracinement

واریته‌های متصل

# جمع متصل

فضاهای نقطه‌دار

bouquet
smash produit
joint

برداری
(.) ضرب اسکالر
ضرب برداری
جبری
[,] کروشه لی
{,} کروشه پواسون
ضرب خارجی
هومولوژی
cup-produit
حاصل ضرب اشتراک
ترتیبی
+ الحاق
منطق بولی
عطف منطقی فصل منطقی یای انحصاری استلزام منطقی اگر و فقط اگر