📏 سؤال إقليدس
لديك شبكة مستطيلة من a على b خانة (على سبيل المثال 252 × 105). السؤال : ما هو أكبر مربع يمكنه أن يبلّط هذا المستطيل بأكمله، دون أن يترك أي فراغ ؟
هذا المسألة، التي طرحها إقليدس حوالي 300 قبل الميلاد في الكتاب السابع من الأصول، هي مكافئة هندسيًا لحساب القاسم المشترك الأكبر (PGCD) للعددين a و b. والطريقة لحلها هي أقدم خوارزمية في العالم لا تزال تُستعمل كما هي.
🎛️ الطريقة الهندسية في العمل
فكرة إقليدس بسيطة : في مستطيل a × b (مع a > b)، اقتطع مربعًا طول ضلعه b. يتبقى لك مستطيل أصغر. أعد الكرّة. عندما تتمكن من ملء المستطيل الأخير تمامًا بمربعات دون باقٍ، فإن طول ضلع هذا المربع هو القاسم المشترك الأكبر.
🎛️ التقطيع الهندسي للمستطيل
غيّر a و b. شاهد المستطيل وهو يُلتهَم بمربعات متتالية.
النتيجة
PGCD(252, 105) = 21
📐 الصيغة الحسابية (التي تتعلمها في البكالوريا)
هندسيًا، نقتطع مربعات. حسابيًا، نُجري قسمات إقليدية متتالية. القاعدة المفتاح :
PGCD(a, b) = PGCD(b, a mod b)
إلى أن يصبح الباقي مساويًا للصفر.
مثال : PGCD(252, 105)
- 252 = 2 × 105 + 42
- 105 = 2 × 42 + 21
- 42 = 2 × 21 + 0 ← الباقي منعدم
- PGCD = 21 (آخر باقٍ غير منعدم)
⚡ لماذا هذه الخوارزمية سريعة إلى هذا الحد
جمال خوارزمية إقليدس هو أنها تُصغّر أسّيًا الأعداد المتعامل معها. في كل مرحلة، يُقسَّم الباقي على الأقل على 2 (مبرهنة لامي، 1844).
النتيجة : لحساب القاسم المشترك الأكبر لعددين صحيحين من n أرقام، تستغرق الخوارزمية حوالي 5n قسمة. بالنسبة لعددين من 600 رقم (مستعملان في التشفير)، يكون ذلك حوالي 3000 عملية — بضع أجزاء من الثانية على هاتفك.
على سبيل المقارنة، فإن حساب قاسم مشترك أكبر بتفكيك العددين إلى عوامل أولية سيستغرق عمر الكون نفسه بالنسبة لهذه الأحجام.
🔐 خوارزمية إقليدس الممتدة (بيزو)
صيغة قوية أخرى : خوارزمية إقليدس الممتدة لا تحسب فقط القاسم المشترك الأكبر، بل أيضًا معاملي بيزو u و v بحيث :
au + bv = PGCD(a, b)
بالنسبة لـ 252 و 105 : نجد 252 × 2 + 105 × (−5) = 504 − 525 = −21… لا، في الحقيقة 252 × (−2) + 105 × 5 = −504 + 525 = 21. 21 = PGCD. ∎
متطابقة بيزو هذه هي في قلب التشفير RSA : فهي تتيح حساب المقلوب القياسي (المعياري) لعدد، وهي مرحلة حاسمة لتوليد المفتاح الخاص.
🎓 خوارزمية إقليدس في البكالوريا علوم رياضية
خوارزمية إقليدس مقررة في البرنامج الرسمي للثانية بكالوريا علوم رياضية، في باب الحسابيات. ستجد فيها :
- حساب القاسم المشترك الأكبر بالقسمات المتتالية
- مبرهنة بيزو : a ∧ b = d ⟺ ∃ u, v عددان صحيحان : au + bv = d
- متمّمة إقليدس : إذا كان p عددًا أوليًا و p يقسم ab، فإن p يقسم a أو p يقسم b
- المعادلات الديوفانتية ax + by = c (الحل عبر إقليدس الممتدة)
- المقلوب القياسي : إيجاد x بحيث ax ≡ 1 [n]
🌍 2300 سنة من الفائدة المتواصلة
تتمتع خوارزمية إقليدس بمكانة خاصة في تاريخ العلوم : إنها الخوارزمية الوحيدة التي اختُرعت في العصور القديمة ولا تزال تُستعمل كما هي اليوم، بنفس الصيغة، وبنفس التبرير، في جميع حواسيب العالم.
🧠 تأمل أخير
خوارزمية إقليدس مثال مثالي على حقيقة متناقضة ظاهريًا : في العلوم، فإن ما هو الأقدم ليس بالضرورة الأكثر تجاوزًا. بل على العكس، فإن ما يبقى 2000 سنة هو عادةً ما يلامس شيئًا جوهريًا.
عندما تتعلم إقليدس في درس الحسابيات، لا تنظر إليه كطُرفة تاريخية. انظر إليه كـاللبنة الأساسية التي يستعملها كل أمن المعلوماتية في العالم. إنه على الأرجح أنفع شيء قدّمه لك عالم رياضيات يوناني على الإطلاق.
Vérifie ta compréhension
3 questions courtes pour valider tes acquis. Tu peux réessayer.