--- title: "حساب الأعداد الصحيحة" book: "الرياضيات الجامعية — السنة 1" subject: math language: ar chapter: 6 exercises: 12 source: https://one-course.com/books/math/3/ar/chapter/6-integer-arithmetic --- # الفصل 6 — حساب الأعداد الصحيحة بدأ الحساب — أي دراسة [قابلية القسمة](#def-b1-arith-divides) في $\Z$ — في مجلد الثانوية. ويعيد هذا الفصل بناءه كاملًا انطلاقًا من القسمة الإقليدية، ببراهين تامة: [القاسم المشترك الأكبر](#thm-b1-arith-gcd) [وخوارزمية إقليدس](#met-b1-arith-euclid)، ومتطابقة بيزو ومبرهنة غاوس المساعدة، [والتفكيك إلى عوامل أولية](#thm-b1-arith-fta)، وحساب التوافقات حتى مبرهنة فيرما الصغرى. وإلى جانب فتنتها الخاصة، هذه المادة هي النموذج الذي يحاكيه [الفصل 8](https://one-course.com/books/math/3/ar/chapter/8-polynomials#ch-b1-poly) من أجل كثيرات الحدود. ## 6.1 قابلية القسمة والقسمة الإقليدية **تعريف 6.1 (قابلية القسمة).** من أجل $a, b \in \Z$، نقول إن $b$ *يقسم* $a$ (ويُكتب $b \mid a$) عندما يكون $a = bq$ من أجل $q \in \Z$ ما. والنتائج الأساسية: إذا كان $b \mid a$ و $b \mid a'$ فإن $b \mid (ua + va')$ لكل $u, v \in \Z$؛ وإذا كان $b \mid a$ و $a \neq 0$ فإن $\abs b \leq \abs a$؛ و $a \mid b$ مع $b \mid a$ يفرضان $b = \pm a$. **مبرهنة 6.2 (القسمة الإقليدية).** لكل $a \in \Z$ وكل $b \in \N^*$، يوجد زوج واحد بالضبط $(q, r) \in \Z \times \N$ يحقق $$ a = bq + r, \qquad 0 \leq r < b . $$ **برهان.** *الوجود.* [المجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $A = \{a - bk : k \in \Z\} \cap \N$ جزء غير خالٍ من $\N$ (خذ $k = -\abs a$: $a + b\abs a \geq a + \abs a \geq 0$). وليكن $r = a - bq$ أصغر عناصرها. فإذا كان $r \geq b$ لكان $r - b = a - b(q+1)$ عنصرًا أصغر من $A$: وهذا تناقض. إذن $0 \leq r < b$. *الوحدانية.* إذا كان $bq + r = bq' + r'$ مع $0 \leq r, r' < b$ فإن $b(q - q') = r' - r$ و $\abs{r' - r} < b$: فمضاعف $b$ في الطرف الأيسر يجب أن يكون $0$، ومنه $q = q'$ و $r = r'$. ∎ **مثال 6.3 (الترقيم الموضعي بالقسمة المتكررة).** اكتب $2026$ في الأساس $7$. اقسم مرارًا على $7$، محتفظًا بالبواقي: $$ 2026 = 7 \times 289 + 3, \quad 289 = 7 \times 41 + 2, \quad 41 = 7 \times 5 + 6, \quad 5 = 7 \times 0 + 5 . $$ وبقراءة البواقي من الأخير إلى الأول: $2026 = (5\,6\,2\,3)_7$. وللتحقق: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14 + 3 = 2026$. ووحدانية القسمة الإقليدية هي بالضبط ما يجعل كل رقم *مفروضًا*: ففي كل خطوة يكون الباقي هو العدد الصحيح الوحيد في $\intint06$ الموافق للقيمة الحالية بترديد $7$، فتكون الكتابة في الأساس $7$ وحيدة — وهي الواقعة المستعملة ضمنًا كلما تلاعبت مسألة نهاية الأسبوع [بعبارة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-statement) «أرقام $n$ في الأساس $p$». ## 6.2 القاسم المشترك الأكبر **مبرهنة 6.4 (الزمر الجزئية للمجموعة Z\ZZ؛ وجود القاسم المشترك الأكبر).** 1. كل زمرة جزئية من $(\Z, +)$ على الصورة $n\Z = \{nk : k \in \Z\}$ من أجل $n \in \N$ وحيد. 2. من أجل $a, b \in \Z$ غير معدومين معًا، تكون [المجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $a\Z + b\Z = \{au + bv : u, v \in \Z\}$ زمرةً جزئية من $\Z$ ، ومنه فهي تساوي $d\,\Z$ من أجل $d \in \N^*$ وحيد. وهذا العدد $d$ هو *القاسم المشترك الأكبر* $\gcd(a, b)$ : فهو [يقسم](#def-b1-arith-divides) $a$ و $b$ ، وكل قاسم مشترك للعددين $a$ و $b$ [يقسم](#def-b1-arith-divides) $d$ . **برهان.** (1) لتكن $H \subseteq \Z$ زمرةً جزئية (غير خالية ومستقرة بالطرح؛ والتعريف الصوري في [الفصل 7](https://one-course.com/books/math/3/ar/chapter/7-algebraic-structures#ch-b1-structures)، ولا تُستعمل إلا هاتان الخاصيتان). إذا كانت $H = \{0\}$ فخذ $n = 0$. وإلا احتوت $H$ عنصرًا غير معدوم ومقابله، ومنه أصغر عنصر موجب تمامًا $n$. عندئذ $n\Z \subseteq H$. ومن أجل $x \in H$، اكتب $x = nq + r$ مع $0 \leq r < n$ ([المبرهنة 6.2](#thm-b1-arith-division))؛ عندئذ $r = x - nq \in H$، وتفرض أصغرية $n$ أن $r = 0$: أي $x \in n\Z$. والوحدانية: $n$ هو أصغر عنصر موجب في $n\Z$. (2) تحتوي $a\Z + b\Z$ العنصرَ $0$ وهي مستقرة بالطرح، فهي إذن $d\Z$ حيث $d \geq 1$ (إذ تحتوي $a$ أو $b$ غير المعدوم). وبما أن $a, b \in d\Z$، [يقسم](#def-b1-arith-divides) $d$ كليهما. وإذا قسم $c$ كلًّا من $a$ و $b$ فإن $c$ [يقسم](#def-b1-arith-divides) كل $au + bv$ — وبوجه خاص $c \mid d$، لأن $d \in a\Z + b\Z$. وهذه هي الخاصية المعلنة (وهي تستلزم $\abs c \leq d$، فيستحق $d$ اسم القاسم المشترك *الأكبر*). ∎ **نتيجة 6.5 (متطابقة بيزو).** من أجل $a, b$ غير معدومين معًا، يوجد $u, v \in \Z$ يحققان $$ au + bv = \gcd(a, b) . $$ وبوجه خاص (الحالة $\gcd(a,b) = 1$، حالة *الأوليّين فيما بينهما*): يكون $a$ و $b$ [أوليّين فيما بينهما](#cor-b1-arith-bezout) إذا وفقط إذا كان للمعادلة $au + bv = 1$ حلّ. **برهان.** $\gcd(a,b) = d \in d\Z = a\Z + b\Z$. وأمّا التكافؤ: فإذا كان $\gcd(a,b) = 1$ وفّرت متطابقة بيزو الحلّ؛ وبالعكس فإن $au + bv = 1$ يفرض على كل قاسم مشترك للعددين $a, b$ أن [يقسم](#def-b1-arith-divides) $1$. ∎ **طريقة 6.6 (خوارزمية إقليدس، الممدَّدة).** لحساب $\gcd(a, b)$ (حيث $a > b > 0$): اقسم $a = bq + r$؛ عندئذ $\gcd(a, b) = \gcd(b, r)$ (فالقواسم المشتركة للزوج $(a,b)$ وللزوج $(b,r)$ تتطابق، لأن $r = a - bq$)؛ وكرّر حتى يصير الباقي $0$؛ ويكون آخر باقٍ غير معدوم هو [القاسم المشترك الأكبر](#thm-b1-arith-gcd). وبإجراء القسمات بالمقلوب (أو بحفظ المعاملات أثناء النزول) نحصل على زوج بيزو $(u, v)$. **مثال 6.7.** $\gcd(120, 23)$: $120 = 5 \times 23 + 5$؛ و $23 = 4 \times 5 + 3$؛ و$5 = 1\times 3 + 2$؛ و $3 = 1 \times 2 + 1$؛ و $2 = 2 \times 1 + 0$. ومنه $\gcd = 1$. وبالمقلوب: $$ \begin{align*} 1 &= 3 - 2 = 3 - (5 - 3) = 2\times 3 - 5 = 2(23 - 4\times 5) - 5 \\ &= 2 \times 23 - 9 \times 5 = 2\times 23 - 9(120 - 5\times 23) = 47 \times 23 - 9 \times 120 . \end{align*} $$ وللتحقق: $47 \times 23 = 1081$ و $9 \times 120 = 1080$. **مبرهنة 6.8 (مبرهنة غاوس المساعدة ونتائجها).** ليكن $a, b, c \in \Z$. 1. (مبرهنة غاوس المساعدة) إذا كان $a \mid bc$ و $\gcd(a, b) = 1$ فإن $a \mid c$ . 2. إذا كان $a \mid c$ و $b \mid c$ و $\gcd(a,b) = 1$ فإن $ab \mid c$ . 3. إذا كان $\gcd(a, b) = \gcd(a, c) = 1$ فإن $\gcd(a, bc) = 1$ . **برهان.** (1) بمتطابقة بيزو: $au + bv = 1$. اضرب في $c$: $acu + bcv = c$. والحدّان كلاهما يقبل القسمة على $a$ (والثاني لأن $a \mid bc$)، ومنه $a \mid c$. (2) اكتب $c = aq$؛ ومن $b \mid aq$ و $\gcd(a, b) = 1$، تعطي النقطة (1) أن $b \mid q$، ومنه $ab \mid aq = c$. (3) لدينا $au + bv = 1$ و $au' + cv' = 1$. اضرب العلاقتين: $$ 1 = (au + bv)(au' + cv') = a\,\bigl(auu' + ucv' + u'bv\bigr) + bc\,(vv') , $$ وهي علاقة بيزو بين $a$ و $bc$: ومنه حسب [النتيجة 6.5](#cor-b1-arith-bezout) يكون $\gcd(a, bc) = 1$. ∎ **مثال 6.9 (حلّ معادلة ديوفانتية خطية).** جد كل $(x, y) \in \Z^2$ يحقق $6x + 10y = 4$. أولًا *اختبار الوجود*: القاسم $\gcd(6, 10) = 2$ [يقسم](#def-b1-arith-divides) $4$، فتوجد حلول (فلو لم [يقسم](#def-b1-arith-divides) [القاسم المشترك الأكبر](#thm-b1-arith-gcd) الطرفَ الأيمن لكان الطرف الأيسر دائمًا مضاعفًا له ولما وُجد أيّ حلّ). واقسم الجميع: $3x + 5y = 2$. والحل الخاص مرئيّ: $(x_0, y_0) = (-1, 1)$. وأمّا العام فاطرح: $3(x + 1) = -5(y - 1)$، ومنه $3 \mid 5(y-1)$، وتعطي مبرهنة غاوس المساعدة (إذ $\gcd(3,5) = 1$) أن $3 \mid y - 1$: أي $y = 1 - 3k$، ثم $x = -1 + 5k$. وبالعكس فكل زوج كهذا يفي بالغرض: $$ (x, y) = (-1 + 5k,\ 1 - 3k), \qquad k \in \Z . $$ والنمط عام: حلّ خاص واحد زائد المضاعفات الصحيحة للمقدار $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — وهي بنية «الخاص زائد المتجانس» نفسها التي في [الفصل 5](https://one-course.com/books/math/3/ar/chapter/5-linear-differential-equations#ch-b1-diffeq)، مع قيام مبرهنة غاوس المساعدة بدور الوحدانية. **تعريف 6.10 (المضاعف المشترك الأصغر).** المقدار $\operatorname{lcm}(a, b)$ هو المولّد في $\N$ للزمرة الجزئية $a\Z \cap b\Z$: فهو مضاعف مشترك للعددين $a$ و $b$ [يقسم](#def-b1-arith-divides) كل مضاعف مشترك، ومن أجل $a, b \in \N^*$، $$ \gcd(a,b) \times \operatorname{lcm}(a,b) = ab \qquad (\text{والبرهان في } \text{التمرين 6.5}). $$ **مثال 6.11 (مسائل التوافق مسائلُ مضاعف مشترك أصغر).** لترسين متعاشقين $84$ و $36$ سنًّا. فبعد كم سنٍّ من الحركة المشتركة يعودان معًا إلى وضعهما الابتدائي؟ يتكرر التشكيل عندما يكون عدد الأسنان المنقضية مضاعفًا مشتركًا للعددين $84$ و $36$؛ وأول مرة هي عند $$ \operatorname{lcm}(84, 36) = \frac{84 \times 36}{\gcd(84, 36)} = \frac{3024}{12} = 252 $$ سنًّا — أي $3$ دورات للترس الكبير و $7$ للترس الصغير ($252/84$ و $252/36$). ولاحظ الطريق العملي: *احسب [القاسم المشترك الأكبر](#thm-b1-arith-gcd) أولًا* (بإقليدس: $84 = 2\times36 + 12$ و$36 = 3\times12$)، ثم اقسم — ولا تبنِ [المضاعف المشترك الأصغر](#def-b1-arith-lcm) أبدًا بسرد المضاعفات. فكل سؤال عن [توافق](#def-b1-arith-congruence) دوريّ (تروس، واصطفافات كوكبية، والتقاء أعداد عشرية دورية) يُردّ إلى هذا الحساب الواحد. ## 6.3 الأعداد الأولية **تعريف 6.12.** العدد الصحيح $p \geq 2$ يكون *أوليًا* عندما تكون قواسمه الموجبة الوحيدة هي $1$ و $p$. ومن أجل $p$ أوليّ و $a \in \Z$: إمّا $p \mid a$ وإمّا $\gcd(p, a) = 1$. ومنه ([المبرهنة 6.8](#thm-b1-arith-gauss)) تصحّ *مبرهنة إقليدس المساعدة*: إذا كان $p \mid ab$ فإن $p \mid a$ أو $p \mid b$. **ملاحظة 6.13 (اختبار الأولية بالقسمة التجريبية).** إذا كان $n = ab$ مع $2 \leq a \leq b$ فإن $a^2 \leq ab = n$، ومنه $a \leq \sqrt n$: أي أن للعدد المركّب $n$ دائمًا قاسمًا [أوليًا](#def-b1-arith-prime) $\leq \sqrt n$. ومنه فلاختبار أولية $n$ يكفي تجريب الأعداد الأولية حتى $\sqrt n$. ومن أجل $n = 271$: لدينا $\sqrt{271} < 17$، و $271$ لا يقبل القسمة على أيّ من $2, 3, 5, 7, 11, 13$ (فهو فرديّ، ومجموع أرقامه $10$، ولا ينتهي بالرقم $0$ ولا بالرقم $5$، و$271 = 7\cdot38 + 5 = 11\cdot24 + 7 = 13\cdot20 + 11$): فهو أوليّ، بعد ستّ قسمات بدل مئتين. والحاجز $\sqrt n$ عتبة حقيقية: فتجاوزه بكفاءة من أجل أعداد ذات مئة رقم يقتضي اختبارات الأولية الحديثة النابتة من [المبرهنة 6.23](#thm-b1-arith-fermat). **مبرهنة 6.14 (إقليدس).** الأعداد الأولية لا نهائية العدد. **برهان.** لكل عدد صحيح $n \geq 2$ قاسم أوليّ: فأصغر قواسمه التي $\geq 2$ أوليّ (إذ إن تعميلًا فعليًا له يُنتج قاسمًا أصغر للعدد $n$). ولنفترض الآن أن $p_1, \dots, p_k$ هي كل الأعداد الأولية، ولنضع $N = p_1 p_2 \cdots p_k + 1 \geq 2$. عندئذ [يقسم](#def-b1-arith-divides) عدد أوليّ $p_i$ ما العددَ $N$؛ لكن $p_i$ [يقسم](#def-b1-arith-divides) كذلك $N - 1 = p_1\cdots p_k$، ومنه $p_i \mid 1$ — وهذا محال. ∎ **مبرهنة 6.15 (المبرهنة الأساسية في الحساب).** كل عدد صحيح $n \geq 2$ جداءُ أعداد أولية، والتفكيك $$ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} \qquad (p_1 < p_2 < \dots < p_k \text{ أوليّة},\ \alpha_i \in \N^*) $$ وحيد. **برهان.** *الوجود* بالاستقراء القوي ([المبرهنة 1.12](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#thm-b1-logic-induction)): فالعدد $n = 2$ أوليّ؛ ومن أجل $n > 2$، إمّا أن يكون $n$ [أوليًا](#def-b1-arith-prime) وإمّا $n = ab$ مع $2 \leq a, b < n$، ويفكّك فرض الاستقراء كلًّا من $a$ و $b$. *الوحدانية.* نفترض $p_1 \cdots p_r = q_1 \cdots q_s$ (والأعداد الأولية مسرودة بتكرار، وليكن $r \leq s$)، ونستقرئ على $r$. فإذا كان $r = 0$ كان الطرف الأيسر $1$، فيُفرض $s = 0$ (لأن جداءً غير خالٍ من أعداد أولية يفوق $1$). ومن أجل $r \geq 1$: [يقسم](#def-b1-arith-divides) العدد الأوليّ $p_1$ المقدارَ $q_1(q_2\cdots q_s)$، ومنه بمبرهنة إقليدس المساعدة إمّا $p_1 \mid q_1$ وإمّا $p_1 \mid q_2\cdots q_s$؛ وبالتكرار [يقسم](#def-b1-arith-divides) $p_1$ عددًا $q_j$ ما. لكن $q_j$ أوليّ و $p_1 \geq 2$: فبالضرورة $p_1 = q_j$. واختصر هذا العامل المشترك (وهذا مشروع: فالحلقة $\Z$ تامة) لتحصل على $$ p_2 \cdots p_r = q_1 \cdots \widehat{q_j} \cdots q_s $$ (والقبعة تشير إلى الحذف)، وهو تساوٍ بين جداءين أقصر؛ ويقول فرض الاستقراء إن القائمتين $p_2, \dots, p_r$ و $q_1, \dots, \widehat{q_j}, \dots, q_s$ تتطابقان بغضّ النظر عن الترتيب، ومنه كذلك القائمتان الأصليتان. وتجمع صورة الأسس الأعدادَ الأولية المتساوية. ∎ **قضية 6.16 (التقييمات).** من أجل $p$ أوليّ و $n \in \N^*$، نكتب $v_p(n)$ للدلالة على أس $p$ في تفكيك $n$ (مع $v_p(n) = 0$ إذا كان $p \nmid n$). عندئذ $$ v_p(mn) = v_p(m) + v_p(n), \qquad m \mid n \iff \forall p,\ v_p(m) \leq v_p(n), $$ $$ v_p\bigl(\gcd(m,n)\bigr) = \min\bigl(v_p(m), v_p(n)\bigr), \qquad v_p\bigl(\operatorname{lcm}(m,n)\bigr) = \max\bigl(v_p(m), v_p(n)\bigr). $$ **برهان.** تصحّ المتطابقة الأولى لأن التفكيكات تتضارب ولأن تفكيك $mn$ وحيد. وإذا كان $m \mid n$ فاكتب $n = mq$ و طبّقها. وبالعكس، إذا كان $v_p(m) \leq v_p(n)$ دائمًا، فإن العدد الصحيح $q = \prod_p p^{\,v_p(n) - v_p(m)}$ يحقق $mq = n$. وأمّا صيغة [القاسم المشترك الأكبر](#thm-b1-arith-gcd): فالعدد الصحيح $d = \prod p^{\min}$ [يقسم](#def-b1-arith-divides) كليهما بالمعيار، و كل قاسم مشترك $c$ يحقق $v_p(c) \leq \min$ لكل $p$، ومنه $c \mid d$؛ والاستدلال نفسه من أجل [المضاعف المشترك الأصغر](#def-b1-arith-lcm) مع $\max$. ∎ **مثال 6.17 (المربعات والمكعبات عبر التقييمات).** العدد الصحيح $n \geq 1$ مربع تامّ إذا وفقط إذا كان كل $v_p(n)$ زوجيًا (فإذا كان $n = m^2$ فإن $v_p(n) = 2v_p(m)$؛ وبالعكس نصّف كل أسّ). وبالمثل من أجل المكعبات مع مضاعفات $3$. ومنه فإن $21168 = 2^4 \times 3^3 \times 7^2$ ليس مربعًا (إذ $v_3 = 3$ فرديّ) ولا مكعبًا (إذ $v_2 = 4$)؛ و أصغر عدد صحيح موجب $m$ يجعل $21168\,m$ مكعبًا يُوجد برفع كل أسّ إلى مضاعف $3$ التالي: $$ m = 2^{6-4} \times 3^{3-3} \times 7^{3-2} = 2^2 \times 7 = 28, \qquad 21168 \times 28 = 2^6\,3^3\,7^3 = (2^2 \times 3 \times 7)^3 = 84^3 . $$ والفكرة النافذة: تصير الأسئلة الجدائية (المربعات والمكعبات والقواسم [والقاسم المشترك الأكبر](#thm-b1-arith-gcd) [والمضاعف المشترك الأصغر](#def-b1-arith-lcm)) أسئلةً *إحداثيةً إحداثية* على متجهات الأسس $(v_2, v_3, v_5, \dots)$ — ووحدانية التفكيك هي [العبارة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-statement) القائلة إن هذه الإحداثيات موجودة ومعرَّفة تعريفًا سليمًا. ## 6.4 التوافقات **تعريف 6.18.** من أجل $n \in \N^*$: نكتب $a \equiv b \pmod n$ عندما يكون $n \mid a - b$. وهذه [علاقة تكافؤ](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-equiv) متوافقة مع الجمع و الضرب: فإذا كان $a \equiv b$ و $a' \equiv b'$ (بترديد $n$) فإن $a + a' \equiv b + b'$ و $aa' \equiv bb'$ و $a^k \equiv b^k$ من أجل $k \in \N$. **مثال 6.19 (التحقق بالتسعة).** [التوافق](#def-b1-arith-congruence) مع $+$ و $\times$ أداة تحقق قديمة قدم التجارة. وبما أن $10 \equiv 1 \pmod 9$، يكون كل عدد صحيح موافقًا بترديد $9$ لمجموع أرقامه (المبرهن عليه في [التمرين 6.2](#exo-b1-arith-2)). وللتحقق من الدعوى $1234 \times 567 = 699\,678$: يعطي مجموعا الأرقام $1234 \equiv 1$ و$567 \equiv 18 \equiv 0 \pmod 9$، ومنه يجب أن يكون الجداء $\equiv 1 \times 0 = 0$؛ وبالفعل $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$. فالتحقق يمرّ (والجداء صحيح في الواقع). ولو أفاد أحدهم بالقيمة $699\,478$ لأدانه مجموع الأرقام $43 \equiv 7 \not\equiv 0$ فورًا. والاختبار أحاديّ الجانب — فهو يمسك الخطأ إلا إذا كان الخطأ نفسه مضاعفًا للعدد $9$ — وهذا بالضبط درس شبه الأولية في [المثال 6.24](#ex-b1-arith-pseudoprime) مصغَّرًا: فتحققات [التوافق](#def-b1-arith-congruence) تدحض ولا تشهد. **قضية 6.20 (قابلية القلب بترديد nnn).** العدد $a$ *قابل للقلب بترديد $n$* (أي $ab \equiv 1 \pmod n$ من أجل $b$ ما) إذا وفقط إذا كان $\gcd(a, n) = 1$. ويكون المقلوب عندئذ وحيدًا بترديد $n$ ويُحسب [بخوارزمية إقليدس](#met-b1-arith-euclid) الممدَّدة. **برهان.** تعني $ab \equiv 1 \pmod n$ أن $ab + nk = 1$ من أجل $k$ ما: وهي علاقة بيزو، وهي موجودة إذا وفقط إذا كان $\gcd(a,n) = 1$ ([النتيجة 6.5](#cor-b1-arith-bezout)). والوحدانية: إذا كان $ab \equiv ab' \equiv 1$ فإن $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$. ∎ **مثال 6.21 (قلب العدد 777 بترديد 262626).** بما أن $\gcd(7, 26) = 1$، يكون صف $7$ قابلًا للقلب بترديد $26$. وبإقليدس الممدَّدة: $$ 26 = 3 \times 7 + 5, \qquad 7 = 1 \times 5 + 2, \qquad 5 = 2 \times 2 + 1 , $$ ثم بالمقلوب: $$ 1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 . $$ ومنه $7 \times (-11) \equiv 1 \pmod{26}$، أي $7^{-1} \equiv -11 \equiv 15 \pmod{26}$؛ وللتحقق: $7 \times 15 = 105 = 4 \times 26 + 1$. وبامتلاك المقلوب، يُحلّ أيّ [توافق](#def-b1-arith-congruence) $7x \equiv c \pmod{26}$ بعملية ضرب واحدة: $x \equiv 15c$. وهذا القلب الآليّ هو حصان العمل في الحساب الترديدي — وفي بروتوكولات المفتاح العام المذكورة في [الملاحظة 6.27](#rem-b1-arith-whereused)، حيث تكون الترديدات ذات مئات الأرقام لكن الخوارزمية هي هذه بالضبط. **مثال 6.22 (عندما لا يكون المعامل قابلًا للقلب).** حُلَّ $12x \equiv 8 \pmod{20}$. هنا $\gcd(12, 20) = 4$، فلا يكون $12$ قابلًا للقلب بترديد $20$ — لكن المعادلة تبقى قابلة للمعالجة. يقول [التوافق](#def-b1-arith-congruence) إن $20 \mid 12x - 8$؛ وبقسمة العلاقة كلها على $4$ (وهو قاسم للمكوّنات الثلاثة)، تكافئ $5 \mid 3x - 2$، أي $$ 3x \equiv 2 \pmod 5 . $$ والآن $\gcd(3, 5) = 1$ و$3^{-1} \equiv 2 \pmod 5$ ($3 \times 2 = 6 \equiv 1$)، ومنه $x \equiv 4 \pmod 5$: فالحلول هي $x \equiv 4, 9, 14, 19 \pmod{20}$ — أي *أربعة* صفوف بترديد $20$، مطابقةً للقاسم المشترك الأكبر. (ولو لم يقبل الطرف الأيمن القسمة على $4$، مثل $12x \equiv 6 \pmod{20}$، لما وُجد أيّ حلّ البتة: فالطرف الأيسر دائمًا $\equiv 0 \pmod 4$.) والشكل العام: $ax \equiv b \pmod n$ قابل للحلّ إذا وفقط إذا كان $\gcd(a, n) \mid b$، ويكون له عندئذ بالضبط $\gcd(a, n)$ صفًّا من الحلول — فاقسم كل شيء على [القاسم المشترك الأكبر](#thm-b1-arith-gcd) ثم اقلب. **مبرهنة 6.23 (مبرهنة فيرما الصغرى).** ليكن $p$ عددًا [أوليًا](#def-b1-arith-prime). لكل $a \in \Z$: $$ a^p \equiv a \pmod p, $$ وإذا كان $p \nmid a$ فإن $a^{p-1} \equiv 1 \pmod p$. **برهان.** أولًا، من أجل $1 \leq k \leq p - 1$، يقبل [المعامل الثنائي](https://one-course.com/books/math/3/ar/chapter/2-counting#def-b1-counting-objects) $\binom pk = \frac{p!}{k!(p-k)!}$ القسمة على $p$: إذ إن $k!\,(p-k)!\, \binom pk = p!$ و $p$ [يقسم](#def-b1-arith-divides) $p!$ لكنه أوليّ مع $k!(p-k)!$ (فكل العوامل $< p$)، ومنه تعطي مبرهنة غاوس المساعدة أن $p \mid \binom pk$. ولنبرهن الآن على $a^p \equiv a$ من أجل $a \in \N$ بالاستقراء. وهي صحيحة من أجل $a = 0$. وإذا كان $a^p \equiv a$ فإن مبرهنة ثنائي الحدّ تعطي $$ (a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \equiv a + 1 \pmod p, $$ إذ تنعدم كل الحدود الوسطى بترديد $p$. ومن أجل $a < 0$، طبّق النتيجة على $-a$ وافصل $p = 2$ (حيث $x \equiv -x$) عن $p$ الفرديّ (حيث $(-a)^p = -a^p$). وأخيرًا، إذا كان $p \nmid a$، فاضرب $a^p \equiv a$ في مقلوب للعدد $a$ بترديد $p$ ([القضية 6.20](#prop-b1-arith-invmod)). ∎ **مثال 6.24 (عكس مبرهنة فيرما يخفق: العدد 341341341).** تعطي مبرهنة فيرما الصغرى اختبارَ *تركيبٍ* رخيصًا: فإذا كان $a^{n-1} \not\equiv 1 \pmod n$ من أجل $a$ ما أوليّ مع $n$ فإن $n$ ليس [أوليًا](#def-b1-arith-prime). فهل يمكن للاختبار أن يشهد بالأولية كذلك؟ لا: خذ $n = 341 = 11 \times 31$، وهو مركّب، و $a = 2$. وبما أن $2^{10} = 1024 = 3 \times 341 + 1$، يكون $$ 2^{10} \equiv 1 \pmod{341} \qquad\Longrightarrow\qquad 2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} : $$ فيجتاز العدد المركّب $341$ اختبار فيرما من أجل الأساس $2$ (وهو أصغر *شبه أوليّ* كهذا). ويكشفه الأساس $3$ (إذ $3^{340} \not\equiv 1$)، ومنه فاختبار الأولية العملي يُجري الاختبار على عدة أسس، مع تحسينات — والنسخ الصناعية من هذه الفكرة هي التي تشهد بأولية الأعداد الكبيرة في [الملاحظة 6.27](#rem-b1-arith-whereused). والعبرة: أن الاستلزام وعكسه يحيا كلٌّ منهما حياته ([الملاحظة 1.10](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#rem-b1-logic-pitfalls))، حتى في المبرهنات. **مثال 6.25 (حسابات توافق عملية).** ما باقي $7^{2026}$ بترديد $11$؟ بمبرهنة فيرما، $7^{10} \equiv 1 \pmod{11}$. وبما أن $2026 = 10 \times 202 + 6$: $$ 7^{2026} \equiv 7^6 = (7^2)^3 = 49^3 \equiv 5^3 = 125 \equiv 4 \pmod{11}. $$ فالباقي هو $4$. والاستراتيجية: أرجِع الأسّ بترديد الرتبة التي توفّرها مبرهنة فيرما، ثم أرجِع القوى الوسيطة في كل خطوة. **ملاحظة 6.26 (مزالق شائعة في الحساب).** 1. *قسمة [توافق](#def-b1-arith-congruence).* من $ac \equiv bc \pmod n$ *لا* يجوز استنتاج $a \equiv b$ إلا إذا كان $\gcd(c, n) = 1$ : إذ $6 \equiv 2 \pmod 4$ لكن $3 \not\equiv 1 \pmod 4$ . والقاعدة العامة الصحيحة تقسم الترديد كذلك: $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ . 2. *إساءة استعمال مبرهنة إقليدس المساعدة.* يستلزم $a \mid bc$ أن $a \mid b$ أو $a \mid c$ من أجل $a$ *الأوليّ* وحده (أو الأوليّ مع أحد العاملين): إذ $6 \mid 4 \times 9$ ومع ذلك لا [يقسم](#def-b1-arith-divides) $6$ أيًّا من العاملين. 3. *الأولية فيما بين عددين علاقة لا خاصية.* فقولنا «العددان $8$ و $9$ [أوليّان فيما بينهما](#cor-b1-arith-bezout) » صحيح وإن لم يكن أيٌّ منهما [أوليًا](#def-b1-arith-prime) ؛ وقولنا «أوليّة مثنى مثنى» أقوى من «أوليّة إجمالًا» (إذ $\gcd(6, 10, 15) = 1$ لكن لا زوج منها أوليّ فيما بين عنصريه). 4. *الأسس لا تحيا بترديد $n$.* في $a^k \bmod n$ ، لا يجوز إرجاع الأسّ إلا بترديد *رتبة* $a$ (وهي مثلًا $p - 1$ عندما تنطبق مبرهنة فيرما)، ولا بترديد $n$ أبدًا: إذ $2^{10} \bmod 11$ يساوي $1$ ، لا $2^{10 \bmod 11} = 2^{10}$ — والإرجاع الذي يفلح هو الذي يجريه [المثال 6.25](#ex-b1-arith-congruences) . **ملاحظة 6.27 (أين يُستعمل هذا الفصل).** هذا الفصل قالبٌ بقدر ما هو صندوق عدّة. فالسلسلة كلها — القسمة الإقليدية، [والقاسم المشترك الأكبر](#thm-b1-arith-gcd)، وبيزو، وغاوس، ووحدانية التفكيك — تُعاد حرفيًا من أجل كثيرات الحدود في [الفصل 8](https://one-course.com/books/math/3/ar/chapter/8-polynomials#ch-b1-poly)، حيث تلعب «الدرجة» دور القيمة المطلقة؛ ومقارنة الفصلين جنبًا إلى جنب أحسن سبيل لفهمهما معًا. ويصير حساب التوافقات الحلقةَ $\Z/n\Z$ في [الفصل 7](https://one-course.com/books/math/3/ar/chapter/7-algebraic-structures#ch-b1-structures)، وتكوّن عناصرها القابلة للقلب ([القضية 6.20](#prop-b1-arith-invmod)) أول مثال غير بديهي على زمرة العناصر القابلة للقلب. وتعود التقييمات في مسألة نهاية الأسبوع أدناه (صيغة لوجاندر) وتشغّل براهين الصمم في [الفصل 10](https://one-course.com/books/math/3/ar/chapter/10-real-numbers#ch-b1-reals). وخارج هذا المجلد، يكون قلب بيزو بترديد $n$ محركَ التعمية ذات المفتاح العام، وتكون مبرهنة فيرما الصغرى جدَّ اختبارات الأولية التي تشهد بأولية الأعداد الكبيرة المستعملة هناك. **ملاحظة 6.28 (استراحة: Z\ZZ بوصفها قالبًا).** تراجع خطوة عن المبرهنات المفردة ولاحظ معمار الفصل: أداة واحدة (القسمة الإقليدية) أنتجت تصنيفًا (الزمر الجزئية $n\Z$)، الذي أنتج مبرهنة وجود ([القاسم المشترك الأكبر](#thm-b1-arith-gcd) وبيزو)، التي أنتجت حساب [قابلية القسمة](#def-b1-arith-divides) (غاوس)، الذي أنتج وحدانية التفكيك — وكل طابق يستند إلى الطابق الذي تحته لا غير. وسيُشيَّد المبنى نفسه مرتين أخريين في هذا المجلد بطوابق أرضية مختلفة: في [الفصل 8](https://one-course.com/books/math/3/ar/chapter/8-polynomials#ch-b1-poly)، حيث تحلّ القسمة بالدرجة محلّ القسمة بالحجم ويتكرر كل ما فوقها *حرفيًا*؛ وفي صورة مصغَّرة داخل كل $\Z/n\Z$ في [الفصل 7](https://one-course.com/books/math/3/ar/chapter/7-algebraic-structures#ch-b1-structures)، حيث تصير أسئلة قابلية القلب (وهي [القضية 6.20](#prop-b1-arith-invmod) من هذا الفصل) عباراتٍ بنيوية عن الحلقات والحقول. والتعرف على حجة بوصفها «حجة $\Z$ منقولة» أسرع طريق لتعلّم تلك الفصول — وهو أول مذاق لعادة الجبر الأساسية، أي البرهان على مبرهنات تخصّ *بديهيات* لا أغراضًا. ![الأسطر من 0 إلى 7 من مثلث باسكال مع تظليل المدخلات الفردية: يحوي السطر n منها 2s_2(n)، حيث s_2(n) عدد الآحاد في الكتابة الثنائية للعدد n (الأسطر 1, 2, 4: مدخلتان فرديتان؛ والسطر 7 = (111)_2: الثمانية كلها). والنمط ذاتي التشابه — إذ يولّد كل «مثلث فرديات» نسختين من نفسه — هو مبرهنة كومر في صورة رسم، وهي مبرهن عليها في مسألة نهاية الأسبوع أدناه.](https://one-course.com/images/onecourse/chapters/math-3/b1-arith/fig-8546c89fa14c.svg) *الأسطر من $0$ إلى $7$ من مثلث باسكال مع تظليل المدخلات *الفردية*: يحوي السطر $n$ منها $2^{s_2(n)}$، حيث $s_2(n)$ عدد الآحاد في الكتابة الثنائية للعدد $n$ (الأسطر $1, 2, 4$: مدخلتان فرديتان؛ والسطر $7 = (111)_2$: الثمانية كلها). والنمط ذاتي التشابه — إذ يولّد كل «مثلث فرديات» نسختين من نفسه — هو مبرهنة كومر في صورة رسم، وهي مبرهن عليها في مسألة نهاية الأسبوع أدناه.* ## 6.5 تمارين **تمرين 6.1 ★.** احسب $\gcd(1\,001, 777)$ [بخوارزمية إقليدس](#met-b1-arith-euclid)، وأعط زوج بيزو له. **حل التمرين 6.1.** $1001 = 1 \times 777 + 224$؛ و$777 = 3 \times 224 + 105$؛ و$224 = 2 \times 105 + 14$؛ و$105 = 7 \times 14 + 7$؛ و $14 = 2 \times 7 + 0$. ومنه $\gcd(1001, 777) = 7$. وبالمقلوب: $$ 7 = 105 - 7 \times 14 = 105 - 7(224 - 2\times 105) = 15 \times 105 - 7 \times 224 $$ $$ = 15(777 - 3\times 224) - 7\times 224 = 15 \times 777 - 52 \times 224 = 15 \times 777 - 52(1001 - 777) = 67 \times 777 - 52 \times 1001 . $$ وللتحقق: $67 \times 777 = 52\,059$ و$52 \times 1001 = 52\,052$؛ والفرق $7$. وزوج بيزو: $(u, v) = (-52, 67)$ من أجل $1001u + 777v = 7$. **تمرين 6.2 ★.** برهن على قواعد [قابلية القسمة](#def-b1-arith-divides) في الأساس $10$: أن العدد الصحيح موافق بترديد $9$ لمجموع أرقامه، وبترديد $11$ للمجموع المتناوب لأرقامه. وما $123\,456\,789$ بترديد $9$ وبترديد $11$؟ **حل التمرين 6.2.** بما أن $10 \equiv 1 \pmod 9$: يكون $10^k \equiv 1$، ومنه $\sum_k d_k 10^k \equiv \sum_k d_k \pmod 9$. وبما أن $10 \equiv -1 \pmod{11}$: يكون $10^k \equiv (-1)^k$، ومنه فالعدد الصحيح موافق للمجموع المتناوب $\sum_k (-1)^k d_k$ بترديد $11$ (بدءًا من رقم *الآحاد* بالإشارة $+$). ومن أجل $123\,456\,789$: مجموع الأرقام $45 \equiv 0 \pmod 9$. والمجموع المتناوب من الآحاد: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$، ومنه فالعدد $\equiv 5 \pmod{11}$. **تمرين 6.3 ★.** حُلَّ في $\Z$: $91x \equiv 1 \pmod{237}$ *(بإقليدس الممدَّدة)*. **حل التمرين 6.3.** بإقليدس: $237 = 2 \times 91 + 55$؛ و$91 = 1 \times 55 + 36$؛ و$55 = 1 \times 36 + 19$؛ و$36 = 1 \times 19 + 17$؛ و $19 = 1 \times 17 + 2$؛ و$17 = 8 \times 2 + 1$. وبالمقلوب: $$ 1 = 17 - 8\times 2 = 17 - 8(19 - 17) = 9\times 17 - 8\times 19 = 9(36 - 19) - 8\times 19 = 9\times 36 - 17\times 19 $$ $$ = 9\times 36 - 17(55 - 36) = 26\times 36 - 17\times 55 = 26(91 - 55) - 17\times 55 = 26\times 91 - 43\times 55 $$ $$ = 26\times 91 - 43(237 - 2\times 91) = 112 \times 91 - 43 \times 237. $$ ومنه $91 \times 112 \equiv 1 \pmod{237}$: فالحلول هي $x \equiv 112 \pmod{237}$. (وللتحقق: $91 \times 112 = 10\,192 = 43 \times 237 + 1$.) **تمرين 6.4 ★.** جد كل الأزواج $(x, y) \in \Z^2$ التي تحقق $17x + 39y = 1$؛ ثم كل الأزواج التي تحقق $17 x + 39 y = 5$. **حل التمرين 6.4.** $\gcd(17, 39) = 1$: تعطي [خوارزمية إقليدس](#met-b1-arith-euclid) $39 = 2\times 17 + 5$ و$17 = 3\times 5 + 2$ و $5 = 2\times 2 + 1$، وبالمقلوب $$ 1 = 5 - 2\times 2 = 5 - 2(17 - 3\times 5) = 7\times 5 - 2\times 17 = 7(39 - 2\times 17) - 2\times 17 = 7\times 39 - 16\times 17 . $$ والحل الخاص $(x_0, y_0) = (-16, 7)$. والحل العام للمعادلة المتجانسة $17x + 39y = 0$: $x = 39k$ و $y = -17k$ (لأن $17 \mid 39y$ و $\gcd(17,39) = 1$ يفرضان $17 \mid y$ — بمبرهنة غاوس المساعدة). ومنه $$ (x, y) = (-16 + 39k,\; 7 - 17k), \qquad k \in \Z . $$ ومن أجل الطرف الأيمن $5$، اضرب الحل الخاص في $5$: $(x, y) = (-80 + 39k,\; 35 - 17k)$ حيث $k \in \Z$. **تمرين 6.5 ★★.** برهن على أنه من أجل $a, b \in \N^*$: $\gcd(a,b) \times \operatorname{lcm}(a,b) = ab$. *(استعمل صيغتَي التقييم في [القضية 6.16](#prop-b1-arith-valuation) و$\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$.)* **حل التمرين 6.5.** من أجل كل عدد أوليّ $p$، مع $\alpha = v_p(a)$ و $\beta = v_p(b)$: $$ v_p\bigl(\gcd(a,b)\bigr) + v_p\bigl(\operatorname{lcm}(a,b)\bigr) = \min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta = v_p(ab) . $$ وعددان صحيحان موجبان لهما التقييم نفسه عند كل عدد أوليّ متساويان ([القضية 6.16](#prop-b1-arith-valuation))، ومنه $\gcd(a,b)\operatorname{lcm}(a,b) = ab$. **تمرين 6.6 ★★.** لتكن $a = 2^{10} \times 3^4 \times 5^2$ و$b = 2^6 \times 3^7 \times 7$. احسب $\gcd(a, b)$ و$\operatorname{lcm}(a,b)$ وعدد القواسم الموجبة للعدد $a$. *(وبرهن على صيغة عدّ القواسم $\prod_i (\alpha_i + 1)$.)* **حل التمرين 6.6.** التقييمات: $\gcd(a, b) = 2^{\min(10,6)} 3^{\min(4,7)} 5^{\min(2,0)} 7^{\min(0,1)} = 2^6\, 3^4 = 5184$؛ و$\operatorname{lcm}(a,b) = 2^{10}\, 3^7\, 5^2\, 7$. وعدّ القواسم: القاسم الموجب للعدد $n = \prod p_i^{\alpha_i}$ هو بالضبط اختيار $\prod p_i^{\beta_i}$ مع $0 \leq \beta_i \leq \alpha_i$ ([القضية 6.16](#prop-b1-arith-valuation))؛ والاختيارات مستقلة، فيوجد $\prod_i (\alpha_i + 1)$ قاسمًا. ومن أجل $a$: $(10+1)(4+1)(2+1) = 165$. **تمرين 6.7 ★★.** برهن على أن $\sqrt p$ أصمّ من أجل كل عدد أوليّ $p$، باستعمال التقييمات: قارن $v_p$ لطرفَي $p q^2 = r^2$. **حل التمرين 6.7.** نفترض $\sqrt p = \frac rq$ حيث $r, q \in \N^*$، أي $p q^2 = r^2$. وبتطبيق $v_p$: يكون $v_p(pq^2) = 1 + 2v_p(q)$ فرديًا، بينما $v_p(r^2) = 2 v_p(r)$ زوجيّ. ولا يمكن لعدد صحيح أن يكون له تقييمان بالعدد $p$ أحدهما فرديّ والآخر زوجيّ: وهذا تناقض. إذن $\sqrt p \notin \Q$. **تمرين 6.8 ★★.** (مسألة البواقي الصينية) جد كل الأعداد الصحيحة $x$ التي تحقق $$ x \equiv 2 \pmod 7, \qquad x \equiv 5 \pmod{11}. $$ وبرهن في الطريق على أنه من أجل $m, n$ [أوليّين فيما بينهما](#cor-b1-arith-bezout)، يكون لزوج التوافقين $x \equiv a \ (m)$ و $x \equiv b\ (n)$ حلٌّ دائمًا، وحيدٌ بترديد $mn$. **حل التمرين 6.8.** *الواقعة العامة.* مع $\gcd(m,n) = 1$، تعطي متطابقة بيزو $mu + nv = 1$. ضع $x_0 = b\,mu + a\,nv$. عندئذ $x_0 \equiv a\,nv \equiv a(1 - mu) \equiv a \pmod m$ وبالمثل $x_0 \equiv b \pmod n$: أي الوجود. وإذا كان $x$ و $x'$ حلّين، قسم $m$ و $n$ الفرقَ $x - x'$، ومنه $mn \mid x - x'$ ([المبرهنة 6.8](#thm-b1-arith-gauss) (2)): أي الوحدانية بترديد $mn$. *وعدديًا:* $m = 7$ و $n = 11$: $7 \times (-3) + 11 \times 2 = 1$. ومنه $x_0 = 5 \times 7 \times (-3) + 2 \times 11 \times 2 = -105 + 44 = -61 \equiv 16 \pmod{77}$. وللتحقق: $16 = 2\times 7 + 2 \equiv 2 \pmod 7$؛ و$16 = 11 + 5 \equiv 5 \pmod{11}$. والحلول: $x \equiv 16 \pmod{77}$. **تمرين 6.9 ★★.** احسب $3^{1000}$ بترديد $7$، والرقمين العشريين الأخيرين من $7^{100}$ *(بترديد $100 = 4 \times 25$: استعمل [التمرين 6.8](#exo-b1-arith-8))*. **حل التمرين 6.9.** بترديد $7$: تعطي مبرهنة فيرما أن $3^6 \equiv 1$، و$1000 = 6 \times 166 + 4$، ومنه $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$. والرقمان الأخيران من $7^{100}$: اعمل بترديد $4$ وبترديد $25$. بترديد $4$: $7 \equiv -1$، ومنه $7^{100} \equiv 1$. وبترديد $25$: $7^2 = 49 \equiv -1$، ومنه $7^4 \equiv 1$ و$7^{100} = (7^4)^{25} \equiv 1$. وبمبرهنة البواقي الصينية ([التمرين 6.8](#exo-b1-arith-8))، يكون $7^{100} \equiv 1 \pmod{100}$: فالرقمان الأخيران هما $01$. **تمرين 6.10 ★★★.** من أجل $m, n \in \N^*$، برهن على أن $\gcd(2^m - 1,\, 2^n - 1) = 2^{\gcd(m,n)} - 1$. *إرشاد: بيّن أولًا أن باقي $2^m - 1$ بترديد $2^n - 1$ هو $2^r - 1$ حيث $r$ باقي $m$ بترديد $n$؛ ثم اتبع [خوارزمية إقليدس](#met-b1-arith-euclid).* **حل التمرين 6.10.** اكتب $m = nq + r$ حيث $0 \leq r < n$. عندئذ $$ 2^m - 1 = 2^r\bigl(2^{nq} - 1\bigr) + 2^r - 1, $$ و $2^n - 1$ [يقسم](#def-b1-arith-divides) $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots + 1)$. ومنه، بترديد $2^n - 1$، يكون $\;2^m - 1 \equiv 2^r - 1$، وبما أن $0 \leq 2^r - 1 < 2^n - 1$، فهذا *هو* الباقي الإقليدي. ومنه فإن [خوارزمية إقليدس](#met-b1-arith-euclid) على الزوج $(2^m - 1, 2^n - 1)$ تحاكي، أسًّا بأسّ، الخوارزمية على $(m, n)$: فكل خطوة قسمة تضع مكان الزوج $(m, n)$ الزوجَ $(n, r)$ في الأعلى وبالزوج $(2^m - 1, 2^n - 1)$ الزوجَ $(2^n - 1, 2^r - 1)$ في الأسفل. والخوارزمية في الأعلى تنتهي عند $\gcd(m,n)$، ومنه تنتهي في الأسفل عند $2^{\gcd(m,n)} - 1$. **تمرين 6.11 ★★★.** (مبرهنة ويلسون) ليكن $p$ عددًا [أوليًا](#def-b1-arith-prime). برهن على أن $$ (p-1)! \equiv -1 \pmod p , $$ بازدواج كل عامل من $(p-1)!$ مع مقلوبه بترديد $p$ و تعيين العوامل المزدوجة مع نفسها (وحُلَّ $x^2 \equiv 1 \pmod p$ أولًا). وتحقق من العكس: إذا كان $n \geq 2$ غير أوليّ فإن $(n-1)! \not\equiv -1 \pmod n$. **حل التمرين 6.11.** حُلَّ أولًا $x^2 \equiv 1 \pmod p$: لدينا $p \mid (x-1)(x+1)$، ومنه بمبرهنة إقليدس المساعدة يكون $x \equiv 1$ أو $x \equiv -1 \pmod p$. وفي الجداء $(p-1)! = 1 \times 2 \times \dots \times (p-1)$، يكون كل عامل $a$ قابلًا للقلب بترديد $p$، ويكون مقلوبه $a^{-1}$ أحد العوامل كذلك ([القضية 6.20](#prop-b1-arith-invmod)). فازدوج كل $a$ مع $a^{-1}$: يكون جداء كل زوج $1$، إلا العوامل المزدوجة مع نفسها (حيث $a = a^{-1}$، أي $a^2 \equiv 1$) فتبقى وحدها — وهي بالضبط $1$ و $p - 1$. ومنه $$ (p-1)! \equiv 1 \times (p - 1) \equiv -1 \pmod p . $$ (ومن أجل $p = 2$: $1! = 1 \equiv -1 \pmod 2$؛ فتنحلّ حجة الازدواج لكن النتيجة تصحّ.) *العكس.* ليكن $n \geq 2$ مركّبًا، $n = ab$ مع $1 < a \leq b < n$. فإذا كان $a < b$، ظهر كلاهما عاملين متمايزين في $(n-1)!$، ومنه $n \mid (n-1)!$ و$(n-1)! \equiv 0 \not\equiv -1$. وإذا كان $a = b$ (أي $n = a^2$): فمن أجل $a \geq 3$ يكون كلٌّ من $a$ و $2a$ $< n$، ومنه $n = a^2 \mid a \times 2a \mid (n-1)!$، والاستنتاج نفسه؛ ومن أجل $n = 4$، $(n-1)! = 6 \equiv 2 \not\equiv -1 \pmod 4$. **تمرين 6.12 ★★★.** (أعداد فيرما) من أجل $n \in \N$، لتكن $F_n = 2^{2^n} + 1$. 1. برهن على أن $F_0 F_1 \cdots F_{n-1} = F_n - 2$ من أجل $n \geq 1$ (بالاستقراء). 2. استنتج أن أعداد فيرما أوليّة مثنى مثنى. 3. استنتج برهانًا ثانيًا، مستقلًا عن [المبرهنة 6.14](#thm-b1-arith-euclidprimes) ، على أن الأعداد الأولية لا نهائية العدد. **حل التمرين 6.12.** 1. بالاستقراء. من أجل $n = 1$: $F_0 = 3 = F_1 - 2 = 5 - 2$. وبافتراض $F_0\cdots F_{n-1} = F_n - 2$: $$F_0 \cdots F_n = (F_n - 2)F_n = \bigl(2^{2^n} - 1\bigr)\bigl(2^{2^n} + 1\bigr) = 2^{2^{n+1}} - 1 = F_{n+1} - 2 .$$ 2. ليكن $m < n$ و $d = \gcd(F_m, F_n)$ . حسب (1)، [يقسم](#def-b1-arith-divides) $F_m$ العددَ $F_n - 2$ ، ومنه [يقسم](#def-b1-arith-divides) $d$ كلًّا من $F_n$ و $F_n - 2$ ، فهو [يقسم](#def-b1-arith-divides) إذن $2$ . لكن كل عدد فيرما فرديّ، ومنه $d = 1$ . 3. لكل $F_n \geq 3$ قاسم أوليّ $p_n$ (وهي الخطوة الأولى من [المبرهنة 6.14](#thm-b1-arith-euclidprimes) ). فإذا كان $m \neq n$ كان $p_m \neq p_n$ ، لأن عددًا [أوليًا](#def-b1-arith-prime) مشتركًا كان سيقسم $\gcd(F_m, F_n) = 1$ . ومنه [فالتطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) $n \mapsto p_n$ متباين من $\N$ في الأعداد الأولية: أي أن الأعداد الأولية لا نهائية العدد. ## 6.6 مسألة: صيغة لوجاندر واحتفاظات كومر **مسألة 6.1.** كم صفرًا ينتهي به التمثيل العشري للعدد $1000!$ — وأعمق من ذلك، ما القوة المضبوطة لعدد أوليّ $p$ التي تقسم $n!$، أو تقسم معاملًا ثنائيًا؟ الجوابان الكاملان جوهرتان من الحساب الابتدائي: *صيغة لوجاندر* $v_p(n!) = \sum_{k\geq1} \lfloor n/p^k \rfloor$، وصورتها الرقمية $v_p(n!) = \frac{n - s_p(n)}{p-1}$، و*مبرهنة كومر*: إذ يعدّ $v_p\binom{m+n}m$ عددَ *الاحتفاظات* عند جمع $m$ و $n$ في الأساس $p$. وتبرهن هذه المسألة على الاثنتين، وتتحقق منهما إحداهما بالأخرى عدديًا، وتجني النتائج الكلاسيكية — الأصفار الختامية، وزوجية مثلث باسكال، وحاصرًا أول في اتجاه مبرهنة الأعداد الأولية. وفي كل ما يلي، $p$ عدد أوليّ، و $\floor{x}$ الجزء الصحيح، و $s_p(n)$ مجموع أرقام $n$ مكتوبًا في الأساس $p$. **الجزء 1 — الأجزاء الصحيحة والتقييمات وصيغة لوجاندر.** 1. تسخين: احسب $10!$ واقرأ عدد أصفاره الختامية؛ واحسب $v_2(10!)$ و $v_5(10!)$ مباشرةً من تفكيك كل عامل من $1, 2, \dots, 10$ . 2. برهن على أنه من أجل $x \in \R$ و $n \in \N^*$ ، $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ . 3. برهن على أن $v_p(a + b) \geq \min\bigl(v_p(a), v_p(b)\bigr)$ لكل $a, b \in \N^*$ ، مع التساوي كلما كان $v_p(a) \neq v_p(b)$ . 4. بيّن أن عدد مضاعفات $m$ في $\intint1n$ هو $\lfloor n/m \rfloor$ . 5. برهن على *صيغة لوجاندر*: من أجل كل $n \in \N^*$، $$v_p(n!) = \sum_{k=1}^{\infty} \Bigl\lfloor \frac{n}{p^k} \Bigr\rfloor$$ (وهو مجموع منتهٍ: إذ تنعدم الحدود بمجرد أن يكون $p^k > n$). *عُدَّ، من أجل كل $k$، عوامل $\intint1n$ التي تقبل القسمة على $p^k$: فيسهم كلٌّ منها بوحدة واحدة بالضبط عن كل مستوى يبلغه.* **الجزء 2 — الصورة الرقمية والأصفار الختامية.** 6. احسب $v_5(1000!)$ و $v_2(1000!)$ ، واستنتج: كم صفرًا ينتهي به $1000!$ ؟ 7. برهن على الصورة الرقمية لصيغة لوجاندر: بكتابة $n = \sum_i a_i p^i$ في الأساس $p$، $$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$$ 8. نتيجتان من أجل $p = 2$ : بيّن أن $2^n$ لا [يقسم](#def-b1-arith-divides) $n!$ أبدًا، وأن $2^{n-1}$ [يقسم](#def-b1-arith-divides) $n!$ تحديدًا عندما يكون $n$ قوةً للعدد $2$ . 9. حاصر النقص: بيّن أن $\frac n{p-1} - \log_p(n) - 1 \leq v_p(n!) < \frac n{p-1}$ ، بحيث يكون $\frac{v_p(n!)}{n} \to \frac1{p-1}$ : أي أنه على المدى الطويل تتراكم نسبة $\frac1{p-1}$ من عامل $p$ واحد عن كل وحدة. 10. لتكن $Z(n) = v_5(n!)$ عدد الأصفار الختامية للعدد $n!$ . بيّن أن $Z(n) - Z(n-1) = v_5(n)$ ، واستنتج أن $Z$ تتخطى القيمة $5$ كليًا (احسب $Z(24)$ و $Z(25)$ )، و برهن على أنه لا يوجد عاملي ينتهي بخمسة أصفار بالضبط. **الجزء 3 — مبرهنة كومر.** 11. برهن على أن $\lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor \in \{0, 1\}$ لكل $x, y \in \R$، و استنتج من صيغة لوجاندر أن $$v_p\binom{m+n}m = \sum_{k\geq1}\Bigl( \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),$$ وهو مجموع حدود يساوي كلٌّ منها $0$ أو $1$. 12. برهن على *مبرهنة كومر* : أن الحدّ ذا الرتبة $k$ من ذلك المجموع يساوي $1$ تحديدًا عندما يُنتج جمع $m$ و $n$ في الأساس $p$ احتفاظًا نحو الموضع $k$ ؛ ومنه فإن $v_p\binom{m+n}m$ هو العدد الكلي للاحتفاظات. *(اكتب $m = p^km_1 + m_0$ و $n = p^kn_1 + n_0$ مع $0 \leq m_0, n_0 < p^k$ وافحص $\lfloor (m_0 + n_0)/p^k \rfloor$.)* 13. استنتج أنه من أجل $0 < j < p^k$: $$v_p\binom{p^k}{j} = k - v_p(j) ,$$ بعدّ الاحتفاظات في الجمع $j + (p^k - j)$. (وبوجه خاص $p \mid \binom p j$ من أجل $0 < j < p$: وهي الخطوة المفتاحية في [المبرهنة 6.23](#thm-b1-arith-fermat)، مستعادةً.) 14. برهن على أن $v_2\binom{2n}n = s_2(n)$ . واستنتج أن [المعامل الثنائي](https://one-course.com/books/math/3/ar/chapter/2-counting#def-b1-counting-objects) المركزي زوجيّ دائمًا، وأن $\binom{2n}n \equiv 2 \pmod 4$ تحديدًا عندما يكون $n$ قوةً للعدد $2$ . 15. بيّن، باستعمال متطابقة فاندرموند ( [التمرين 2.7](https://one-course.com/books/math/3/ar/chapter/2-counting#exo-b1-counting-7) ) والسؤال 13، أن $\binom{2p}p \equiv 2 \pmod p$ من أجل كل عدد أوليّ $p$ . 16. احسب $v_3\binom{1000}{500}$ مرتين: مرةً بمبرهنة كومر (اكتب $500$ في الأساس $3$ وعُدَّ الاحتفاظات في $500 + 500$ )، ومرةً بالصورة الرقمية لصيغة لوجاندر (احسب $s_3(500)$ و $s_3(1000)$ )؛ وتأكّد من أن الاثنتين تعطيان القيمة نفسها. **الجزء 4 — زوجية مثلث باسكال، وحاصر على كثافة الأعداد الأولية.** 17. برهن على المعيار الرقمي: يكون $\binom nk$ *فرديًا* إذا وفقط إذا كان كل رقم ثنائي من $k$ أصغر من الرقم المقابل من $n$ أو مساويًا له. وصُغ وبرهن على المعيار المماثل [للعبارة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-statement) $p \nmid \binom nk$ في الأساس $p$ . 18. استنتج أن السطر $n$ من مثلث باسكال يحوي بالضبط $2^{s_2(n)}$ مدخلة فردية؛ وتحقق من ذلك على السطرين $4$ و $5$ . 19. استنتج أن كل المدخلات الداخلية $\binom nk$ (حيث $0 < k < n$ ) زوجية إذا وفقط إذا كان $n$ قوةً للعدد $2$ . 20. برهن على أن كل قوة أولية تقسم $\binom{m+n}m$ لا تفوق $m + n$ : أي إذا كان $p^a \mid \binom{m+n}m$ فإن $p^a \leq m + n$ . *(كم حدًّا غير معدوم يمكن أن يحوي مجموع السؤال 11؟)* 21. استنتج أن $\binom{2n}n$ [يقسم](#def-b1-arith-divides) $\operatorname{lcm}(1, 2, \dots, 2n)$، واجمع ذلك مع الحاصر الأدنى $\binom{2n}n \geq \frac{4^n}{2n+1}$ (وستبرهن عليه: فالمدخلة المركزية أكبر مدخلات السطر $2n$ التي عددها $2n + 1$) للحصول على $$\operatorname{lcm}(1, \dots, 2n) \geq \frac{4^n}{2n+1} :$$ فالمضاعفات المشتركة للأعداد الصحيحة الأولى تنمو *أسّيًا* — وهي لمحة كمّية أولى عن وفرة الأعداد الأولية. **الجزء 5 — توليفة ختامية.** 22. جد أصغر $n$ يجعل $n!$ ينتهي بعدد $2026$ صفرًا على الأقل. *(قدّر $Z(n) \approx n/4$، ثم عدّل بالصيغة المضبوطة.)* 23. تحقق متقاطع أخير: بيّن أن $7$ *لا* [يقسم](#def-b1-arith-divides) $\binom{100}{50}$ ، أولًا بكتابة $50$ في الأساس $7$ و التأكد من أن الجمع $50 + 50$ بلا احتفاظ، ثم بحساب $v_7(100!)$ و $v_7(50!)$ بصيغة لوجاندر. 24. أين استعملت المسألة بالضبط: (أ) وحدانية التفكيك؛ (ب) تفكيك القسمة الإقليدية $n = p^k n_1 + n_0$ ؛ (ج) حجة عدّ من [الفصل 2](https://one-course.com/books/math/3/ar/chapter/2-counting#ch-b1-counting) ؟ جملة واحدة لكلٍّ منها. 25. توليفة، في فقرة قصيرة: تحوّل صيغة لوجاندر سؤالًا في [قابلية القسمة](#def-b1-arith-divides) إلى حساب أرقام، و تقرأ مبرهنة كومر الجوابَ من احتفاظات عملية جمع واحدة — علّق على هذه الترجمة، وعلى تحققات السؤال 16، وعلى ما يوحي به حاصر السؤال 21 عن الأعداد الأولية ( [والعبارة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-statement) الكاملة، وهي مبرهنة الأعداد الأولية، تتجاوز هذا المجلد بكثير؛ والنظير الكثيرحدودي لصندوق عدّة هذا الفصل هو [الفصل 8](https://one-course.com/books/math/3/ar/chapter/8-polynomials#ch-b1-poly) ). **حل المسألة 6.1.** **1.** $10! = 3\,628\,800$: أي صفران ختاميان. والتقييمات عاملًا عاملًا: تأتي قوى $2$ من $2, 4 = 2^2, 6, 8 = 2^3, 10$، والمجموع $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$؛ وتأتي قوى $5$ من $5$ و $10$: أي $v_5(10!) = 2$. والأصفار الختامية $= \min(v_2, v_5) = 2$، وهذا متسق. **2.** اكتب القسمة الإقليدية $\lfloor x\rfloor = nq + r$ حيث $0 \leq r \leq n - 1$. عندئذ $x = nq + r + \{x\}$ مع $0 \leq r + \{x\} < n$، ومنه $\lfloor x/n \rfloor = q = \bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor$. **3.** ليكن $\alpha = v_p(a) \leq \beta = v_p(b)$ (بالمبادلة عند الحاجة) واكتب $a = p^\alpha a'$ و $b = p^\beta b'$ حيث $p \nmid a', b'$. عندئذ $a + b = p^\alpha\bigl(a' + p^{\beta - \alpha}b'\bigr)$، ومنه $v_p(a + b) \geq \alpha = \min$. وإذا كان $\alpha < \beta$ كان القوس $a' + p^{\beta-\alpha}b' \equiv a' \not\equiv 0 \pmod p$: فيكون التقييم $\alpha$ بالضبط. **4.** مضاعفات $m$ في $\intint1n$ هي $m, 2m, \dots, qm$ حيث $q$ أكبر عدد صحيح يحقق $qm \leq n$، أي $q = \lfloor n/m \rfloor$. **5.** بوحدانية التفكيك، $v_p(n!) = \sum_{j=1}^{n} v_p(j)$. وبعدّ آخر: يسهم كل $j$ بمقدار $v_p(j) = \#\{k \geq 1 : p^k \mid j\}$، ومنه $$ v_p(n!) = \sum_{j=1}^n \#\{k : p^k \mid j\} = \sum_{k\geq1} \#\{j \leq n : p^k \mid j\} = \sum_{k\geq1} \Bigl\lfloor \frac n{p^k} \Bigr\rfloor $$ حسب السؤال 4 — وهي صيغة لوجاندر. والمجموع منتهٍ: إذ تنعدم الحدود التي فيها $p^k > n$. **6.** $v_5(1000!) = 200 + 40 + 8 + 1 = 249$ (بالقسمة على $5, 25, 125, 625$)؛ و$v_2(1000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 994$. وأمّا الأصفار الختامية للعدد $1000!$: فكل صفر يستهلك عاملًا $2$ وعاملًا $5$، ومنه يوجد منها $\min(994, 249) = 249$. **7.** مع $n = \sum_i a_ip^i$، يعطي السؤال 2 أن $\lfloor n/p^k \rfloor = \sum_{i \geq k} a_ip^{i-k}$ (أي ببتر النشر في الأساس $p$). وبالجمع على $k \geq 1$ وبمبادلة المجموعين المنتهيين: $$ v_p(n!) = \sum_{i\geq1} a_i \sum_{k=1}^{i} p^{i-k} = \sum_{i\geq0} a_i\,\frac{p^i - 1}{p - 1} = \frac{n - s_p(n)}{p - 1} . $$ **8.** من أجل $p = 2$: $v_2(n!) = n - s_2(n)$. وبما أن $n \geq 1$ يحقق $s_2(n) \geq 1$، يكون دائمًا $v_2(n!) \leq n - 1 < n$: أي $2^n \nmid n!$. ويكون $v_2(n!) = n - 1$ إذا وفقط إذا كان $s_2(n) = 1$ إذا وفقط إذا كان $n$ قوةً للعدد $2$. **9.** للعدد $n$ عدد $\lfloor \log_p n \rfloor + 1$ من الأرقام في الأساس $p$، وكلٌّ منها لا يفوق $p - 1$، ومنه $1 \leq s_p(n) \leq (p-1)\bigl(\log_p(n) + 1\bigr)$. وبالتعويض في السؤال 7: $$ \frac n{p-1} - \log_p(n) - 1 \;\leq\; v_p(n!) \;<\; \frac n{p-1}, $$ وبالقسمة على $n$: $\frac{v_p(n!)}n \to \frac1{p-1}$. **10.** $Z(n) - Z(n-1) = v_5(n!/(n-1)!) = v_5(n)$: أي أن عدّ الأصفار الختامية يقفز بمقدار $v_5(n)$ عند كل مضاعف للعدد $5$ ويبقى ثابتًا بينها. ولدينا $Z(24) = \lfloor24/5\rfloor = 4$ و$Z(25) = 5 + 1 = 6$: فعند $n = 25$ يقفز العدّ من $4$ إلى $6$ مباشرةً (إذ $v_5(25) = 2$)، وبما أن $Z$ غير متناقصة مع $Z \leq 4$ قبله و $Z \geq 6$ بعده، فلا تُبلغ القيمة $5$ أبدًا: أي لا يوجد عاملي ينتهي بخمسة أصفار بالضبط. **11.** اكتب $x = \lfloor x\rfloor + \{x\}$: عندئذ $\lfloor x + y\rfloor = \lfloor x\rfloor + \lfloor y\rfloor + \lfloor \{x\} + \{y\}\rfloor$، ويجعل $0 \leq \{x\} + \{y\} < 2$ الجزءَ الصحيح الأخير $0$ أو $1$. ثم، [بتطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) صيغة لوجاندر ثلاث مرات، $$ v_p\binom{m+n}m = v_p\bigl((m{+}n)!\bigr) - v_p(m!) - v_p(n!) = \sum_{k\geq1}\Bigl( \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr), $$ وهو مجموع منتهٍ من حدود تساوي $0$ أو $1$ (طبّق الدعوى الأولى على $x = m/p^k$ و $y = n/p^k$). **12.** ثبّت $k \geq 1$ واكتب $m = p^km_1 + m_0$ و$n = p^kn_1 + n_0$ حيث $0 \leq m_0, n_0 < p^k$ (بالقسمة الإقليدية: إذ $m_0$ هو العدد المكوَّن من أرقام $m$ الدنيا $k$). عندئذ $$ \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor - \Bigl\lfloor\frac m{p^k}\Bigr\rfloor - \Bigl\lfloor\frac n{p^k}\Bigr\rfloor = \Bigl\lfloor\frac{m_0 + n_0}{p^k}\Bigr\rfloor , $$ وهو $1$ إذا كان $m_0 + n_0 \geq p^k$ و $0$ فيما عدا ذلك. لكن $m_0 + n_0 \geq p^k$ تقول بالضبط إن جمع أرقام $m$ و $n$ الدنيا $k$ يفيض إلى الموضع $k$ — أي احتفاظًا نحو الموضع $k$ في خوارزمية الجمع المدرسية. وبالجمع على $k$: يكون $v_p\binom{m+n}m$ عدد الاحتفاظات في الجمع $m + n$ في الأساس $p$. (كومر، 1852.) **13.** طبّق مبرهنة كومر مع $m = j$ و $n = p^k - j$، فالمجموع $p^k = (1\underbrace{0\cdots0}_{k})_p$. وليكن $a = v_p(j)$، فتكون أرقام $j$ في الأساس $p$ عند المواضع $0, \dots, a-1$ تساوي $0$ ويكون الرقم عند الموضع $a$ غير معدوم. وأرقام $p^k - j$ تحت الموضع $a$ تساوي $0$ كذلك ($p^k - j = p^a(p^{k-a} - j/p^a)$). وعند الموضع $a$ يجب أن يكون مجموع الرقمين غير المعدومين $p$ (فرقم الناتج $0$): أي احتفاظ واحد؛ وعند كل موضع من $a+1, \dots, k-1$، يكون مجموع الرقمين مع الاحتفاظ الوارد $p$ (ورقم الناتج $0$ من جديد): فينتشر الاحتفاظ. والمجموع: $k - a$ احتفاظًا، ومنه $v_p\binom{p^k}j = k - v_p(j)$. ومن أجل $k = 1$: يكون $v_p\binom pj = 1$ من أجل $0 < j < p$، وهي [قابلية القسمة](#def-b1-arith-divides) المستعملة في [المبرهنة 6.23](#thm-b1-arith-fermat). **14.** بالصورة الرقمية (السؤال 7)، باستعمال $s_2(2n) = s_2(n)$ (بإلحاق رقم صفر): $$ v_2\binom{2n}n = \bigl(2n - s_2(2n)\bigr) - 2\bigl(n - s_2(n)\bigr) = 2s_2(n) - s_2(2n) = s_2(n) \geq 1 : $$ فيكون $\binom{2n}n$ زوجيًا دائمًا، ويكون $v_2 = 1$ (أي $\binom{2n}n \equiv 2 \pmod 4$) تحديدًا عندما يكون $s_2(n) = 1$، أي عندما يكون $n$ قوةً للعدد $2$. **15.** بمتطابقة فاندرموند مع $m = n = k = p$: $\binom{2p}p = \sum_{j=0}^p \binom pj\binom p{p-j} = \sum_{j=0}^p \binom pj^2$. ومن أجل $0 < j < p$ لدينا $p \mid \binom pj$ (السؤال 13)، ومنه $\binom pj^2 \equiv 0 \pmod p$؛ ويعطي الحدّان الطرفيان $1 + 1$: $\binom{2p}p \equiv 2 \pmod p$. **16.** في الأساس $3$: $500 = 486 + 9 + 3 + 2$، والأرقام (من الأدنى إلى الأعلى) $(2, 1, 1, 0, 0, 2)$، ومنه $s_3(500) = 6$؛ و$1000 = 729 + 243 + 27 + 1$، والأرقام $(1, 0, 0, 1, 0, 1, 1)$، ومنه $s_3(1000) = 4$. *بمبرهنة كومر:* اجمع $500 + 500$ في الأساس $3$: الموضع $0$: $2 + 2 = 4$، فالرقم $1$ والاحتفاظ $1$؛ والموضع $1$: $1 + 1 + 1 = 3$، فالرقم $0$ والاحتفاظ $1$؛ والموضع $2$: $1 + 1 + 1 = 3$، فالرقم $0$ والاحتفاظ $1$؛ والموضع $3$: $0 + 0 + 1 = 1$، بلا احتفاظ؛ والموضع $4$: $0$؛ والموضع $5$: $2 + 2 = 4$، فالرقم $1$ والاحتفاظ $1$؛ والموضع $6$: يحطّ الاحتفاظ: فالرقم $1$. أي أربعة احتفاظات: $v_3\binom{1000}{500} = 4$. *وبصيغة لوجاندر:* $v_3(1000!) = \frac{1000 - 4}2 = 498$ و $v_3(500!) = \frac{500 - 6}2 = 247$، ومنه $v_3\binom{1000}{500} = 498 - 2\times247 = 4$. والحسابان متفقان — وأرقام الجمع $(1, 0, 0, 1, 0, 1, 1)$ تعيد إنتاج $1000$، كما يجب. **17.** بمبرهنة كومر (مع $p = 2$ و $m = k$ و $n' = n - k$): يكون $\binom nk$ فرديًا إذا وفقط إذا كان الجمع $k + (n - k)$ في الأساس $2$ بلا احتفاظ، أي إذا وفقط إذا تحققت عند كل موضع العلاقة $k_i + (n - k)_i = n_i$؛ وعندئذ $k_i \leq n_i$ لكل $i$. وبالعكس، إذا كان $k_i \leq n_i$ لكل $i$، كان العدد ذو الأرقام $n_i - k_i$ هو $n - k$ وكان الجمع بلا احتفاظ. والبرهان نفسه في الأساس $p$: يكون $p \nmid \binom nk$ إذا وفقط إذا كان كل رقم من $k$ في الأساس $p$ أصغر من الرقم المقابل من $n$ أو مساويًا له. **18.** بعدّ الأعداد $k \in \intint0n$ التي تخضع أرقامها للشرط $k_i \leq n_i$: يُختار كل رقم من $k$ باستقلال من بين $n_i + 1$ قيمة، فيكون عدد الاختيارات $\prod_i (n_i + 1)$؛ وفي الأساس $2$ يكون هذا $2^{\#\{i : n_i = 1\}} = 2^{s_2(n)}$. والسطر $4 = (100)_2$: أي $2^1 = 2$ مدخلة فردية — وبالفعل ليس في $1, 4, 6, 4, 1$ مدخلات فردية إلا عند الطرفين. والسطر $5 = (101)_2$: أي $2^2 = 4$ — وبالفعل $1, 5, 10, 10, 5, 1$. **19.** تكون كل المدخلات الداخلية زوجية $\iff$ يحوي السطر بالضبط $2$ من المدخلات الفردية (فالطرفان فرديان دائمًا) $\iff 2^{s_2(n)} = 2 \iff s_2(n) = 1 \iff n$ قوةٌ للعدد $2$. **20.** في مجموع السؤال 11، ينعدم الحدّ ذو الرتبة $k$ بمجرد أن يكون $p^k > m + n$ (إذ تتساوى الأجزاء الصحيحة الثلاثة عندئذ، بل إن الأول يكون $0$ عندما $p^k > m+n$؛ وببساطة أكبر كل حدّ يكون $0$). ومنه فإن عدد الحدود غير المعدومة $\lfloor \log_p(m+n)\rfloor$ على الأكثر، وقيمة كلٍّ منها $1$: أي $a = v_p\binom{m+n}m \leq \log_p(m+n)$، أي $p^a \leq m + n$. **21.** من أجل كل عدد أوليّ $p$ لدينا $v_p\bigl(\operatorname{lcm}(1, \dots, 2n)\bigr) = \lfloor\log_p(2n)\rfloor$ (فأكبر قوة للعدد $p$ لا تفوق $2n$ تظهر بين $1, \dots, 2n$). ويعطي السؤال 20 مع $m = n$ أن $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ من أجل كل $p$: ومنه حسب [القضية 6.16](#prop-b1-arith-valuation) يكون $\binom{2n}n \mid \operatorname{lcm}(1, \dots, 2n)$. وأمّا الحجم: فالنسبة $\binom{2n}{k+1}/\binom{2n}k = \frac{2n-k}{k+1} \geq 1$ بالضبط من أجل $k < n$، ومنه فالمدخلة المركزية أكبر مدخلات السطر $2n$ التي عددها $2n + 1$، ومنه $4^n = \sum_k \binom{2n}k \leq (2n+1)\binom{2n}n$. وبالجمع: $$ \operatorname{lcm}(1, \dots, 2n) \geq \binom{2n}n \geq \frac{4^n}{2n + 1} . $$ فلو كانت الأعداد الأولية تحت $2n$ قليلة لما بلغ [المضاعف المشترك الأصغر](#def-b1-arith-lcm) هذا الحجم: فالنموّ الأسّي للمضاعف المشترك الأصغر أثر كمّي على وفرة الأعداد الأولية. **22.** $Z(n) = \sum_k\lfloor n/5^k\rfloor \approx \frac n4$، فاستهدف قربَ $n = 4 \times 2026 = 8104$: $Z(8104) = 1620 + 324 + 64 + 12 + 2 = 2022$. وارتقِ بمضاعفات $5$: $Z(8110) = 2024$ و $Z(8115) = 2025$ و $$ Z(8120) = 1624 + 324 + 64 + 12 + 2 = 2026 . $$ وبما أن $Z$ ثابتة بين مضاعفات $5$ و$Z(8119) = Z(8115) = 2025$، يكون أصغر $n$ ذي $2026$ صفرًا ختاميًا على الأقل هو $n = 8120$. **23.** في الأساس $7$: $50 = 49 + 1$، والأرقام (من الأدنى إلى الأعلى) $(1, 0, 1)$. وبجمع $50 + 50$: الموضع $0$: $1 + 1 = 2 < 7$، بلا احتفاظ؛ والموضع $1$: $0 + 0 = 0$؛ والموضع $2$: $1 + 1 = 2 < 7$، بلا احتفاظ. فالجمع بلا احتفاظ، ومنه بمبرهنة كومر $v_7\binom{100}{50} = 0$: أي $7 \nmid \binom{100}{50}$. وصيغة لوجاندر [توافق](#def-b1-arith-congruence) ذلك: $v_7(100!) = \lfloor 100/7 \rfloor + \lfloor 100/49 \rfloor = 14 + 2 = 16$ و$v_7(50!) = 7 + 1 = 8$، ومنه $v_7\binom{100}{50} = 16 - 2\times8 = 0$. **24.** (أ) تقوم وحدانية التفكيك بأساس تعريف $v_p$ نفسه وجمعيّته، ومنه صيغة لوجاندر وكل استنتاج في [قابلية القسمة](#def-b1-arith-divides) ([القضية 6.16](#prop-b1-arith-valuation)). (ب) وأنتجت القسمة الإقليدية متطابقة البتر في السؤال 2 والتفكيك $m = p^km_1 + m_0$ الذي يعزل الاحتفاظ (السؤال 12). (ج) وأمّا العدّ: فعدّ مضاعفات $m$ (السؤال 4)، وجداء اختيارات الأرقام (السؤال 18)، وحاصر مجموع السطر $4^n \leq (2n+1)\binom{2n}n$ (السؤال 21) كلها حجج على نهج [الفصل 2](https://one-course.com/books/math/3/ar/chapter/2-counting#ch-b1-counting). **25.** تحوّل صيغة لوجاندر السؤال «ما قوة $p$ التي تقسم $n!$» إلى حساب أرقام في الأساس $p$؛ وتضغط مبرهنة كومر الجوابَ من أجل المعاملات الثنائية في احتفاظات عملية جمع واحدة — [فقابلية القسمة](#def-b1-arith-divides)، وهي في الظاهر خاصية إجمالية لأعداد ضخمة، تُقرأ محليًا رقمًا رقمًا. والسؤال 16 هو النموذج: أربعة احتفاظات، محسوبة باليد، تحدّد القوة المضبوطة للعدد $3$ في عدد ذي مئات الأرقام. ويبيّن السؤال 21 أن دائرة الأفكار نفسها تلامس مياهًا عميقة: فالحاصر الأدنى الأسّي للمقدار $\operatorname{lcm}(1, \dots, 2n)$ خطوة أولى ابتدائية كل الابتدائية نحو مبرهنة الأعداد الأولية، التي يقع برهانها بعيدًا خارج هذا المجلد. وصندوق العدّة كله — القسمة [والقاسم المشترك الأكبر](#thm-b1-arith-gcd) والتقييمات — يُعاد من أجل كثيرات الحدود في [الفصل 8](https://one-course.com/books/math/3/ar/chapter/8-polynomials#ch-b1-poly)، حيث يكون نظير نشر الأرقام هو النشر بقوى $(X - a)$.