خوارزمية إقليدس (Euclid's Algorithm): شرح مبسّط لإيجاد القاسم المشترك الأكبر

خوارزمية إقليدس (Euclid's Algorithm) هي طريقة قديمة وبسيطة لإيجاد القاسم المشترك الأكبر بين عددين صحيحين، أي أكبر عدد يقبل القسمة على كليهما دون باقٍ. فكرتها الأساسية أنيقة: بدلاً من تحليل العددين إلى عواملهما الأولية، نكتفي بحساب باقي القسمة بشكل متكرر حتى يصبح الباقي صفراً، فيكون آخر باقٍ غير صفري هو القاسم المشترك الأكبر. هذا هو الجواب المباشر، وفي بقية المقال نشرح كيف تعمل خطوةً بخطوة، ولماذا تُعدّ من أهم اللبنات في علوم الحاسوب.

ما هو القاسم المشترك الأكبر (GCD) ولماذا نحتاجه؟

القاسم المشترك الأكبر (يُرمز له بـ GCD أو gcd) بين العددين 12 و18 هو 6، لأنه أكبر عدد يقسم الاثنين معاً. نستخدمه كثيراً في اختزال الكسور (مثلاً 18/12 تصبح 3/2 بعد القسمة على 6)، وفي أنظمة التشفير، وفي مسائل تقسيم الكميات بالتساوي. المشكلة أن تحليل الأعداد الكبيرة إلى عواملها الأولية بطيء جداً، وهنا تتألق خوارزمية إقليدس لأنها تصل إلى الجواب بسرعة كبيرة دون أي تحليل.

كيف تعمل خوارزمية إقليدس خطوة بخطوة

الصيغة الحديثة والأكثر كفاءة تعتمد على باقي القسمة (عملية modulo)، وليس على الطرح المتكرر:

1. لديك عددان، الأكبر a والأصغر b.
2. احسب باقي قسمة a على b، وسمِّه r.
3. استبدل a بالقيمة b، واستبدل b بالقيمة r.
4. كرّر الخطوات حتى يصبح b مساوياً للصفر.
5. عندها تكون القيمة المتبقية في a هي القاسم المشترك الأكبر.

مثال محلول: إيجاد gcd(48, 18)

• 48 ÷ 18 يعطي باقياً قدره 12 ← نحتفظ بـ (18, 12)
• 18 ÷ 12 يعطي باقياً قدره 6 ← نحتفظ بـ (12, 6)
• 12 ÷ 6 يعطي باقياً قدره 0 ← توقّف

آخر باقٍ غير صفري هو 6، إذاً gcd(48, 18) = 6. لاحظ أننا أنجزنا ذلك في ثلاث خطوات فقط، مهما كبر العددان يبقى عدد الخطوات صغيراً لأن الخوارزمية تعمل بزمن لوغاريتمي.

طريقة الطرح أم طريقة الباقي؟

النسخة الأصلية التي وصفها إقليدس كانت تعتمد على الطرح المتكرر، لكن النسخة الحديثة تستخدم باقي القسمة لأنها أسرع بكثير. إليك المقارنة:

المعيار	طريقة الطرح	طريقة الباقي (Modulo)
الفكرة	نطرح الأصغر من الأكبر تكراراً	نأخذ باقي القسمة مباشرة
السرعة	بطيئة مع الأعداد المتباعدة	سريعة جداً (لوغاريتمية)
مثال gcd(1000, 2)	نحو 500 خطوة	خطوة واحدة
الاستخدام العملي	تعليمي فقط	المعتمدة في البرمجة

الخلاصة: افهم طريقة الطرح لأنها تشرح المنطق، لكن استخدم طريقة الباقي دائماً في الكود الحقيقي.

مثال على التنفيذ البرمجي

الصيغة التكرارية قصيرة ومباشرة في معظم لغات البرمجة:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

نقطة مهمة يغفل عنها كثيرون: هذه الخوارزمية تعمل بشكل صحيح حتى لو كان أحد العددين صفراً، إذ إن gcd(a, 0) يساوي a. كما أنها تعطي النتيجة نفسها بغضّ النظر عن ترتيب العددين، لأن الخطوة الأولى تعيد ترتيبهما تلقائياً.

أين تُستخدم عملياً؟

الاستخدام الأبرز والأصدق تقنياً هو في التشفير. خوارزمية RSA مثلاً تعتمد على نسخة موسّعة تُسمى الخوارزمية الإقليدية الممتدة (Extended Euclidean Algorithm)، التي لا تحسب القاسم المشترك الأكبر فحسب، بل تجد أيضاً المعكوس الضربي ضمن الحساب القياسي (modular inverse)، وهو ما يُستخدم في توليد المفاتيح.

كما تُستخدم في:

• اختزال الكسور في المكتبات الرياضية والبرمجية.
• حل المعادلات الديوفانتية (المعادلات ذات الحلول الصحيحة).
• خوارزميات نظرية الأعداد وبعض تطبيقات الجداول الزمنية والتزامن.

تنبيه: بعض المقالات تبالغ فتنسب لخوارزمية إقليدس أدواراً في «معالجة الصور» أو «إدارة قواعد البيانات» بشكل مباشر، والأدق أنها تظهر هناك بشكل غير مباشر ضمن حسابات أخرى، وليست أداة أساسية في تلك المجالات.

الأسئلة الشائعة

هل تعمل خوارزمية إقليدس مع الأعداد السالبة؟ النسخة الأساسية مصممة للأعداد الصحيحة الموجبة. مع الأعداد السالبة، خذ القيمة المطلقة أولاً، لأن القاسم المشترك الأكبر يُعرّف عادةً كقيمة موجبة.

ما الفرق بينها وبين تحليل العوامل الأولية؟ كلاهما يوصل إلى القاسم المشترك الأكبر، لكن التحليل إلى عوامل أولية بطيء جداً مع الأعداد الكبيرة، بينما خوارزمية إقليدس تظل سريعة حتى مع أعداد ضخمة من مئات الأرقام.

ما الفرق بين النسخة العادية والممتدة؟ النسخة العادية تعطيك القاسم المشترك الأكبر فقط، أما الممتدة فتعطيك إضافةً معاملَين يحققان علاقة معينة، وهي ضرورية لحساب المعكوس الضربي في التشفير.

كم تبلغ سرعتها؟ تعمل بتعقيد زمني لوغاريتمي تقريباً بالنسبة لأصغر العددين، أي أن عدد الخطوات ينمو ببطء شديد حتى لو تضاعف حجم الأرقام، وهذا سرّ اعتمادها في الأنظمة التي تتطلب أداءً عالياً.