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