خوارزمية القسمة

في هذه الحصة سنطوّر خوارزمية القسمة بوصفها المبدأ الذي يضفي الطابع الرسمي، على مستوى الأعداد الصحيحة، على التفكيك الوحيد b=qa+r مع 0\le r<|a|. يُبرهَن أولاً على وجود خارج القسمة والباقي، ثم على وحدانيتهما. وأخيراً، يُفسَّر معنى الباقي، وتُربط النظرية بـخوارزمية القسمة الطويلة بوصفها إجراءً حسابياً، كما يُستبق ارتباطها الطبيعي بالحسابيات المعيارية وتطبيقاتها الحاسوبية.

أهداف التعلّم

عند إتمام هذه الحصة سيكون الطالب قادراً على:

1. تحديد المفاهيم والأدوار الأساسية للقسمة الصحيحة (المقسوم، المقسوم عليه، خارج القسمة، الباقي) ومفهوم القابلية للقسمة بوصفها حالة تامة.
2. شرح صياغة خوارزمية/مبرهنة القسمة الإقليدية، بما في ذلك الشروط التي تحدد الباقي (0\le r<|a|) وغرضها في تجنب الالتباس.
3. تطبيق التفكيك الإقليدي b=qa+r لتحديد q وr في أمثلة ملموسة، مع التحقق من حدّ الباقي.
4. تحليل معالجة الحالات بحسب إشارة المقسوم والمقسوم عليه، وتبرير سبب حفاظ الاصطلاح الإقليدي على باقٍ غير سالب.
5. تنفيذ خوارزمية القسمة الطويلة بوصفها إجراءً آلياً قائماً على التمثيل الموضعي لاستخراج q وr.

فهرس المحتويات:
القسمة والقابلية للقسمة
مبرهنة القسمة الإقليدية
برهان القسمة الإقليدية
تفسير خارج القسمة والباقي
خوارزمية القسمة الطويلة
الخلاصة
تمارين مقترحة ومحلولة

القسمة والقابلية للقسمة

في الحساب، تصف القابلية للقسمة الحالة «التامة»: a\mid b تعني أن b يُكتب تماماً بوصفه مضاعفاً لـa. ومع ذلك، وعلى الرغم من عدم تحقق القابلية للقسمة دائماً بين أي عددين صحيحين، يمكننا مع ذلك أن نتساءل «كم مرة يحتوي عددٌ ما عدداً آخر، وإذا لم يحتوه تماماً، فما الذي يتبقى». في هذا السياق تظهر خوارزمية القسمة، التي تضمن أن أي عدد صحيح b يمكن كتابته على أنه مضاعف لـa مضافاً إليه «باقٍ».

على سبيل المثال، لِنعتبر a=3 وb=16. من الواضح أن 3 لا يقسم 16. ومع ذلك، يمكن إيجاد خارج قسمة وباقٍ لعملية القسمة، لأن

16 = 5\cdot 3 + 1

وبناءً على ذلك، عند قسمة b=16 على a=3 (حيث إن b هو المقسوم وa هو المقسوم عليه)، والمُمثَّلة بـ16/3 أو 16\div 3، نحصل على خارج القسمة q=5 وعلى الباقي r=1. وبوجه عام، يؤكد خوارزمية القسمة أنه لأي عددين صحيحين a (المقسوم عليه) وb (المقسوم) مع a\neq 0، توجد أعداد صحيحة وحيدة q وr بحيث

b=qa+r,\qquad 0\le r<|a|

في هذا المثال، 16=3\cdot 5+1، وتتحقق الشرطية 0\le r<|a| لأن 0\le 1<3. وتمنع هذه الصياغة حدوث اللبس عندما يكون المقسوم عليه (أو المقسوم) سالباً، كما تضمن أن يكون الباقي دائماً غير سالب وأصغر من القيمة المطلقة للمقسوم عليه.

مبرهنة القسمة الإقليدية

إن نتيجة تطبيق خوارزمية القسمة هي ما يُعرف بـالقسمة الإقليدية، وهي تستند إلى النتيجة الآتية.

مبرهنة: لتكن a,b\in\mathbb{Z} مع a\neq 0. عندئذٍ توجد q,r\in\mathbb{Z} وحيدتان بحيث

b=qa+r,\qquad 0\le r<|a|.

يُسمّى العدد الصحيح q خارج القسمة، ويُسمّى r الباقي لقسمة b على a.

برهان القسمة الإقليدية

ينقسم هذا البرهان إلى جزأين: يُبرهَن أولاً على وجود خارج القسمة والباقي؛ ثم يُبيَّن أنهما، بعد إثبات وجودهما، وحيدان.

الوجود

