شهادة القاسم الأكبر: البواقي والرجوع في القسمة

التحقق من القاسم الأكبر بتركيب العددين يضيف سببًا واضحًا إلى النتيجة التي أعطتها القسمة المتتابعة. سنؤلف مثال العددين ثلاثمئة وثلاثة وعشرين ومئة وسبعة وثمانين، ونحسب بواقيهما حتى نتوقف. ثم نرجع في المعادلات لنكتب القاسم بعمليات ضرب وجمع وطرح في العددين الأصليين. نريد أن نفهم لماذا تحافظ الخطوات على القواسم المشتركة، ولماذا لا يكفي أن نجد عددًا يقسم الأصلين فقط فنسمّيه الأكبر. الأعداد والجداول والرسمان من إعدادنا للشرح، وليست نتائج مسح أو اختبار أداء برنامج. نبدأ بأعداد صحيحة موجبة ونكتب خارج القسمة والباقي في خانتين مختلفتين، ثم نفصل حساب القاسم من شهادة تؤكد أنه أكبر ما يمكن.

الخلاصة السريعة

تبدل خوارزمية إقليدس زوج العددين بزوج القاسم والباقي مع حفظ القواسم المشتركة. آخر باقٍ غير صفري يعطي القاسم الأكبر. وللتحقق يمكن أن نجمع شرطين: العدد يقسم الأصلين، ويمكن كتابته تركيبًا بمعاملات صحيحة منهما؛ عندئذ لا يستطيع قاسم مشترك أكبر تجاوزه. [1] [2]

القسمة الأولى تكتب 323=187×1+136؛ الزوج التالي 187 و 136، وليس 323 و 136 مع تجاهل القاسم السابق.
البواقي المتتابعة 136 ثم 51 ثم 34 ثم 17 ثم صفر؛ القاسم المطلوب 17، لا صفر ولا خارج القسمة الأخير 2.
للتحقق من الاشتراك:323=17×19 و 187=17×11؛ العدد 17 يقسم الأصلين دون باقٍ.
للتحقق من الأكبر:17=7×187−4×323؛ أي قاسم مشترك للأصلين يقسم هذا التركيب، ولذلك يقسم 17.
العدد 1 يقسم الأصلين أيضًا، لكن ذلك وحده لا يجعله الأكبر. والعدد 34 تركيب صحيح منهما، لكنه لا يقسمهما؛ كل شرط يحتاج الآخر.
قسمة البسط 323 والمقام 187 على 17 تختصر الكسر إلى 19 على 11، مع الاحتفاظ بقيمته.
البواقي الصحيحة الموجبة تتناقص، ولذلك تنتهي القسمة في هذا المثال. لا نواصل القسمة على صفر بعد سطر التوقف.

قاسم مشترك لا يعني الأكبر تلقائيًا

القاسم المشترك عدد يقسم الأصلين دون باقٍ، والقاسم المشترك الأكبر هو أكبر القواسم المشتركة الموجبة للزوج الذي ندرسه. [1]

العدد واحد يقسم ثلاثمئة وثلاثة وعشرين ومئة وسبعة وثمانين، لكننا لا نكتفي به جوابًا عن الأكبر. نحتاج طريقة تبين كل ما يمكن أن يصل إليه قاسم مشترك، أو شهادة تمنع وجود واحد أكبر من المرشح الذي وجدناه. فرق السؤالين مهم: اختبار القسمة قد يؤكد الاشتراك، بينما كلمة الأكبر تحتاج حجة إضافية. نعرض في نهاية المثال كيف يعمل الاختباران معًا دون أن نكتب قائمة طويلة بكل العوامل.

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

اكتب خارج القسمة والباقي معًا

في القسمة الصحيحة نكتب العدد الأول مساويًا للقاسم مضروبًا في خارج القسمة زائد الباقي، ويكون الباقي غير سالب وأصغر من القاسم الموجب. [2]

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

ويمكن أن تكتب مساواة حسابية صحيحة بخارج صفر وباقٍ ثلاثمئة وثلاثة وعشرين، لكنها لا تحقق شرط أن الباقي أصغر من المئة والسبعة والثمانين. شرط الباقي ليس تفصيلًا تجميليًا؛ هو ما يجعل الخطوات تنقص وتستقر على إجراء محدد. افحص المساواة وحدود الباقي معًا قبل قبول صف في الجدول، بدل التأكد من الضرب فقط ثم حمل قيمة لا تناسب قسمة الخوارزمية.

323 = 187 × 1 + 136; 0 ≤ 136 < 187

لماذا يقسم كل قاسم مشترك الباقي؟

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

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

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

والعكس يمنع ظهور قاسم إضافي

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

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

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

اتبع سلسلة المثال حتى صفر الباقي

بعد القسمة الأولى نقسم مئة وسبعة وثمانين على مئة وستة وثلاثين، فيكون الخارج واحدًا والباقي واحدًا وخمسين. ثم نقسم مئة وستة وثلاثين على الواحد والخمسين، فيكون الخارج اثنين والباقي أربعة وثلاثين. بعد ذلك الواحد والخمسون على الأربعة والثلاثين يعطي خارجًا واحدًا وباقيًا سبعة عشر. وأخيرًا أربعة وثلاثون على سبعة عشر يعطي خارج اثنين وباقي صفر.

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

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

المقسوم	القاسم	الخارج	الباقي
323	187	1	136
187	136	1	51
136	51	2	34
51	34	1	17
34	17	2	0

آخر باقٍ غير صفري هو الجواب

