الگوریتم اقلیدس
From Wikipedia, the free encyclopedia
الگوریتم اقلیدس روشی موسوم به روش نردبانی یا تقسیمات متوالی برای یافتن بزرگترین مقسوم علیه مشترک (ب.م.م) دو عدد است.
بزرگترین مقسوم علیه مشترک دو عدد a و b را بهصورت نشان میدهند. برای محاسبه
عدد بزرگتر را بر عدد کوچکتر تقسیم می کنیم؛ اگر باقیمانده صفر بود، پس عدد کوچکتر همان ب.م.م دو عدد است؛ وگرنه عدد کوچکتر را بر باقیمانده تقسیم قبلی تقسیم میکنیم و این فرایند را تا جایی پیش میبریم تا به باقی مانده صفر برسیم.
مثال: برای محاسبهٔ عدد بزرگتر یعنی ۱۸ را بر ۱۲ تقسیم میکنیم و سپس ۱۲ را بر باقی ماندهٔ تقسیم قبل (باقیمانده ۱۸ تقسیم بر ۱۲ مساوی با ۶ است) تقسیم میکنیم. ۱۲ تقسیم بر ۶ باقیمانده صفر دارد؛ بنابراین
.