لتكن a,b\in\mathbb{Z} مع a\neq 0، ولْنُعرّف d=|a| بحيث d>0. سنبرهن أولاً حالة b\ge 0، حيث سنُظهر وجود q,r\in\mathbb{Z} يحققان b=dq+r و0\le r<d. ثم سنتناول حالة b<0. وفي الختام، سنستبدل d بـ|a| للحصول على الصيغة b=qa+r مع 0\le r<|a|.

لـb\in\mathbb{Z} مع b\ge 0، نُعرّف القضية P(b): «توجد أعداد صحيحة q,r\in\mathbb{Z} بحيث b=dq+r و0\le r<d». سنبرهن بالاستقراء أن P(b) صحيحة لكل b\ge 0.

حالة الأساس: عندما b=0، بأخذ q=0 وr=0 نحصل على 0=d\cdot 0+0 و0\le 0<d. وعليه فإن P(0) صحيحة.

الخطوة الاستقرائية: ليكن k\ge 0 ولنفرض أن P(k) صحيحة. إذن توجد أعداد صحيحة q,r\in\mathbb{Z} بحيث

k=dq+r,\qquad 0\le r<d.

بإضافة 1 إلى الطرفين نحصل على

k+1=dq+(r+1).

كما أن من 0\le r<d ينتج r+1\le d. وبناءً عليه، لا يمكن إلا أن تقع إحدى الحالتين r+1<d أو r+1=d.

الحالة 1: إذا كان r+1<d، نُعرّف q'=q وr'=r+1. وعندئذٍ

k+1=dq'+r',\qquad 0\le r'<d.

الحالة 2: إذا كان r+1=d، فإن k+1=dq+d=d(q+1)+0. نُعرّف q'=q+1 وr'=0، ويكون

k+1=dq'+r',\qquad 0\le r'<d.

في كلتا الحالتين بنينا عددين صحيحين q',r' يحققان k+1=dq'+r' و0\le r'<d. وعليه فإن P(k+1) صحيحة. وبالاستقراء نستنتج أن P(b) صحيحة لكل b\ge 0.

والآن نعتبر الحالة b<0. عندئذٍ -b>0. بتطبيق النتيجة السابقة على -b، توجد أعداد صحيحة q,r\in\mathbb{Z} بحيث

-b=dq+r,\qquad 0\le r<d.

وبالضرب في -1 نحصل على

b=-dq-r.

إذا كان r=0، فيكفي أخذ q_1=-q وr_1=0، فنحصل على b=dq_1+r_1 و0\le r_1<d.

وإذا كان r>0، نُعرّف q_1=-q-1 وr_1=d-r. وبما أن 0<r<d، فإن 0<d-r<d، أي 0\le r_1<d. إضافةً إلى ذلك،

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

وبناءً على ذلك، لكل b\in\mathbb{Z} توجد أعداد صحيحة q_1,r_1\in\mathbb{Z} بحيث b=dq_1+r_1 و0\le r_1<d.

وأخيراً، لنتذكّر أن d=|a|. فإذا كان a>0، فإن d=a، وتُكتب المساواة b=dq_1+r_1 على صورة b=aq_1+r_1، مع 0\le r_1<|a|.

وإذا كان a<0، فإن d=-a، وعندئذٍ b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1. وبِتعريف q=-q_1 وr=r_1 نحصل على

b=qa+r,\qquad 0\le r<|a|.

وبذلك تثبت وجود q وr لأي a,b\in\mathbb{Z} مع a\neq 0.

الوحدانية

لنفترض وجود q,q',r,r'\in\mathbb{Z} بحيث

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

بطرح العبارتين نحصل على