تنتهي الخوارزمية بباقٍ صفر، ويكون آخر باقٍ غير صفري القاسم المشترك الأكبر. البواقي الموجبة تتناقص، لذلك لا تستمر القسمة الصحيحة إلى ما لا نهاية. [2]

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

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

gcd(323,187) = gcd(34,17) = gcd(17,0) = 17

ارجع في المعادلات لتركيب السبعة عشر

تسمح خطوات القسمة بالرجوع وكتابة القاسم الأكبر تركيبًا بمعاملات صحيحة من العددين الأصليين. [2]

نبدأ من السبعة عشر يساوي واحدًا وخمسين ناقص أربعة وثلاثين. نعوض الأربعة والثلاثين بمئة وستة وثلاثين ناقص ضعفي الواحد والخمسين، فيصير السبعة عشر ثلاثة أضعاف الواحد والخمسين ناقص مئة وستة وثلاثين. ثم نعوض الواحد والخمسين بمئة وسبعة وثمانين ناقص مئة وستة وثلاثين، فنحصل على ثلاثة أضعاف مئة وسبعة وثمانين ناقص أربعة أضعاف مئة وستة وثلاثين.

وأخيرًا مئة وستة وثلاثون هو ثلاثمئة وثلاثة وعشرون ناقص مئة وسبعة وثمانين. بعد التعويض وتجميع الحدود يصبح السبعة عشر سبعة أضعاف المئة والسبعة والثمانين ناقص أربعة أضعاف الثلاثمئة والثلاثة والعشرين. احتفظنا بالمساواة في كل تعويض، ولم نخمن معاملين ثم نقرب نتيجتهما. الرسم الثاني يميز هذا التركيب من اختبار القسمة الذي سنجريه بجانبه.

17 = 51 − 34 = 3×51 − 136 = 3×187 − 4×136 = 7×187 − 4×323

شهادتان تؤكدان أنه الأكبر

إذا قسم عدد الأصلين، فإنه يقسم أي تركيب صحيح منهما بالجمع والطرح والضرب في أعداد صحيحة. [1]

الاختبار الأول يبين أن سبعة عشر قاسم مشترك: ثلاثمئة وثلاثة وعشرون سبعة عشر في تسعة عشر، ومئة وسبعة وثمانون سبعة عشر في أحد عشر. إذن يوجد قاسم مشترك بهذا المقدار فعلًا، ولا بد أن يكون الأكبر على الأقل سبعة عشر. لم يثبت هذا الاختبار وحده عدم وجود قاسم مشترك أكبر منه، ولذلك نضيف المساواة التي استخرجناها بالرجوع.

بما أن كل قاسم مشترك يقسم تركيب السبعة عشر من الأصلين، فإنه يقسم سبعة عشر. القاسم الصحيح الموجب لعدد موجب لا يتجاوزه، فكل قاسم مشترك لا يزيد على سبعة عشر. جمع هذا الحد مع وجود السبعة عشر قاسمًا مشتركًا يثبت أنه الأكبر. الشهادة قصيرة بعد حسابها، ويمكن للقارئ فحص الضربين والتركيب من الأصلين دون إعادة كل جدول البواقي كي يثق بالنتيجة.

323 = 17×19; 187 = 17×11; 7×187 − 4×323 = 1309 − 1292 = 17

بطاقتان أصليتان لإثبات أن سبعة عشر أكبر قاسم: قسمتا الأصلين دون باقٍ، ومساواة سبعة عشر بتركيب سبعة في مئة وسبعة وثمانين ناقص أربعة في ثلاثمئة وثلاثة وعشرين — شهادة تحقق أصلية: السبعة عشر يقسم الأصلين إلى تسعة عشر وأحد عشر، ويكتب أيضًا سبعة في المئة والسبعة والثمانين ناقص أربعة في الثلاثمئة والثلاثة والعشرين. الشرط الأول يثبت وجود المرشح قاسمًا، والثاني يمنع قاسمًا مشتركًا أكبر منه.

لماذا يحتاج كل اختبار إلى الآخر؟

العدد واحد يقسم الأصلين، لكن الاختبار الأول وحده لا يرفعه إلى الأكبر؛ المثال يحمل قاسمًا أكبر هو سبعة عشر. أما أربعة وثلاثون، فيمكن كتابته أربعة عشر في مئة وسبعة وثمانين ناقص ثمانية في ثلاثمئة وثلاثة وعشرين، لأنه ضعف تركيب السبعة عشر. مع ذلك لا يقسم الأصلين؛ كلاهما عدد فردي من مضاعفات سبعة عشر وليس مضاعفًا للأربعة والثلاثين.

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

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

اختصار الكسر يستعمل القاسم دون تغيير قيمته

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

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

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

323/187 = (323÷17)/(187÷17) = 19/11

الترتيب والإشارات وحالة الصفر

إذا عرض السؤال المئة والسبعة والثمانين قبل الثلاثمئة والثلاثة والعشرين، يمكننا ترتيب الأكبر أولًا عند بدء هذا الإجراء. هذا تبديل ترتيب للزوج لا تغيير لمجموعة قواسمه المشتركة. ونركز على القواسم الموجبة، لذلك لا نجعل ترتيب الطرح في شهادة لاحقة يعطي قاسمًا أكبر سالبًا؛ يمكن أن تظهر معاملات سالبة في التركيب، بينما القاسم الذي نريد تعريفه يبقى موجبًا في حالتنا.

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

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

راجع الحساب والبرهان كلًا بسؤاله

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

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

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

المصادر ومتابعة القراءة

أُعدّ هذا المقال بصياغة عربية أصلية بالاستناد إلى المصادر أعلاه، وهو مدخل تمهيدي إلى الموضوع. اقرأ منهجية المحتوى وحدوده.