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

في الرياضيات، خوارزمية أقليدس (بالإنجليزية: Euclidean algorithm)‏ هي طريقة فعالة تمكن من إيجاد القاسم المشترك الأكبر لعددين وهو أكبر عدد يقسم في نفس الوقت العددين معا بدون أي باق من القسمة. يُرمز له بالفرنسية ب PGCD وبالإنجليزية GCD. سميت هذه الخوارزمية هكذا نسبة إلى عالم الرياضيات الإغريقي أقليدس الذي وصف الخوارزمية لأول مرة في كتابه المعروف باسم الأصول (حوالي عام 300 ق.م). هي مثال عن الخوارزميات (الخوارزمية طريقةٌ تمكن من القيام بعملية ما، خطوة خطوة طِبقا لقواعد معينة محددة مسبقا). وهو من أقدم الخوارزميات اللائي ما زلن قيد الاستعمال. قد تستعمل من أجل اختزال كسر إلى شكله المبسط غير القابل للاختزال، وهي جزء من الحسابات المتعلقة بنظرية الأعداد والتشفير. تعتمد خوارزمية أقليدس على مبدأ أن القاسم المشترك الأكبر لعددين لا يتغير إذا عُوض أكبرهما بالفرق بينه وبين أصغرهما. على سبيل المثال، 21 هو القاسم المشترك الأكبر للعددين 252 و 105 (نظرا إلى أن 252 = 21 * 12 و 105 = 21 * 5)، وأن 21 هو أيضا القاسم المشترك الأكبر ل 105 و 252 - 105 = 147. بقلب مراحل خوارزمية أقليدس، الأخيرة، فما قبلها، فما قبلها وهكذا، يُحصل على صيغة يُعبر فيها عن القاسم المشترك الأكبر بتأليفة خطية للعددين الأصليين، أي على شكل مجموعهما بعد ضرب كل واحد منهما في عدد صحيح ما. على سبيل المثال، . تعرف هذه المسألة بمتطابقة بيزو نسبة إلى عالم الرياضيات الفرنسي إيتيان بيزو. الصيغة التي وُصفت أعلاه لخوارزمية أقليدس (وهكذا وصفها إقليدس) قد تتأخر أثناء عملية حساب الفرق بين أكبر العددين وأصغرهما، خصوصا إذا كان العدد الأكبر أكبر بكثير من العدد الأصغر. هناك صيغة أكثر سرعة من هذه الصيغة، تمكن من اختصار هذه المراحل. بدلا من تعويض أكبر العددين بالفرق بينه وبين أصغر العددين، يُعوض أكبر العددين بباقي قسمته على أصغر العددين. في هذه الطريقة، الخوارزمية تتوقف عندما يصيرا الباقي مساويا للصفر. تطبيقا لهذه الطريقة، الخوارزمية لا تتطلب أبدا، من الخطوات ما يتجاوز خمسة أضعاف عدد أرقام العدد المقسوم عليه، مكتوبا في القاعدة 10. برهن على هذه المسألة عالم الرياضيات الفرنسي غابرييل لامي. كان ذلك عام 1844، غارسا بذلك البذرة الأولى لعلم التعقد الحسابي. رأت النور خلال القرن العشرين طرق إضافية مكنت من جعل الخوارزمية أكثر قوة وسرعة. لخوارزمية أقليدس العديد من التطبيقات النظرية والعملية. تستعمل من أجل اختزال الكسور إلى شكلها المبسط. تستعمل أيضا في أثناء القسمة في إطار الحسابيات النمطية. قد تشكل بعض من الحسابات المستعملة لهذه الخوارزمية، جزءا من بروتوكولات التعمية التي بفضلها تؤمن الاتصالات عبر الأنترنيت. وتستعمل أيضا في طرق تمكن من كسر هذه الأنظمة التشفيرية؛ وذلك بتحليل عدد صحيح إلى عوامل. تستعمل خوارزمية أقليدس في حلحلة بعض الأشكال الخاصة من المعادلات الديوفانتية، من قبيل ايجاد أعداد صحيحة تحقق معادلات تردُدية عدة في إطار مبرهنة الباقي الصينية، ومن قبيل إنشاء الكسور المستمرة ومن أجل ايجاد لأعداد حقيقية. أضف إلى ذلك أنها تستعمل حجرَ أساس في البرهان على مبرهنات في نظرية الأعداد من قبيل مبرهنة المربعات الأربع للاغرانج والمبرهنة الأساسية في الحسابيات. صُممت الخوارزمية في الأصل من أجل العمل على قسمة الأعداد الطبيعية والقياسات الهندسية، ولكنها عُممت خلال القرن التاسع عشر على كائنات ر ياضية أخرى. الأعداد الصحيحة الغاوسية ومتعددات الحدود ذات متغير واحد مثالان على ذلك.