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

تُعَدّ القابلية للقسمة نقطة الانطلاق الحقيقية لنظرية الأعداد، لأنها تحوّل الأعداد الصحيحة إلى نظام ذي بنية: إذ لم تعد تنظر إلى الأعداد بوصفها «كميات» فحسب، بل باعتبارها عناصر إمّا أن تتوافق فيما بينها أو لا تتوافق. فمن خلال بنية واحدة فقط، a\mid b، يمكن التعبير عن معايير التبسيط والتحليل إلى عوامل، وصولًا إلى جوهر بعض الإجراءات مثل خوارزمية إقليدس، التي تُمكّن من حساب القواسم المشتركة العظمى في ثوانٍ حتى مع أعداد كبيرة. فضلًا عن ذلك، فهي الأساس التقني لأفكار تظهر مرارًا في الرياضيات التطبيقية وعلوم الحاسوب: الت合同ات، والحسابيات المعيارية، وعمليات التحقق، والشفـرات، و(لاحقًا) علم التشفير. إن إتقان القابلية للقسمة يعني، في جوهره، تعلّم اكتشاف أنماط غير مرئية في الأعداد الصحيحة وتحويلها إلى إجراءات تعمل دائمًا.

أهداف التعلّم
عند الانتهاء من هذا الملخص سيكون الطالب قادرًا على:

1. فهم علاقة القابلية للقسمة بين الأعداد الصحيحة.
2. فهم تعريف القابلية للقسمة وخصائصها.
3. تطوير براهين رياضية لنتائج ونظريات متعلقة بالقابلية للقسمة.

فهرس المحتويات
تعريف القابلية للقسمة
الخصائص الأساسية للقابلية للقسمة
تمارين مقترحة

تعريف القابلية للقسمة

تُصبح الفكرة غير الرسمية «a يقسم b» دقيقة عندما نعبّر عنها بوصفها علاقة بين الأعداد الصحيحة. نقول إن عددًا صحيحًا a يقسم عددًا صحيحًا b إذا أمكن كتابة b على أنه مضاعف دقيق لـ a. يشكّل هذا التعريف أساس بقية هذا الملخص، لأنه يحوّل عبارات من قبيل «يناسب تمامًا» إلى معيار قابل للتحقق.

تعريف. لتكن a,b\in\mathbb{Z} مع a\neq 0. نقول إن a يقسم b، ونكتب a\mid b، إذا وفقط إذا وُجد عدد صحيح k\in\mathbb{Z} بحيث b=ka. وفي غير ذلك نكتب a\nmid b.

a\mid b := (\exists k \in \mathbb{Z})(b = ka )

في هذا التعريف، يُسمّى العدد k خارج القسمة (أو العامل) المرتبط بعلاقة القابلية للقسمة. فعلى سبيل المثال، إن القول 6\mid 42 يكافئ القول بوجود k\in\mathbb{Z} بحيث 42=6k؛ وفي هذه الحالة يكفي أخذ k=7.

من المهم مراعاة

• إن الشرط a\neq 0 شرطٌ أساسي، لأنه لو حاولنا السماح بـ a=0، فإن شرط القابلية للقسمة سيفرض وجود k\in\mathbb{Z} بحيث b=0\cdot k. غير أن 0\cdot k=0 لكل k، ومن ثم تكون الإمكانية الوحيدة هي b=0. في هذه الحالة لا يوجد k «محدد» بالعلاقة، إذ إن أي k\in\mathbb{Z} يحقق 0=0\cdot k. وبعبارة أخرى، فإن التعبير غير الرسمي k=b/a يتحول إلى k=0/0، وهو غير معرّف. ولتفادي هذا الانحلال (حيث تفقد فكرة خارج القسمة معناها)، يُشترط أن يكون a\neq 0. ولهذا السبب لا تُعد العلاقة 0\mid b صالحة.
• في المقابل، فإن a\mid 0 صحيحة لكل a\in\mathbb{Z} مع a\neq 0، إذ يكفي أخذ k=0 فنحصل على 0=a\cdot 0.

وينتج عن هذا التعريف تكافؤ سنستخدمه بصورة متكررة: القول إن a\mid b يكافئ القول إن b ينتمي إلى مجموعة المضاعفات الصحيحة لـ a، أي b\in a\mathbb{Z}، حيث a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\}. وتُبرز هذه الصياغة أن القابلية للقسمة ليست «حيلة»، بل طريقة لوصف مجموعات جزئية عالية التنظيم داخل \mathbb{Z}.

الخصائص الأساسية للقابلية للقسمة

• الانعكاسية: a\mid a.
  البرهان:

  \begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; العنصر المحايد للضرب في $\mathbb{Z}$}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; إدخال الوجودي (1)}\\ (3) &\vdash a \mid a &\text{; تعريف القابلية للقسمة (2)} \\ &\blacksquare & \end{array}