a(q-q')=r'-r.

وبما أن 0\le r,r'<|a|، فإن |r'-r|<|a|. أما الطرف الأيسر فهو مضاعف لـa، وبالتالي هو أيضاً مضاعف لـ|a|. والمضاعف الصحيح الوحيد لـ|a| الذي تكون قيمته المطلقة أصغر تماماً من |a| هو 0؛ إذ إنه إذا كان |a| m \neq 0 مع m\in\mathbb{Z}، فإن \big| |a| m \big| \ge |a| . وعليه r'-r=0، أي r=r'، وبالتعويض في b=qa+r نستنتج q=q'. ومن ثمّ يكون التفكيك وحيداً.

تفسير خارج القسمة والباقي

• ما معنى «الباقي». إذا كان b=qa+r، فإن r=b-qa هو ما «يتبقى» بعد طرح المضاعف qa من b. وبعبارة أخرى، فإن r هو المتبقي الناتج عن مواءمة b مع شبكة مضاعفات a.
• لماذا يُشترط 0\le r<|a|. من دون هذا الشرط لن يكون الزوج (q,r) وحيداً. ففي الواقع، إذا كان b=qa+r، فإن b=a(q+1)+(r-a) أيضاً. يفرض الشرط 0\le r<|a| على الباقي أن يقع ضمن نافذة ثابتة \{0,1,2,\dots,|a|-1\}، وبذلك يمنع «إعادة تسميات» غير منتهية للعدد نفسه.
• ماذا يحدث إذا كان a سالباً. تظل المبرهنة صحيحة من دون أي تغيير: يبقى الباقي غير سالب ومحدوداً بـ|a|. وهذا أمر مهم لأن بعض لغات البرمجة تستخدم القطع نحو الصفر وقد تُنتج بواقي سالبة، بينما تعتمد الرياضيات الاصطلاح 0\le r<|a| ليكون الباقي ممثلاً «قياسياً».

  إضافةً إلى ذلك، عندما a>0، يتطابق خارج القسمة مع دالة الجزء الصحيح:

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

خوارزمية القسمة الطويلة

انطلاقاً من القسمة الإقليدية يمكن تنفيذ خوارزمية القسمة الطويلة، بالاستفادة من التمثيل الموضعي للأعداد. هذه الخوارزمية هي تقنية حسابية تتيح إيجاد القيم q وr بسرعة عندما نرغب في حساب b\div a مع a,b\in\mathbb{Z} وa\neq 0.

لوصفها، نستعرض أولاً بعض الأمثلة التي توضح العملية والحالات الممكنة أثناء تنفيذ الخوارزمية.

1. لنفترض أننا نريد حساب 57\div 4. هنا 57 هو المقسوم و4 هو المقسوم عليه. لتحقيق ذلك سنجري التسلسل الآتي من العمليات الحسابية:

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{كتابة عملية القسمة.} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{فصل أول بادئة (من اليسار) من المقسوم تكون}\\ &\text{أكبر من أو مساوية للمقسوم عليه، وفي هذه الحالة 5.} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{التفكير في أكبر عدد إذا ضُرب في $4$}\\ &\text{أعطى ناتجاً أصغر من أو مساوياً لـ$5$ وكتابته يمين المساواة. وهو 1.} \\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{ضرب النتيجة في المقسوم عليه وطرحها من القيمة المختارة.} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{اختيار وإنزال الرقم التالي.} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{تكرار التسلسل مع العدد الأخير المتحصل عليه.} \end{array}

   تنتهي الخوارزمية عندما تنفد الأرقام المتبقية لـ«إنزالها»، ويكون الناتج هو خارج القسمة q=14 والباقي r=1. وعلى وجه الخصوص، يكون الباقي دائماً أصغر من المقسوم عليه.

2. لنفترض أننا نريد حساب 132\div 5. لتحقيق ذلك سنجري التسلسل الآتي من العمليات الحسابية:

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{فصل أول بادئة من المقسوم والبحث عن عدد طبيعي}\\ & \text{إذا ضُرب في 5 كان أصغر من أو مساوياً لها. وإذا لم يمكن،}\\ & \text{نضم الرقم التالي حتى يصبح ذلك ممكناً.} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{عندما تنجح الخطوة السابقة، نُنفّذ الخوارزمية بصورة اعتيادية.} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. إذا كان للمقسوم عدد أكبر من الأرقام، يُنفَّذ الإجراء بالطريقة نفسها. فعلى سبيل المثال، عند حساب 3521\div 12 نحصل على:

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. إذا كان أحد العددين سالباً، فهناك طريقتان مقبولتان لعرض النتيجة. ومع ذلك، فإن الصيغة القياسية في نظرية الأعداد هي تلك التي يكون فيها الباقي موجباً، ومن ثم متسقة مع القسمة الإقليدية. على سبيل المثال، إذا حسبنا -598\div 21، فنحصل على التطويرات الممكنة الآتية، وكلٌّ منها صحيح بوصفه متطابقة:

   • مع باقٍ سالب: يتم الحصول عليه بإزالة الإشارة في بداية العملية ثم إعادتها في النهاية.

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     ومن هذا نحصل على:

     598 = 21 \times 28 + 10

     ثم إذا ضربنا طرفي المساواة في -1 نحصل على:

     -598 = 21 \times (-28) - 10

     وعليه، في هذا التمثيل يكون ناتج -598\div 21 هو خارج القسمة q=-28 والباقي r=-10.

     وإذا ضربنا مرة أخرى طرفي المساواة في -1 نحصل على:

     598 = (-21)\times(-28) + 10

     وبذلك يكون ناتج 598\div (-21) هو خارج القسمة q=-28 والباقي r=10.

   • مع باقٍ موجب ومتسق مع القسمة الإقليدية: انطلاقاً من التطوير السابق نحصل على:

     -598 = 21 \times (-28) - 10

     ثم بإضافة 0=21-21 إلى الطرف الأيمن من هذه المساواة نحصل على:

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     وعليه، وبالالتزام بالقسمة الإقليدية، فإن نتيجة حساب -598\div 21 هي خارج قسمة q=-29 وباقٍ r=11.

   فيما يتعلّق بما هو اصطلاحي في القسمة الإقليدية، فإن النتيجة ذات الباقي الموجب فقط هي التي تمثّل خارج القسمة والباقي الإقليديين. ومع ذلك، فإن كلا التعبيرين هويتان صحيحتان ويمكن أن يكونا مفيدين في سياقات مختلفة. وعلى الرغم من أن خوارزمية القسمة الطويلة قد تُنتج بواقي سالبة، فإن ذلك يكون عملياً للحصول على النتائج بطريقة آلية وإجراء معالجات جبرية من دون خطوات إضافية. ومن جهة أخرى، فإن النتائج ذات الباقي الموجب، المتسقة مع القسمة الإقليدية، تسمح بتثبيت ممثّل قياسي لكل فئة بواقي (على سبيل المثال، ضمن \{0,1,\dots,n-1\})، مما يسهّل وسم الأعداد الصحيحة بدقة ومن دون لبس. ويجدر التنبيه إلى أن هناك أيضاً اصطلاحات أخرى للممثّلات، مثل البواقي المتماثلة، وهي صالحة بالقدر نفسه متى تم تثبيت القاعدة.

الخلاصة

تضمن خوارزمية القسمة أن كل قسمة صحيحة يمكن التعبير عنها بصورة وحيدة على الشكل b=qa+r مع 0\le r<|a|، وهو ما يحدّد معياراً قياسياً لتفسير خارج القسمة والباقي حتى عند دخول أعداد سالبة. ولا تعدّ خوارزمية القسمة الطويلة سوى تطبيق عملي لهذا التفكيك، قائم على التمثيل الموضعي، وتتيح حساب q وr بطريقة آلية. وأخيراً، فإن هذه الصيغة الإقليدية لا تقتصر على تجنّب الالتباس فحسب، بل ترتبط أيضاً بصورة طبيعية بالحسابيات المعيارية؛ إذ يعمل الباقي r ممثّلاً قياسياً لفئة البواقي للعدد b بترديد a، وهو الأساس للعديد من التقنيات في نظرية الأعداد وفي التطبيقات الحاسوبية التي سيتم تناولها في عروض لاحقة.

تمارين مقترحة ومحلولة

القسمة الإقليدية

1. (محلول) أوجد q وr بحيث

   137 = 9q + r,\qquad 0\le r\lt 9.

   الحل: ابحث عن أكبر عدد إذا ضُرب في 9 لا يتجاوز 137. لدينا 15\times 9 = 135 و16\times 9 = 144، ومن ثم فإن خارج القسمة المطلوب هو q=15. الآن احسب الباقي r=137-9q وتحقّق من أن 0\le r\lt 9. وبإجراء التحقّق نحصل على:

   r=137-9\cdot 15=137-135=2.

   وبالتالي، 137=9\cdot 15+2 مع 0\le 2\lt 9.

2. (محلول) أوجد q وr بحيث

   2025 = 37q + r,\qquad 0\le r\lt 37.

   الحل: ابحث عن أكبر عدد إذا ضُرب في 37 لا يتجاوز 2025. لاحظ أن 37\times 54 = 1998 و37\times 55 = 2035، ومن ثم فإن خارج القسمة المطلوب هو q=54. الآن احسب الباقي r=2025-37q وتحقّق من أن 0\le r\lt 37. وبإجراء التحقّق نحصل على:

   r=2025-37\cdot 54=2025-1998=27.

   وبالتالي، 2025=37\cdot 54+27 مع 0\le 27\lt 37.

3. أوجد q وr بحيث

   745 = 23q + r,\qquad 0\le r\lt 23.

4. أوجد q وr بحيث

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. أوجد q وr بحيث

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. باقٍ مُثبّت والبحث عن أعداد صحيحة. ليكن a=12.

   (أ) صِف مجموعة جميع الأعداد الصحيحة b التي يكون باقِي قسمتها الإقليدية على 12 هو r=5.

   (ب) أوجد أصغر عدد صحيح b\gt 1000 يحقق ما سبق، وحدّد خارج القسمة q الموافق.

خوارزمية القسمة الطويلة

في كل حالة، طبّق خوارزمية القسمة الطويلة لحساب خارج القسمة q والباقي r. وحوّل النتيجة إلى قسمة إقليدية عندما تعطي الخوارزمية باقياً سالباً.

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.