عزيزي القارئ دعنا نقوم بقفزة الى الماضى ودعنا نستحضر منه شيئا. دعنا نقوم برحلة الى المرحلة الابتدائية ونتذكر موضوعا ربما نسيه اغلبنا اليوم! كان يشغلنا فى تلك الايام -من ضمن اشياء اخرى- شاغلان: القاسم المشترك الأكبر و المضاعف المشترك الأصغر. وبعد ان اصابنا الأرق فى تلك السن الوادعة وتعلمنا تلك المواضيع لكى نجتاز امتحانات النقل نسيناها ولم يخبرنا احد لماذا تعلمناها أصلا وأخص تحديدا موضوع القاسم المشترك الأكبر.

اذا كان لدينا عدد طبيعي ك 12 مثلا فان الاعداد اللتى تقسمه هى 1 و 2 و 3 و 4 و 6 و12  بمعنى انها هى الاعداد اللتى تقبل 12 القسمة عليها بدون باق. ولذا فان هذه الاعداد تسمى قواسم الأثنى عشر. واذا كان لدينا عدد طبيعي اخر ك 8 فان قواسمه هى: 1 و 2 و 4 و 8. ومن هنا نرى ان القواسم المشتركة بين 12 و 8 هي الأعداد: 2 و 4. وبالتالى فأن القاسم المشترك الأكبر هو 4.

اما بالنسبة للمضاعف المشترك الأصغر فاننا نبحث عن مضاعفات الأعداد. تحديدا نبحث اولا عن 12 مفردة ثم ضعفي 12 ثم ثلاثة اضعاف 12 فاربعة اضعاف 12 وهكذا. وكذلك نفعل نفس الامر بالنسبة للعدد 8 . اذن مضاعفات 12 هى:12 و 24 و 36 و 48 الى اخره. اما مضاعفات الثمانية فهي: 8 و 16 و 24 و 32 الى اخره. ومن هنا نرى ان المضاعف المشترك الأصغر هو 24!

لكن ما الفائدة وراء كل ذلك؟ الاجابة سهلة بالنسبة للمضاعف المشترك الأصغر. نحن نستخدمه فى حساب الكسور. نعلم اننا اذا اردنا جمع 1/12 زائد 1/8 فاننا لابد ان نوحد المقامات أولا. ومن العملي ان نستخدم لذلك المضاعف المشترك الأصغر كمقام مشترك. فيتحول العددان الى 2/24 و 3/24 فتكون النتيجة النهائية 5/24 .

لكن ما فائدة القاسم المشترك الأكبر؟ وكيف يمكن ان نحسبه لعددين؟ وهل لا توجد طريقة اخرى سوي هذه الطريقة الطويلة اللتى تتطلب تجريب كل الاعداد حتى نحدد القواسم المشتركة؟! الاجابة اللتى يوحى بها عنوان الموضوع: بل توجد طريقة ذكية جدا. وهذه الطريقة قدمها اقليدس فى كتابه العناصر. بل ولعل بعضنا درسها فى المرحلة الأبتدائية!

دعونا نقدم للموضوع بمثال بسيط وان كان غير واقعى. لنتخيل ان لدينا مصنعا لانتاج العصى. وان هناك مقاسين لتلك العصى. اما ان يكون طولها 8 أو 12 متر. وبما أن الطلب فى السوق متقلب فاحيانا تشح العصى القصيرة واحيانا نطلب العصى الطويلة فلا نجدها. من اجل ذلك قررنا اننا لن نصنع العصى بكامل طولها ولكن سنصنع فقط اجزاء قصيرة يمكن لحمها مع بعض لنحصل فى النهاية على العصى الطويلة أو القصيرة. السؤال الأن ما هو الطول المثالى لتلك الاجزاء اللتى تقسم المقاسين على حد سواء فنتوائم مع متطلبات السوق وفي نفس الوقت تكون أطول ما يمكن فنقلل من عمليات اللحام ونوفر التكاليف؟ الاجابة كما ذكرناها اعلى هى 4 متر. فبلحم قطعتين معا نحصل على العصا ذات الثمانية امتار وبلحم ثلاث قطعات نحصل على العصا الأطول. لكن دعونا نتأمل فى الأمر بصورة عامة.

مبدأيا ماذا اذا كان للعصاتين نفس الطول: 8 متر؟. منطقيا اننا سنصنع مقاسا واحدا هو 8 متر. ففي هذه الحالة لن توجد لدينا اى مشاكل فى التوزيع ولن نحتاج الى اية لحامات. لكن ماذا عن الحالة العامة حيث تكون العصاتين مختلفتين فى الطول؟

طريقة اقليدس

