خوارزمية أقليدس

طريقة أقليدس لإيجاد القاسم المشترك الأكبر لعددين ابتُدأ بهما ممثلين بالقطعتين AB و CD, عُرفا كل منهما على أنهما مضاعفين لوحدة طول مشتركة. بما أن طول CD أقصر من AB، , استعمل لقياس AB, ولكنه قاسه مرة واحدة لأن الباقي EA أصغر قطعا من CD. الآن, EA تقيس (مرتين) الطول الأقصر DC, حيث الباقي FC أقصر من EA. إذن،FC تقيس (ثلاث مرات) الطولEA. لأنه لم يبق أي باق, تتوقف العملية مع كون FC القاسم المشترك الأكبر. في اليمين، مثال نيكوماكوس مع الأعداد 49 و 21 معطيا قاسمهما المشترك الأكبر مساويا لسبعة. (أُخذ من Heath 1908:300).

في نظرية الأعداد, خوارزمية إقليدس هي خوارزمية لحساب القاسم المشترك الأكبر لعددين طبيعيين، تظهر أهميتها الأساسية في عدم الحاجة لتحليل العددين للتمكن من حساب قاسمهما المشترك الأكبر. تتميز بكونها إحدى أقدم الخوارزميات حيث ترجع إلى سنة 300 ق.م.

مثال

القاسم المشترك الأكبر للعددين 252 و 198 :

252 = 198 * 1 + 54 ‘ أربع وخمسون هو باقي قسمة 252 على 198

فنجد القاسم المشترك للعددين 198 و 54

198 = 54 * 3 + 36 ‘ ست وثلاثون هو باقي القسمة.

نكرر العملية هذه المرة مع : 54 و 36

54 = 36 * 1 + 18

مرة أخرى : 36 = 18 * 2 + 0

هنا وصلنا للصفر فيكون العدد الثاني 18 هو القاسم المشترك الأكبر.

الخلفية

القاسم المشترك الأكبر

مقال تفصيلي :قاسم مشترك أكبر

وصف الخوارزمية

القاسم المشترك الأكبر لعددين طبيعيين A، B يساوي القاسم المشترك الأكبر للعدد الثاني B وباقي قسمة A على B، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر.

$\operatorname{GCD}(A,B) = \operatorname{GCD}(B,r) \cdots \cdots \operatorname{GCD}(N,0)$

حيث r هو باقي قسمة A على B.

N هو القاسم المشترك الأكبر.

التطور التاريخي

من المحتمل أن تكون الخوارزمية الإقليدية قد اكتشفت قرونا قبل إقليدس. بين هنا حاملا ل dividers

تطبيقات رياضياتية

الخوارزمية الإقليدية الممتدة

یمكن تمثیل القاسم المشترك الأكبر للعددین عن طریق دمج خطي مع عددین آخرین ، وذلك كالتالي GCD(x,y) = m*x + n*y كیف یمكن أیجاد قیمتي n و m وذلك عن طریق خوارزمیة اقلیدس الممتدة وھناك ثلاثة طرق لمعرفة ھذه القیم (الطرق ھي مشابھ لبعض ، لكن یمكن القول أنھا مختصره من الأخریات). القیم (الطرق ھي مشابھ لبعض ، لكن یمكن القول أنھا مختصره من الأخریات). الطريقة الأولى: وهي يمكن ان نطلق عليها التراجع وفي هذه الطريقة نقوم بالحل عن طريق خوارزمية اقليدس وبعدها تقول بالتراجع الخلفي لايجاد قيمتي m,n كما في المثال التالي: مثال: قم بتمثيل العددين 26و21 بطريقة اقليدس الممتده : فنبدأ بالحل كما هو الحال في طريقة اقليدس : 26 == 1* 21 + 5 و 21 = 4 * 5 + 1 و 5 == 5 * 1 + 0 وتتوقف عند الصفر. الآن المعادلة التي قبل المعادلة التي باقيها صفر أي المعادلة الثانية نقوم بكتابتها بالشكل التالي : 1 = 21 – 4 * 5 ………… [1] أیضا المعادلة الأولى بنفس الشكل : 5 = 26 – 1 * 21 …………[2]

الآن نعوض المعادلة [2] في [1] 1 = 21 – 4 * (26 – 1 * 21)

ومن غیر أجراء عملیة حسابیة ، فقط نفك القوس لینتج : 1 = 21 -4*26 +4*21 1=21(1+4)-4*26 حيث 21 عامل مشترك لیكون لدینا الناتج النھائي : 4*21 +21

1 = 5*21 + (-4)*26 نتاكد من النتيجة 5*21+ -4*26 والناتج يساوي واحد إذاً المعادلة صحيحة

اذاً قيمة m هي 5 وقيمة nهي -4.

المعادلات الديوفانتية الخطية

معادلة ديوفانتية

مبرهنة الباقي الصيني

مبرهنة الباقي الصيني

شجرة ستيرن-بروكوت

شجرة ستيرن-بروكوت, و متتاليات ستيرن-بروكوت من الرتبة i حيث i = 1, 2, 3, 4.

انظر شجرة ستيرن-بروكوت.

الفعالية الخوارزمية

عدد الخطوات المطلوبة في الخوارزمية الإقليدية لحساب القاسم المشترك الأكبر(x,y). النقط الحمراء indicate relatively few steps (quick), whereas yellow, green and blue points indicate successively more steps (slow). The largest blue area follows the line y = Φx, حيث Φ يمثل the Golden ratio.

في النظم العددية الأخرى

متعددات الحدود

مقال تفصيلي :القاسم المشترك الأكبر لمتعددات الحدود

الأعداد الطبيعية الغاوسية

توزيع الأعداد الطبيعية الغاوسية u + vi في المستوى العقدي, من معايير u² + v² أصغر من 500

تعميمات إلى بُنى رياضياتية أخرى

يمكن أن تطبق الخوارزمية الإقليدية في نظرية العقد.

انظر أيضا

• الخوارزمية الثنائية لحساب القاسم المشترك الأكبر,
• القاسم المشترك الأكبر لمتعددات الحدود,
• خوارزمية العلاقة بين الأعداد الطبيعية,
• خوارزمية ليهمر لحساب القاسم المشترك الأكبر.

مراجع

• من كتاب مقدمة في التشفير بالطرق الكلاسيكية