• التعدّي: إذا كان a\mid b و b\mid c، فإن a\mid c.

  البرهان:

  \begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; تعريف القابلية للقسمة، افتراض}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; تعريف القابلية للقسمة، افتراض}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; تجميع الوجودي (1،2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; من (3)}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; من (4)}\\ &\text{جبر داخل المُكمِّم}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; من (5)}\\ &\text{انغلاق $\mathbb{Z}$ تحت الضرب}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; تعريف القابلية للقسمة (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; نقل العطف إلى الدلالة (7)}\\ &\blacksquare& \end{array}

• التوافق مع الجمع والطرح: إذا كان a\mid b و a\mid c، فإن a\mid (b+c) و a\mid (b-c).
  البرهان:

  \begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; تعريف القابلية للقسمة، افتراض}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; تعريف القابلية للقسمة، افتراض}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; تجميع الوجودي (1،2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; من (3)}\\ &\text{جبر داخل المُكمِّم.}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; من (4)}\\ &\text{انغلاق $\mathbb{Z}$ تحت الجمع.}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; تعريف القابلية للقسمة (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; نقل العطف إلى الدلالة (6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; من (3)}\\ &\text{جبر داخل المُكمِّم.}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; من (8)}\\ &\text{انغلاق $\mathbb{Z}$ تحت الطرح.}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; تعريف القابلية للقسمة (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; نقل العطف إلى الدلالة (10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{; إدخال العطف في النتيجة (7،11)}\\ &\blacksquare& \end{array}

• التوافق مع الضرب: إذا كان a\mid b، فإن a\mid (bc) لكل c\in\mathbb{Z}.
  البرهان:

  \begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; تعريف القابلية للقسمة، افتراض}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; من (1)، إدخال الكلي (c اعتباطي)}\\ &\text{جبر في }\mathbb{Z}\text{ داخل المُكمِّم الوجودي.}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; من (2)، الانغلاق: }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; تعريف القابلية للقسمة (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; نقل الدلالة (4)}\\ &\blacksquare& \end{array}

نظرية: حدّ القاسم

إذا كان b\neq 0 و a\mid b، فإن |a|\le |b|.

البرهان:

\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; افتراض} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; تعريف القابلية للقسمة، افتراض} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; خاصية القيمة المطلقة، من (2)} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; من (1،3)} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; من (4)، إذ }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; من (5)} \\ &\blacksquare& \end{array}

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

1. بيّن أن نظرية «حدّ القاسم» ليست صحيحة بالضرورة إذا كان b=0.
2. لنعتبر مجموعة A وعلاقة \rho على هذه المجموعة. إذا كان العنصران x,y\in A بحيث إن x مرتبط بـ y بواسطة \rho، فإننا نكتب x\rho y. وتُقال العلاقة \rho إنها علاقة ترتيب جزئي على A إذا تحققت الشروط التالية:

   a)(\forall x\in A) (x\rho x)،
   b) (\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)
   c) (\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z).

   أثبت أن علاقة القابلية للقسمة هي علاقة ترتيب جزئي على مجموعة الأعداد الصحيحة.

3. أثبت بالاستقراء أنه إذا كان a\mid b_1, a\mid b_2, \cdots, a\mid b_n، فإن a\mid \sum_{i=1}^n b_i x_i لأي مجموعة \{x_i\}_{i=1}^n \subset \mathbb{Z}. كما أثبت أنه إذا كان a\mid b_i، حيث i\in \{1,2,3,\cdots, n\} وكان c يمكن كتابته على شكل تركيب خطي لهذه b_i، فإن a\mid c.
4. إذا كان a\neq 0، بيّن أن المجموعة \{x\;:\; d\mid a\} مجموعة منتهية.
5. لتكن n\in\mathbb{Z}^+ عددًا ثابتًا، ولتكن

   S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}

   أثبت ما يلي:

   1. d\in S \leftrightarrow n/d\in S
   2. إذا رُتّبت عناصر S ترتيبًا تصاعديًا: 1=d_1 \lt d_2 \lt \cdots \lt d_t =n، فإن العناصر المقابلة n\mid d_i مع i \in \{1,2,\cdots, t\} تكون مرتبة ترتيبًا تنازليًا.
6. افترض أن a,b\in\mathbb{Z}^+ و ab=c. أثبت أن \min\{a,b\}\le \sqrt{c}.
7. يُقال عن عدد صحيح n إنه زوجي إذا كان 2\mid n، وفردي إذا كان 2\nmid n. أثبت أن مجموع وفرق:
   1. عددين زوجيين هو عدد زوجي.
   2. عددين فرديين هو عدد زوجي.
   3. عدد زوجي وعدد فردي هو عدد فردي.
8. إذا كان n عددًا فرديًا مختلفًا عن \pm 1، فأثبت أن n لا يمكنه أن يقسم عددين زوجيين متتاليين.
9. لتكن a,b,n\in\mathbb{Z} بحيث |a-b|\lt |n|. أثبت أن n لا يمكنه أن يقسم لا a ولا b.
10. افترض أن a\in\mathbb{Z}. أثبت ما يلي:
    1. (\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1
    2. (\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0
11. لتكن a,b,c\in\mathbb{Z} ولنفرض أن c\neq 0. بيّن أن ac\mid bc يقتضي أن a\mid b.