نرى فى الرسم: اذا كانت العصاتان مختلفتين فى الطول فبامكاننا تقسيم العصا الطويلة الى جزأين: جزأ بطول العصا القصيرة وجزأ ثان هو المتبقي. ومن الرسم نلاحظ ان  أي قاسم مشترك لابد أن يقسم العصاتين القصيرة والطويلة وكذلك الجزء الفارق بينهما بدون اي باق. ولذلك يمكننا تحويل مسألة البحث عن القاسم المشترك الأكبر بين العصا الطويلة و العصا القصيرة الى مسألة أخري للبحث عن القاسم المشترك الأكبر بين العصا القصيرة وذلك الجزأ المتبقى وتبقى النتيجة كما هي! أى ان القاسم المشترك الاكبر للعددين 12 و 8 هو نفسه القاسم المشترك الأكبر للعددين 8 و 4 حيث ان 8 هو الطول الأصغر و 4 هو الفارق بين 12 و 8. والقاسم المشترك بين 8 و 4 يساوى القاسم المشترك الأكبر بين 4 و 4 . حيث ان 4 هى الطول الاقصر و الاربعة الثانية هى الفارق فى الطول بين 4 و 8. وحيث اننا حصلنا أخيرا على عصاتين متساويتين فيكون القاسم المشترك الاكبر بينهما هو طولهما نفسه اى 4 متر. وبذلك نكون وصلنا الى مرادنا اللذى نبحث عنه.

اذن القاعدة العامة هو ان نحدد فى كل خطوة ماهو الرقم الأصغر وما هو الفارق بين العددين حتى نصل فى النهاية الى عددين متساويين. مثال اخر بالنسبة للعديدن 70 و 30. القاسم المشترك يساوى القاسم المشتركب بين 30 و 40. ومن ثم يساوى القاسم المشترك بين 30 و 10 . ومن ثم العددين 10 و 20 ومن ثم العددين 10 و 10 . ثم تكون النتيجة النهائية 10. وهذه الطريقة تسمي طريقة اقليدس البطيئة!

ويجب أن نلاحظ ان هناك دائم حل لمسائل القاسم المشترك الأكبر. فحيث ان العددين طبيعيان فالعدد 1 هو قاسم مشترك لجميع الأعداد الطبيعية. وفى ابطأ الأحوال سنظل نطرح الأطوال من بعضها حتى نحصل على 1 فى النهاية. ولذلك قد تطول هذه العملية. مثلا لكى نبحث عن القاسم المشترك الأكبر بين 99 و 2. سنكرر عملية الطرح 49 مرة حتى نصل فى النهاية الى العددين 1و2 . ومن ثم نطرح 1 من 2 مرة اخرى لنصل الى ان القاسم المشترك الأكبر هو 1.

طريقة اقليدس السريعة

وطريقة اقليدس السريعة تتبع نفس المبدأ السابق لكن مع تعديل بسيط: فى كل خطوة لاحقة نستبدل العددين الأصليين بالعدد الاصغر وبباقى قسمتهما وليس الفرق بينهما. وهذا يتضح ايضا من الرسم حيث ان مضاعفات الطول الأقصر تقبل التقسيم على القاسم المشترك الأكبر بدون باق. وكذلك ينبغى ان يكون باقى قسمة الطول الأكبر على الطول الأصغر. وتقول القاعدة الثانية لطريقة اقليدس السريعة: اذا كان العدد الأكبر يقبل القسمة على العدد الأصغر بدون باق فيكون الحل اللذى نبحث عنه هو العدد الأصغر نفسه.

بالتالي العددين 12 و 8 سنستبدلهما بالعددين 8 و 4 . حيث ان 8 هو العدد الأصغر و 4 هى باقى قسمة 12 على 8 . وحيث ان 8 تقبل القسمة على 4 بدون باق فيكون الحل هو !4. أما بالنسبة للعديدن 70 و 30 وحيث ان ناتج قسمة 70 على 30 هو 2 ويكون الباقى 10. فنستبدل العديدن ب 30 و 10 . وحيث ان 30 تقبل القسمة على 10 بدون باق. فيكون الحل هو 10. وكذلك الأمر بالنسبة للعديدن 99 و 2 . نستبدلهما بالعددين 2 و 1 . لأن قسمة 99 على 2 تعطي 49 و الباقى 1. وحيث ان 2 تقبل القسمة على 1 بدون باق فيكون القاسم المشترك الأكبر هو 1.

لكن ماذا فائدة القاسم المشترك الاكبر؟ هناك فائدة نعلمها من ايام المدرسة وهى فى اختصار الكسور. مثلا اذا كان لدين العدد 8/12 وبما ان القاسم المشترك بين 8 و 12 هو 4 . فاننا نستطيع ان نختصر 4 من البسط والمقام لنحصل فى النهاية على العدد 2/3 . لكن ليست هذه الفائدة الأهم لطريقة اقليدس اللتى سنطلق عليها الان خوارزمية اقليدس. فهي مستخدمة بقوة في ميدان البرمجيات. فهذه الطريقة نحتاج اليها كثيرا وبدون ان نشعر فى تعاملنا مع اجهزة الكمبيوتر. حيث انها تستخدم بقوة فى ميدان التشفير ونقل المعلومات بصورة امنة.