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

بزرگترین مقسوم علیه مشترک (اختصاری {{{1}}}) (به انگلیسی: 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$

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

به کمک مجموعهٔ مقسوم‌علیه‌ها

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

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

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

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

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

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

منابع

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