الگوریتم اقلیدس

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

الگوریتم اقلیدس، روشی موسوم به روش نردبانی یا تقسیمات متوالی برای یافتن بزرگترین مقسوم علیه مشترک دو عدد است که در ادامه، با مثالی آن را شرح می‌دهیم.
مثال: برای محاسبهٔ (846 , 204) عدد بزرگتر یعنی 846 را بر 204 تقسیم می‌کنیم و سپس 204 را بر باقی ماندهٔ تقسیم مزبور تقسیم می‌کنیم و این عمل را تا جایی که باقی مانده صفر شود ادامه می‌دهیم، آخرین باقی‌مانده غیرصفر، بزرگترین مقسوم علیه مشترک دو عدد مزبور است. همچنین می‌توان این تقسیمات را در جدولی تنظیم نمود.

Euclidean Algorithm

بنابرین (846 , 204) = 6.

اثبات الگوریتم اقلیدس[ویرایش]

برای این که ثابت کنیم چرا با الگوریتم فوق ب.م. م به دست می‌آید به لم زیر توجه کنید:

لم: اگر a = bq + r آن‌گاه (a , b) = (b , r)

اثبات: فرض می‌کنیم (a,b) = d و (b,r) = d'. پس

Proof - Euclidean Algorithm.png

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

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