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

في البداية، في الرياضيات، خوارزمية أقليدس هي طريقة فعالة تمكن من إيجاد القاسم المشترك الأكبر لعددين وهو أكبر عدد يقسم في نفس الوقت العددين معا بدون أي باق من القسمة. يُرمز له بالفرنسية ب PGCD وبالإنجليزية GCD. ونتناول فيما يلي مزيدًا من التفاصيل.
علاوةً على ذلك، لخوارزمية أقليدس الكثير من التطبيقات النظرية والعملية. تستعمل من أجل اختزال الكسور إلى شكلها المبسط. تستعمل كذلك في أثناء القسمة في إطار الحسابيات النمطية. قد تشكل بعض من الحسابات المستعملة لهذه الخوارزمية، جزءا من بروتوكولات التعمية التي بفضلها تؤمن الاتصالات عبر الأنترنيت. وتستعمل كذلك في طرق تمكن من كسر هذه الأنظمة التشفيرية؛ وذلك بتحليل عدد صحيح إلى عوامل. تستعمل خوارزمية أقليدس في حلحلة بعض الأشكال الخاصة من المعادلات الديوفانتية، من قبيل ايجاد أعداد صحيحة تحقق معادلات تردُدية عدة في إطار مبرهنة الباقي الصينية، ومن قبيل إنشاء الكسور المستمرة ومن أجل ايجاد قيم مقربة جذرية لأعداد حقيقية. أضف إلى ذلك أنها تستعمل حجرَ أساس في البرهان على مبرهنات في نظرية الأعداد من قبيل مبرهنة المربعات الأربع للاغرانج والمبرهنة الأساسية في الحسابيات. صُممت الخوارزمية في الأصل من أجل العمل على قسمة الأعداد الطبيعية والقياسات الهندسية، ولكنها عُممت خلال القرن التاسع عشر على كائنات ر ياضية أخرى. الأعداد الصحيحة الغاوسية ومتعددات الحدود ذات متغير واحد مثالان على ذلك.
ومن جهة أخرى، الصيغة التي وُصفت أعلاه لخوارزمية أقليدس (وهكذا وصفها إقليدس) قد تتأخر أثناء عملية حساب الفرق بين أكبر العددين وأصغرهما، خصوصا إذا كان العدد الأكبر أكبر بكثير من العدد الأصغر. هناك صيغة أكثر سرعة من هذه الصيغة، تمكن من اختصار هذه المراحل. بدلا من تعويض أكبر العددين بالفرق بينه وبين أصغر العددين، يُعوض أكبر العددين بباقي قسمته على أصغر العددين. في هذه الطريقة، الخوارزمية تتوقف عندما يصيرا الباقي مساويا للصفر. تطبيقا لهذه الطريقة، الخوارزمية لا تتطلب أبدا، من الخطوات ما يتجاوز خمسة أضعاف عدد أرقام العدد المقسوم عليه، مكتوبا في القاعدة 10. برهن على هذه المسألة عالم الرياضيات الفرنسي غابرييل لامي. كان ذلك عام 1844، غارسا بذلك البذرة الأولى لعلم التعقد الحسابي. رأت النور خلال القرن العشرين طرق إضافية مكنت من جعل الخوارزمية أكثر قوة وسرعة.
وفي السياق ذاته، تعتمد خوارزمية أقليدس على مبدأ أن القاسم المشترك الأكبر لعددين لا يتغير إذا عُوض أكبرهما بالفرق بينه وبين أصغرهما. مثلًا، 21 هو القاسم المشترك الأكبر للعددين 252 و 105 (نظرا إلى أن 252 = 21 * 12 و 105 = 21 * 5)، وأن 21 هو كذلك القاسم المشترك الأكبر ل 105 و 252 - 105 = 147. بقلب مراحل خوارزمية أقليدس، الأخيرة، فما قبلها، فما قبلها وهكذا، يُحصل على صيغة يُعبر فيها عن القاسم المشترك الأكبر بتأليفة خطية للعددين الأصليين، أي على شكل مجموعهما بعد ضرب كل واحد منهما في عدد صحيح ما. مثلًا، . تعرف هذه المسألة بمتطابقة بيزو نسبة إلى عالم الرياضيات الفرنسي إيتيان بيزو.
وعلى صعيد آخر، سميت هذه الخوارزمية هكذا نسبة إلى عالم الرياضيات الإغريقي أقليدس الذي وصف الخوارزمية لأول مرة في كتابه المعروف باسم الأصول (قرابة عام 300 ق.م). هي مثال عن الخوارزميات (الخوارزمية طريقةٌ تمكن من القيام بعملية ما، خطوة خطوة طِبقا لقواعد معينة محددة مسبقا). وهو من أقدم الخوارزميات اللائي ما زلن قيد الاستعمال. قد تستعمل من أجل اختزال كسر إلى شكله المبسط غير القابل للاختزال، وهي جزء من الحسابات المتعلقة بنظرية الأعداد والتشفير.
54 = 36 * 1 + 18
مرة أخرى:
المعادلات الديوفانتية الخطية
علاوةً على ذلك، يمكن لخوارزمية أقليدس كذلك أن تستعمل من أجل حلحلة الكثير من المعادلات الديوفانتية الخطية. تظهر واحدة من هده المعادلات في مبرهنة الباقي الصيني.
مبرهنة الباقي الصيني
مبرهنة الباقي الصيني
مثال
- القاسم المشترك الأكبر ل 48 و 60 هو 12.
- القاسم المشترك الأكبر للعددين 252 و 198:
- 252 = 198 * 1 + 54 ‘ أربع وخمسون هو باقي قسمة 252 على 198
متطابقة بيزو
علاوةً على ذلك، تنص متطابقة بيزو على أن القاسم المشترك الأكبر g لعددين a و b يمكن أن يمثل مجموعا خطيا للعددين a و b؛ أي أنه يوجد عددان، s و t حيث يتوفر ما يلي:
1 = 5*21 + (-4)*26
- نتاكد من النتيجة 5*21+ -4*26 والناتج يساوي واحد إذاً المعادلة صحيحة
- إذاً قيمة m هي 5 وقيمة n هي -4.
- طريقة المصفوفات
في المعادلتين السابقتين
- 1 = 21 – 4 * (26 – 1 * 21)
- ومن غیر أجراء عملیة حسابیة، فقط نفك القوس لینتج:
- 1 = 21 -4*26 +4*21
- 1=21(1+4)-4*26 حيث 21 عامل مشترك
- لیكون لدینا الناتج النهائي: 4*21 +21
36 = 18 * 2 + 0
علاوةً على ذلك، هنا وصلنا للصفر فيكون العدد الثاني 18 هو القاسم المشترك الأكبر.
الخلفية: القاسم المشترك الأكبر
الخوارزمية الإقليدية الممتدة
أیضا المعادلة الأولى بنفس الشكل:
- مثال: قم بتمثيل العددين 26 و 21 بطريقة اقليدس الممتدة:
- فنبدأ بالحل كما هو الحال في طريقة اقليدس:
- 26 = 1* 21 + 5 و 21 = 4 * 5 + 1 و 5 = 5 * 1 + 0
من جهة ثانية، كیف یمكن أیجاد قیمتي n و m وذلك عن طریق خوارزمیة اقلیدس الممتدة وهناك ثلاثة طرق لمعرفة هذه القیم (الطرق هي مشابه لبعض، لكن یمكن القول أنها مختصره من الأخریات).
في هذا الإطار، وتتوقف عند الصفر. الآن المعادلة التي قبل المعادلة التي باقيها صفر أي المعادلة الثانية نقوم بكتابتها بالشكل التالي:
من جهة ثانية، الطريقة الأولى: وهي يمكن ان نطلق عليها التراجع وفي هذه الطريقة نقوم بالحل عن طريق خوارزمية اقليدس وبعدها تقول بالتراجع الخلفي لايجاد قيمتي m،n كما في المثال التالي:
من جانب آخر، یمكن تمثیل القاسم المشترك الأكبر للعددین عن طریق دمج خطي مع عددین آخرین،
الفعالية الخوارزمية
ومن ناحية أخرى، انظر إلى بيير جوزيف إتيان فينك. في سنة 1837، درس إيميل ليجي أسوأ حالة، والتي هي حيث يكون المقسوم والمقسوم عليه عددان متتاليان من متتالية فيبوناتشي. واصل غابرييل لامي سير فينك في عام 1844، مبرهنا على أن عدد خطوات خوارزمية إقليدس لا تتجاوز أبدا خمس مرات عدد الأرقام اللائي يكونن المقسوم عليه، مكتوبا في القاعدة العشرية.
- في النظم العددية الأخرى
- الأعداد الجذرية والأعداد الحقيقية
- متعددات الحدود
إضافةً إلى ذلك، دُرست فعالية خوارزمية أقليدس بشكل كثيف. تتمثل هذه الفعالية في عدد الخطوات اللازمة من أجل إيجاد القاسم المشترك الأكبر المراد حسابه. أول تحليل لفعالية الخوارزمية يرجع إلى العالم غيينو، (كان ذلك عام 1811)، حيث أثبت أنه أثناء حساب القاسم المشترك الأكبر للعددين u و v، عدد الخطوات اللازمة، لا يمكن أن يتجاوز v. وزاد فيما بعد هذا البرهانَ دقة عندما برهن أن هذا العدد لا يمكن أن يتجاوز v/2 +2.
فنجد القاسم المشترك للعددين 198 و 54
نكرر العملية هذه المرة مع: 54 و 36
198 = 54 * 3 + 36 ‘ ست وثلاثون هو باقي القسمة.
وصف الخوارزمية
حيث r هو باقي قسمة A على B.
وفي هذا الصدد، القاسم المشترك الأكبر لعددين طبيعيين A، B يساوي القاسم المشترك الأكبر للعدد الثاني B وباقي قسمة A على B، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر.
N هو القاسم المشترك الأكبر.
التطور التاريخي
تطبيقات رياضياتية
ومن ناحية أخرى، خوارزمية أقليدس هي واحدة من أقدم الخوارزميات الجارية الاستعمال. ظهرت في كتاب الأصول لإقليدس (في نحو عام 300 قبل الميلاد)، وبالتحديد في الكتاب السابع (الخاصيتان الأولى والثانية) والكتاب العاشر (الخاصيتان الثانية والثالثة). في الكاتب السابع، طُبقت الخوارزمية على الأعداد الطبيعية بينما في الكتاب العاشر، طُبقت على أطوال القطع المستقيمة.
إضافةً إلى ذلك، خلال القرن التاسع عشر، فتحت خوارزمية أقليدس الباب نحو تطور أنظمة عددية جديدة. الأعداد الغاوسية وأعداد أيزنشتاين مثالان على ذلك. في سنة 1815، استعمل غاوس خوارزمية أقليدس من أجل البرهان على وحدانية تفكيك الأعداد الغاوسية. رغم أن العمل قِيم بي في عام 1815، إلا أنه لم ينشر لأول مرة إلي في سنة 1832. أشار غاوس إلى الخوارزمية في كتابه استفسارات حسابية والذي نُشر في عام 1801، ولكن فقط في شكل طريقة تمكن من حساب الكسور المستمرة.
شجرة ستيرن-بروكوت
الكسور المستمرة
وعلى صعيد آخر، تُستعمل خوارزمية أقليدس من أجل ترتيب جميع الأعداد الجذرية الموجبة في شجرة ثنائية البحث غير منتهية، تسمى شجرة ستيرن-بروكوت.
الأعداد الطبيعية الغاوسية
- المجالات الإقليدية
- الحلقات غير التبادلية
- تعميمات إلى بُنى رياضياتية أخرى
- المراجع
- من كتاب مقدمة في التشفير بالطرق الكلاسيكية
وفي السياق ذاته، الأعداد الغاوسية الصحيحة هن أعداد مركبة حيث u و v أعداد صحيحة، و هو الجذر التربيعي لناقص واحد. بتعريف خوارزمية مماثلة لخوارزمية أقليدس، يتبين أن الأعداد الغاوسية تقبل هي الأخرى تفكيكا وحيدا لجداء أعداد غاوسية أخرى، وذلك باستعمال الحجة نفسها التي استعمل أعلاه. هذا التفكيك الوحيد يساعد في الكثير من المجالات، منها مثلًا، ايجاد جميع ثلاثيات فيثاغورس، ومنها كذلك البرهان على مبرهنة فيرما حول مجموع مربعين. مساهمة خوارزمية أقليدس في هذه التطبيقات غير أساسية حيث يمكن أن يُبرهن عليها بطرق أخرى.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