خوارزمية إقليدس
خوارزمية إقليدس في نظرية الأعداد هي خوارزمية لحساب القاسم المشهجر الأكبر لعددين طبيعيين ، تظهر أهميتها الأساسية في عدم حاجتنا لتحليل الرقمين كي نتمكن من حساب القاسم المشهجر الأكبر لهما ، وتتميز بكونها إحدى أقدم الخوارزميات حيث ترجع إلى سنة 300 ق.م. .
وصف الخوارزمية
القاسم المشهجر الأكبر لعددين طبيعيين A ، B يساوي القاسم المشهجر الأكبر للعدد الثاني B وباقي قسمة A على B ، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر ، عندئذقد يكون القاسم المشهجر الأكبر هوالعدد الآخر.
حيث :
r باقي قسمة A على B
N هوالقاسم المشهجر الأكبر.
مثال
القاسم المشهجر الأكبر للعددين 252 و198 :
252 = 198 * 1 + 54 ‘ أربع وخمسون هوباقي قسمة 252 على 198
فنجد القاسم المشهجر للعددين 198 و54
198 = 54 * ثلاثة + 36 ‘ ست وثلاثون هوباقي القسمة.
نكرر العملية هذه المرة مع : 54 و36
54 = 36 * 1 + 18
مرة أخرى : 36 = 18 * 2 + 0
هنا وصلنا للصفر فيكون العدد الثاني 18 هوالقاسم المشهجر الأكبر.
