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

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

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

بزرگترین عضو مجموعهٔ شمارنده‌های دو عدد را بزرگترین مقسوم‌علیه مشترک این دو عدد می‌نامیم.
فرض کنید a و b دو عدد صحیح دلخواهند. اگر D(a) و D(b) به ترتیب مجموعهٔ مقسوم‌علیه‌های مثبت a و b باشند، آن‌گاه بزرگترین مقسوم علیه مشترک و که با نماد (a , b) نمایش داده می شود و به شکل زیر تعریف می‌شود.
بزرگترین عضو مجموعهٔ مقسوم‌علیه‌های مشترک و مثبت a و (a,b) = b .


  • اگر (a,b)=1، آن‌گاه a و b را نسبت به هم اول یا متباین می‌خوانیم.
  • (a,b)=(-a,b)=(a,-b)=(-a,-b)
  • (0,a)=|a|
  • چون D(0)={1,2,3,...}، پس مجموعهٔ مقسوم‌علیه‌های صفر و صفر مجموعهٔ اعداد طبیعی است که بزرگترین عضو ندارد، پس (0,0) تعریف نشده‌است. تذکر: برخی از مولفین تعریف می‌کنند (0,0)=0.
  • به ازای هر عدد صحیح k داریم: (a,b)=(a,ka+b).
  • قضیه بزو (Bezout): فرض کنید a و b دو عدد صحیحی هستند که حداقل یکی از آنها مخالف صفر است. اگر (a,b)=d، در این صورت، اعداد صحیح r و s وجود دارند به‌طوری‌که


d = ra + sb

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

به کمک مجموعهٔ مقسوم‌علیه‌ها[ویرایش]

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

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

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

الگوریتم اقلیدس ( موسوم به روش نردبانی یا تقسیمات متوالی )[ویرایش]

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

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

  • آشنایی با نظریهٔ اعداد، نوشتهٔ ویلیام و. آدامز، لری جوئل گولدشتین، ترجمهٔ آدینه محمد نارنجانی، مرکز نشر دانشگاهی
  • آموزش ریاضیات گسسته دورهٔ پیش‌دانشگاهی نظام جدید، نوشتهٔ سیدحسن سیدموسوی، انتشارات مبتکران