ما هي خوارزمية إقليدس؟
القاسم المشترك الأكبر (GCF)، ويُعرف أيضًا باسم العامل المشترك الأعظم (GCD)، هو أكبر عدد صحيح يقسم عددين صحيحين قسمة تامة دون باقٍ. وخوارزمية إقليدس طريقة قديمة بالغة الكفاءة لإيجاده عبر القسمة المتكررة مع حساب الباقي. تُرجِع هذه الحاسبة القاسم المشترك الأكبر لأي عددين صحيحين، وتُظهر كل خطوة من خطوات القسمة كي تتابع الحل بسهولة.
طريقة الاستخدام
أدخل عددين صحيحين في الخانتين القيمة 1 والقيمة 2. تأخذ الأداة العدد الأكبر مقسومًا والعدد الأصغر مقسومًا عليه، ثم تقسم بشكل متكرر حتى يصبح الباقي صفرًا. آخر مقسوم عليه غير صفري هو القاسم المشترك الأكبر. لا يهم ترتيب العددين، كما تُتجاهَل الإشارات السالبة لأن القاسم المشترك الأكبر يعتمد على القيمة المطلقة فقط.
شرح القانون
في كل خطوة تحسب خارج القسمة والباقي وفق العلاقة: \(a = c \times b + R\)، حيث \(c = \lfloor a / b \rfloor\) و\(R = a \bmod b\). بعد ذلك تستبدل \(a\) بـ \(b\)، و\(b\) بالباقي \(R\)، ثم تكرر العملية. وبما أن كل باقٍ يكون أصغر تمامًا من المقسوم عليه السابق، فإن العملية تنتهي حتمًا. وعندما يصبح \(R = 0\) يكون المقسوم عليه الحالي هو الإجابة. وبصيغة تكرارية:
$$\gcd(a, b) = \gcd(b, a \bmod b),\quad \gcd(a, 0) = a$$مثال محلول
أوجد القاسم المشترك الأكبر للعددين (816، 2260). نضع \(a = 2260\) و\(b = 816\).
$$2260 = 2 \times 816 + 628$$$$816 = 1 \times 628 + 188$$$$628 = 3 \times 188 + 64$$$$188 = 2 \times 64 + 60$$$$64 = 1 \times 60 + 4$$$$60 = 15 \times 4 + 0$$يصل الباقي إلى الصفر عند المقسوم عليه 4، وبذلك يكون القاسم المشترك الأكبر (816، 2260) = 4.
الأسئلة الشائعة
هل GCF وGCD الشيء نفسه؟ نعم. مصطلحا «القاسم المشترك الأكبر» و«العامل المشترك الأعظم» مترادفان، وهذه الأداة تُجيب عنهما معًا.
ماذا لو كان أحد المدخلين صفرًا؟ فإن القاسم المشترك الأكبر \(\gcd(a, 0) = a\)، لأن كل عدد يقسم الصفر. أما إذا كان العددان صفرين معًا فإن القاسم المشترك الأكبر يكون غير معرَّف.
هل يمكنني إيجاد القاسم المشترك الأكبر لثلاثة أعداد؟ طبّق الأداة على أزواج: \(\gcd(x, y, z) = \gcd(\gcd(x, y), z)\).
