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

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

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

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

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

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

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

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

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

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

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

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