ما هي خوارزمية إقليدس؟
تُعدّ خوارزمية إقليدس واحدة من أقدم الخوارزميات المعروفة في التاريخ، إذ وصفها عالم الرياضيات اليوناني إقليدس نحو عام 300 قبل الميلاد. وتقوم على إيجاد القاسم المشترك الأكبر (GCD) لعددين صحيحين، أي أكبر عدد يقبل كلاهما القسمة عليه دون باقٍ. تطبّق هذه الحاسبة الخوارزمية على أي عددين صحيحين غير سالبين، كما تُرجع لك المضاعف المشترك الأصغر (LCM).
طريقة الاستخدام
أدخل العددين في الحقلين المخصصين a وb ثم اضغط على زر الحساب. تعرض الحاسبة القاسم المشترك الأكبر كنتيجة رئيسية، والمضاعف المشترك الأصغر كنتيجة ثانوية. لا يهمّ ترتيب العددين، فالقيمة \(\gcd(48, 36)\) تساوي \(\gcd(36, 48)\). وتُعالَج القيم السالبة بقيمتها المطلقة، وإذا كان أحد العددين يساوي صفرًا فإن القاسم المشترك الأكبر هو العدد الآخر ببساطة.
شرح القاعدة الحسابية
تعتمد الخوارزمية على فكرة بسيطة: أي قاسم مشترك للعددين a وb يقسم أيضًا باقي قسمتهما a mod b. لذلك نستبدل العدد الأكبر بالباقي مرارًا وتكرارًا:
$$\gcd(a,b) = \gcd(b,\, a \bmod b), \quad \gcd(a,0) = a$$مع الحالة الأساسية \(\gcd(a, 0) = a\).
تُصغّر كل خطوة العددين بسرعة، حتى إن القيم الكبيرة جدًا تُحلّ في عدد قليل من الخطوات. ثم يُحسب المضاعف المشترك الأصغر وفق المعادلة $$\operatorname{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$$
مثال محلول
لنجد \(\gcd(48, 36)\):
\(48 \bmod 36 = 12 \rightarrow \gcd(36, 12)\)
\(36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = \mathbf{12}\).
إذن القاسم المشترك الأكبر هو 12، والمضاعف المشترك الأصغر $$= \frac{48 \times 36}{12} = \frac{1728}{12} = \mathbf{144}.$$
الأسئلة الشائعة
ماذا لو كان العددان صفرًا؟ القاسم المشترك الأكبر للعددين 0 و0 معرّف هنا بأنه 0، والمضاعف المشترك الأصغر هو 0 أيضًا لعدم وجود مضاعف موجب.
لماذا هي أسرع من سرد العوامل؟ بدلًا من إيجاد كل القواسم، تستخدم الخوارزمية اختصار الباقي، ما يقلّص حجم المسألة بشكل كبير في كل خطوة، وعادة ما يكون الزمن لوغاريتميًا.
هل تتعامل مع الأعداد الكبيرة جدًا؟ نعم. خوارزمية إقليدس فعّالة حتى مع الأعداد ذات الخانات الكثيرة، إذ لا تحتاج سوى عدد قليل من عمليات باقي القسمة.
