بزرگ‌ترین شمارندهٔ مشترک

بزرگترین شمارندهٔ مشترک دو عدد ۶۰ و ۴۸ از محاسبهٔ اشتراک مجموعه شمارنده‌های هر یک از این دو عدد با هم، و ضرب آن‌ها به دست می‌آید.یعنی بزرگترین شمارندهٔ مشترک این دو عدد عبارت است از: ۲×۲×۳ یا همان ۱۲.

بزرگترین شمارندهٔ مشترک یا بزرگترین مقسوم‌علیه مشترک (اختصاری ب.م.م) (به انگلیسی: Greatest Common Divisor (GCD)) در ریاضیات بزرگترین عضو مجموعهٔ شمارنده‌های دو عدد بزرگترین شمارندهٔ مشترک این دو عدد نامیده می‌شود.

مثال

فرض کنید $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$

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

به کمک مجموعهٔ شمارنده‌ها

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

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

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

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

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

جستارهای وابسته

• تست ب. م. م
• کوچک‌ترین مضرب مشترک

منابع

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