تطبيق خوارزمية اقليدس لتعيين القاسم المشترك الأكبر

القاسم المشترك الأكبر لعددين طبيعيين غير معدومين هو أكبر عدد يقسم كلا منهما في الوقت نفسه. لا يتغيّر هذا المعنى بتغيّر الطريقة: طريقة القوائم، والطرح المتتالي، وخوارزمية إقليدس تعطي كلها العدد نفسه، ولا تختلف إلا في عدد الخطوات.

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

تقوم هذه الطريقة على ملاحظة واحدة: إذا كان عدد يقسم العددين معا، فإنه يقسم كذلك الفرق بينهما. إذن استبدال العدد الأكبر بالفرق لا يغيّر شيئا من القواسم المشتركة، ولا يغيّر بالتالي القاسم المشترك الأكبر — لكنه يصغّر الأعداد في كل مرة.

تكبير الصورة

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

تكبير الصورة

الطريقتان تعطيان النتيجة نفسها، والاختيار بينهما اختيار عملي لا غير. الطرح المتتالي لا يحتاج إلا إلى الطرح، فهو مريح ذهنيا عندما يكون العددان متقاربين؛ أما إذا كان أحدهما أكبر بكثير من الآخر فإن عدد الطرحات يصير كبيرا جدا، وهناك تكسب خوارزمية إقليدس الوقت كله.

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

اقسم الأكبر على الأصغر، واحتفظ بالباقي. ثم أزح: القاسم يصير مقسوما، والباقي يصير قاسما. أعد ذلك إلى أن يصير الباقي معدوما، واقرأ عندئذ القاسم الأخير.

وتُرتَّب هذه القسمات الخمس عادة في جدول واحد، سطرا لكل قسمة: هكذا ترى المقسوم والقاسم يتزحزحان خطوة خطوة.

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

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