✖

القاسم المشترك الأكبر

القاسم المشترك الأكبر (greatest common divisor) لعددين صحيحين هو العدد الذي يقسم كلا العددين دون باقٍ، بحيث لا يوجد عدد آخر أكبر منه يقسم كلا العددين دون باقٍ أيضاً.

لنأخذ مثلاً العددين 24 و 32. ما قاسمهما المشترك الأكبر؟ نبحث أولاً عن عدد يقسم كلا العددين.

  • العدد 12 مثلاً يقسم العدد 24، لكنه لا يقسم العدد 32، لأنّ 32÷12 يساوي 2.666…، وهو ليس عدداً صحيحاً. إذن لا يمكن أن يكون العدد 12 القاسم المشترك الأكبر للعددين 24 و 32.
  • وماذا عن العدد 4؟ إنه يقسم كلا العددين، فناتج 24÷4 هو 6، وناتج 32÷4 هو 8. إذن العدد 4 هو أول مرشح لدينا. لكن ألا يوجد عدد أكبر يقسم كلا العددين؟
  • العدد 8 يقسم العدد 24 والعدد 32، وهو أكبر من العدد 4.
  • ولا يوجد عدد آخر أكبر من 8 يقسم كلا العددين. إذن العدد 8 هو القاسم المشترك الأكبر للعددين 24 و 32.

إيجاد القاسم المشترك الأكبر بخوارزمية إقليدس

توجد طريقة بسيطة نسبياً لإيجاد القاسم المشترك الأكبر لعددين، وهي خوارزمية إقليدس. ليكن لدينا في البداية عددان x و y نريد إيجاد قاسمهما المشترك الأكبر، ولنجرب ذلك مثلاً على العددين x = 50 و y = 35. نتبع الخطوات الآتية:

  1. نقسم x / y ونحفظ باقي القسمة، ونرمز لهذا الباقي بالحرف z. في مثالنا نقسم 50÷35، فنحصل على الباقي z = 15.
  2. نبدّل الآن قيم المتغيرات: نضع في المتغير x قيمة y، ونضع في y قيمة z، ونتخلى عن القيمة الأصلية للمتغير x. وبعد هذه الخطوة نحصل على x = 35 و y = 15.
  3. ننظر الآن هل y يساوي صفراً. فإذا كان كذلك، فالقاسم المشترك الأكبر هو العدد x. وبما أنّ y لا يساوي صفراً، فإننا نواصل ونكرر الخطوات كلها من الخطوة الأولى.
  4. نقسم مرة أخرى x / y، أي 35÷15، فنحصل على باقي القسمة z = 5.
  5. نبدّل قيم المتغيرات، فنحصل على x = 15 و y = 5. وبما أنّ y لا يساوي صفراً، فإننا نواصل.
  6. نقسم x / y، أي 15÷5. باقي القسمة z = 0.
  7. نبدّل قيم المتغيرات، فنحصل على x = 5 و y = 0.
  8. الآن y = 0، فتنتهي الخوارزمية. والقاسم المشترك الأكبر هو العدد x = 5.

والمهم أنّ ترتيب العددين لا يؤثر في النتيجة. فلو بدّلنا العددين في المثال، لحصلنا على الزوج x = 35 و y = 50، وتكون الخطوات كما يلي:

  1. نقسم x / y، أي 35÷50، فنحصل على الباقي z = 35.
  2. نبدّل قيم المتغيرات: x = 50 و y = 35.
  3. نرى أننا بعد هذه الخطوة لم نفعل إلا أن بادلنا بين قيمتي المتغيرين x و y…

الآلة الحاسبة

تحسب هذه الآلة الحاسبة القاسم المشترك الأكبر.