الرياضيات الجامعية — السنة 1 · Bachelor Year 1

6حساب الأعداد الصحيحة

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

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 .

برهان. الوجود. المجموعة $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$ وحيدة — وهي الواقعة المستعملة ضمنًا كلما تلاعبت مسألة نهاية الأسبوع بعبارة «أرقام $n$ في الأساس $p$ ».

6.2 القاسم المشترك الأكبر

مبرهنة 6.4 (الزمر الجزئية للمجموعة $\Z$ ؛ وجود القاسم المشترك الأكبر)

كل زمرة جزئية من $(\Z, +)$ على الصورة $n\Z = \{nk : k \in \Z\}$ من أجل $n \in \N$ وحيد.
من أجل $a, b \in \Z$ غير معدومين معًا، تكون المجموعة $a\Z + b\Z = \{au + bv : u, v \in \Z\}$ زمرةً جزئية من $\Z$ ، ومنه فهي تساوي $d\,\Z$ من أجل $d \in \N^*$ وحيد. وهذا العدد $d$ هو القاسم المشترك الأكبر $\gcd(a, b)$ : فهو يقسم $a$ و $b$ ، وكل قاسم مشترك للعددين $a$ و $b$ يقسم $d$ .

برهان. (1) لتكن $H \subseteq \Z$ زمرةً جزئية (غير خالية ومستقرة بالطرح؛ والتعريف الصوري في الفصل 7، ولا تُستعمل إلا هاتان الخاصيتان). إذا كانت $H = \{0\}$ فخذ $n = 0$ . وإلا احتوت $H$ عنصرًا غير معدوم ومقابله، ومنه أصغر عنصر موجب تمامًا $n$ . عندئذ $n\Z \subseteq H$ . ومن أجل $x \in H$ ، اكتب $x = nq + r$ مع $0 \leq r < n$ (المبرهنة 6.2)؛ عندئذ $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$ ، يقسم $d$ كليهما. وإذا قسم $c$ كلًّا من $a$ و $b$ فإن $c$ يقسم كل $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$ أوليّين فيما بينهما إذا وفقط إذا كان للمعادلة $au + bv = 1$ حلّ.

برهان. $\gcd(a,b) = d \in d\Z = a\Z + b\Z$ . وأمّا التكافؤ: فإذا كان $\gcd(a,b) = 1$ وفّرت متطابقة بيزو الحلّ؛ وبالعكس فإن $au + bv = 1$ يفرض على كل قاسم مشترك للعددين $a, b$ أن يقسم $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$ ؛ ويكون آخر باقٍ غير معدوم هو القاسم المشترك الأكبر. وبإجراء القسمات بالمقلوب (أو بحفظ المعاملات أثناء النزول) نحصل على زوج بيزو $(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$ .

(مبرهنة غاوس المساعدة) إذا كان $a \mid bc$ و $\gcd(a, b) = 1$ فإن $a \mid c$ .
إذا كان $a \mid c$ و $b \mid c$ و $\gcd(a,b) = 1$ فإن $ab \mid c$ .
إذا كان $\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 يكون $\gcd(a, bc) = 1$ . ∎

مثال 6.9 (حلّ معادلة ديوفانتية خطية)

جد كل $(x, y) \in \Z^2$ يحقق $6x + 10y = 4$ . أولًا اختبار الوجود: القاسم $\gcd(6, 10) = 2$ يقسم $4$ ، فتوجد حلول (فلو لم يقسم القاسم المشترك الأكبر الطرفَ الأيمن لكان الطرف الأيسر دائمًا مضاعفًا له ولما وُجد أيّ حلّ). واقسم الجميع: $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، مع قيام مبرهنة غاوس المساعدة بدور الوحدانية.

تعريف 6.10 (المضاعف المشترك الأصغر)

المقدار $\operatorname{lcm}(a, b)$ هو المولّد في $\N$ للزمرة الجزئية $a\Z \cap b\Z$ : فهو مضاعف مشترك للعددين $a$ و $b$ يقسم كل مضاعف مشترك، ومن أجل $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$ ). ولاحظ الطريق العملي: احسب القاسم المشترك الأكبر أولًا (بإقليدس: $84 = 2\times36 + 12$ و $36 = 3\times12$ )، ثم اقسم — ولا تبنِ المضاعف المشترك الأصغر أبدًا بسرد المضاعفات. فكل سؤال عن توافق دوريّ (تروس، واصطفافات كوكبية، والتقاء أعداد عشرية دورية) يُردّ إلى هذا الحساب الواحد.

6.3 الأعداد الأولية

تعريف 6.12

العدد الصحيح $p \geq 2$ يكون أوليًا عندما تكون قواسمه الموجبة الوحيدة هي $1$ و $p$ . ومن أجل $p$ أوليّ و $a \in \Z$ : إمّا $p \mid a$ وإمّا $\gcd(p, a) = 1$ . ومنه (المبرهنة 6.8) تصحّ مبرهنة إقليدس المساعدة: إذا كان $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$ دائمًا قاسمًا أوليًا $\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.

مبرهنة 6.14 (إقليدس)

الأعداد الأولية لا نهائية العدد.

برهان. لكل عدد صحيح $n \geq 2$ قاسم أوليّ: فأصغر قواسمه التي $\geq 2$ أوليّ (إذ إن تعميلًا فعليًا له يُنتج قاسمًا أصغر للعدد $n$ ). ولنفترض الآن أن $p_1, \dots, p_k$ هي كل الأعداد الأولية، ولنضع $N = p_1 p_2 \cdots p_k + 1 \geq 2$ . عندئذ يقسم عدد أوليّ $p_i$ ما العددَ $N$ ؛ لكن $p_i$ يقسم كذلك $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): فالعدد $n = 2$ أوليّ؛ ومن أجل $n > 2$ ، إمّا أن يكون $n$ أوليًا وإمّا $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$ : يقسم العدد الأوليّ $p_1$ المقدارَ $q_1(q_2\cdots q_s)$ ، ومنه بمبرهنة إقليدس المساعدة إمّا $p_1 \mid q_1$ وإمّا $p_1 \mid q_2\cdots q_s$ ؛ وبالتكرار يقسم $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$ . وأمّا صيغة القاسم المشترك الأكبر: فالعدد الصحيح $d = \prod p^{\min}$ يقسم كليهما بالمعيار، و كل قاسم مشترك $c$ يحقق $v_p(c) \leq \min$ لكل $p$ ، ومنه $c \mid d$ ؛ والاستدلال نفسه من أجل المضاعف المشترك الأصغر مع $\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 .

والفكرة النافذة: تصير الأسئلة الجدائية (المربعات والمكعبات والقواسم والقاسم المشترك الأكبر والمضاعف المشترك الأصغر) أسئلةً إحداثيةً إحداثية على متجهات الأسس $(v_2, v_3, v_5, \dots)$ — ووحدانية التفكيك هي العبارة القائلة إن هذه الإحداثيات موجودة ومعرَّفة تعريفًا سليمًا.

6.4 التوافقات

تعريف 6.18

من أجل $n \in \N^*$ : نكتب $a \equiv b \pmod n$ عندما يكون $n \mid a - b$ . وهذه علاقة تكافؤ متوافقة مع الجمع و الضرب: فإذا كان $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 (التحقق بالتسعة)

التوافق مع $+$ و $\times$ أداة تحقق قديمة قدم التجارة. وبما أن $10 \equiv 1 \pmod 9$ ، يكون كل عدد صحيح موافقًا بترديد $9$ لمجموع أرقامه (المبرهن عليه في التمرين 6.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 مصغَّرًا: فتحققات التوافق تدحض ولا تشهد.

قضية 6.20 (قابلية القلب بترديد $n$ )

العدد $a$ قابل للقلب بترديد $n$ (أي $ab \equiv 1 \pmod n$ من أجل $b$ ما) إذا وفقط إذا كان $\gcd(a, n) = 1$ . ويكون المقلوب عندئذ وحيدًا بترديد $n$ ويُحسب بخوارزمية إقليدس الممدَّدة.

برهان. تعني $ab \equiv 1 \pmod n$ أن $ab + nk = 1$ من أجل $k$ ما: وهي علاقة بيزو، وهي موجودة إذا وفقط إذا كان $\gcd(a,n) = 1$ (النتيجة 6.5). والوحدانية: إذا كان $ab \equiv ab' \equiv 1$ فإن $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ . ∎

مثال 6.21 (قلب العدد $7$ بترديد $26$ )

بما أن $\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$ . وبامتلاك المقلوب، يُحلّ أيّ توافق $7x \equiv c \pmod{26}$ بعملية ضرب واحدة: $x \equiv 15c$ . وهذا القلب الآليّ هو حصان العمل في الحساب الترديدي — وفي بروتوكولات المفتاح العام المذكورة في الملاحظة 6.27، حيث تكون الترديدات ذات مئات الأرقام لكن الخوارزمية هي هذه بالضبط.

مثال 6.22 (عندما لا يكون المعامل قابلًا للقلب)

حُلَّ $12x \equiv 8 \pmod{20}$ . هنا $\gcd(12, 20) = 4$ ، فلا يكون $12$ قابلًا للقلب بترديد $20$ — لكن المعادلة تبقى قابلة للمعالجة. يقول التوافق إن $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)$ صفًّا من الحلول — فاقسم كل شيء على القاسم المشترك الأكبر ثم اقلب.

مبرهنة 6.23 (مبرهنة فيرما الصغرى)

ليكن $p$ عددًا أوليًا. لكل $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$ ، يقبل المعامل الثنائي $\binom pk = \frac{p!}{k!(p-k)!}$ القسمة على $p$ : إذ إن $k!\,(p-k)!\, \binom pk = p!$ و $p$ يقسم $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). ∎

مثال 6.24 (عكس مبرهنة فيرما يخفق: العدد $341$ )

تعطي مبرهنة فيرما الصغرى اختبارَ تركيبٍ رخيصًا: فإذا كان $a^{n-1} \not\equiv 1 \pmod n$ من أجل $a$ ما أوليّ مع $n$ فإن $n$ ليس أوليًا. فهل يمكن للاختبار أن يشهد بالأولية كذلك؟ لا: خذ $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. والعبرة: أن الاستلزام وعكسه يحيا كلٌّ منهما حياته (الملاحظة 1.10)، حتى في المبرهنات.

مثال 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 (مزالق شائعة في الحساب)

قسمة توافق. من $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)}$ .
إساءة استعمال مبرهنة إقليدس المساعدة. يستلزم $a \mid bc$ أن $a \mid b$ أو $a \mid c$ من أجل $a$ الأوليّ وحده (أو الأوليّ مع أحد العاملين): إذ $6 \mid 4 \times 9$ ومع ذلك لا يقسم $6$ أيًّا من العاملين.
الأولية فيما بين عددين علاقة لا خاصية. فقولنا «العددان $8$ و $9$ أوليّان فيما بينهما» صحيح وإن لم يكن أيٌّ منهما أوليًا؛ وقولنا «أوليّة مثنى مثنى» أقوى من «أوليّة إجمالًا» (إذ $\gcd(6, 10, 15) = 1$ لكن لا زوج منها أوليّ فيما بين عنصريه).
الأسس لا تحيا بترديد $n$ . في $a^k \bmod n$ ، لا يجوز إرجاع الأسّ إلا بترديد رتبة $a$ (وهي مثلًا $p - 1$ عندما تنطبق مبرهنة فيرما)، ولا بترديد $n$ أبدًا: إذ $2^{10} \bmod 11$ يساوي $1$ ، لا $2^{10 \bmod 11} = 2^{10}$ — والإرجاع الذي يفلح هو الذي يجريه المثال 6.25.

ملاحظة 6.27 (أين يُستعمل هذا الفصل)

هذا الفصل قالبٌ بقدر ما هو صندوق عدّة. فالسلسلة كلها — القسمة الإقليدية، والقاسم المشترك الأكبر، وبيزو، وغاوس، ووحدانية التفكيك — تُعاد حرفيًا من أجل كثيرات الحدود في الفصل 8، حيث تلعب «الدرجة» دور القيمة المطلقة؛ ومقارنة الفصلين جنبًا إلى جنب أحسن سبيل لفهمهما معًا. ويصير حساب التوافقات الحلقةَ $\Z/n\Z$ في الفصل 7، وتكوّن عناصرها القابلة للقلب (القضية 6.20) أول مثال غير بديهي على زمرة العناصر القابلة للقلب. وتعود التقييمات في مسألة نهاية الأسبوع أدناه (صيغة لوجاندر) وتشغّل براهين الصمم في الفصل 10. وخارج هذا المجلد، يكون قلب بيزو بترديد $n$ محركَ التعمية ذات المفتاح العام، وتكون مبرهنة فيرما الصغرى جدَّ اختبارات الأولية التي تشهد بأولية الأعداد الكبيرة المستعملة هناك.

ملاحظة 6.28 (استراحة: $\Z$ بوصفها قالبًا)

تراجع خطوة عن المبرهنات المفردة ولاحظ معمار الفصل: أداة واحدة (القسمة الإقليدية) أنتجت تصنيفًا (الزمر الجزئية $n\Z$ )، الذي أنتج مبرهنة وجود (القاسم المشترك الأكبر وبيزو)، التي أنتجت حساب قابلية القسمة (غاوس)، الذي أنتج وحدانية التفكيك — وكل طابق يستند إلى الطابق الذي تحته لا غير. وسيُشيَّد المبنى نفسه مرتين أخريين في هذا المجلد بطوابق أرضية مختلفة: في الفصل 8، حيث تحلّ القسمة بالدرجة محلّ القسمة بالحجم ويتكرر كل ما فوقها حرفيًا؛ وفي صورة مصغَّرة داخل كل $\Z/n\Z$ في الفصل 7، حيث تصير أسئلة قابلية القلب (وهي القضية 6.20 من هذا الفصل) عباراتٍ بنيوية عن الحلقات والحقول. والتعرف على حجة بوصفها «حجة $\Z$ منقولة» أسرع طريق لتعلّم تلك الفصول — وهو أول مذاق لعادة الجبر الأساسية، أي البرهان على مبرهنات تخصّ بديهيات لا أغراضًا.

الأسطر من 0 إلى 7 من مثلث باسكال مع تظليل المدخلات الفردية: يحوي السطر n منها 2s_2(n)، حيث s_2(n) عدد الآحاد في الكتابة الثنائية للعدد n (الأسطر 1, 2, 4: مدخلتان فرديتان؛ والسطر 7 = (111)_2: الثمانية كلها). والنمط ذاتي التشابه — إذ يولّد كل «مثلث فرديات» نسختين من نفسه — هو مبرهنة كومر في صورة رسم، وهي مبرهن عليها في مسألة نهاية الأسبوع أدناه. — الأسطر من $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)$ بخوارزمية إقليدس، وأعط زوج بيزو له.

حل

حل التمرين 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 ★

برهن على قواعد قابلية القسمة في الأساس $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$ : تعطي خوارزمية إقليدس $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 و $\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)، ومنه $\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)؛ والاختيارات مستقلة، فيوجد $\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$ أوليّين فيما بينهما، يكون لزوج التوافقين $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 (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).

حل

حل التمرين 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)، يكون $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$ ؛ ثم اتبع خوارزمية إقليدس.

حل

حل التمرين 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$ يقسم $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$ ، فهذا هو الباقي الإقليدي.

ومنه فإن خوارزمية إقليدس على الزوج $(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$ عددًا أوليًا. برهن على أن

(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). فازدوج كل $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$ .

برهن على أن $F_0 F_1 \cdots F_{n-1} = F_n - 2$ من أجل $n \geq 1$ (بالاستقراء).
استنتج أن أعداد فيرما أوليّة مثنى مثنى.
استنتج برهانًا ثانيًا، مستقلًا عن المبرهنة 6.14، على أن الأعداد الأولية لا نهائية العدد.

حل

حل التمرين 6.12.

بالاستقراء. من أجل $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 .$
ليكن $m < n$ و $d = \gcd(F_m, F_n)$ . حسب (1)، يقسم $F_m$ العددَ $F_n - 2$ ، ومنه يقسم $d$ كلًّا من $F_n$ و $F_n - 2$ ، فهو يقسم إذن $2$ . لكن كل عدد فيرما فرديّ، ومنه $d = 1$ .
لكل $F_n \geq 3$ قاسم أوليّ $p_n$ (وهي الخطوة الأولى من المبرهنة 6.14). فإذا كان $m \neq n$ كان $p_m \neq p_n$ ، لأن عددًا أوليًا مشتركًا كان سيقسم $\gcd(F_m, F_n) = 1$ . ومنه فالتطبيق $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 — الأجزاء الصحيحة والتقييمات وصيغة لوجاندر.

تسخين: احسب $10!$ واقرأ عدد أصفاره الختامية؛ واحسب $v_2(10!)$ و $v_5(10!)$ مباشرةً من تفكيك كل عامل من $1, 2, \dots, 10$ .
برهن على أنه من أجل $x \in \R$ و $n \in \N^*$ ، $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ .
برهن على أن $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)$ .
بيّن أن عدد مضاعفات $m$ في $\intint1n$ هو $\lfloor n/m \rfloor$ .
برهن على صيغة لوجاندر: من أجل كل $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 — الصورة الرقمية والأصفار الختامية.

احسب $v_5(1000!)$ و $v_2(1000!)$ ، واستنتج: كم صفرًا ينتهي به $1000!$ ؟
برهن على الصورة الرقمية لصيغة لوجاندر: بكتابة $n = \sum_i a_i p^i$ في الأساس $p$ ،

$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$
نتيجتان من أجل $p = 2$ : بيّن أن $2^n$ لا يقسم $n!$ أبدًا، وأن $2^{n-1}$ يقسم $n!$ تحديدًا عندما يكون $n$ قوةً للعدد $2$ .
حاصر النقص: بيّن أن $\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$ واحد عن كل وحدة.
لتكن $Z(n) = v_5(n!)$ عدد الأصفار الختامية للعدد $n!$ . بيّن أن $Z(n) - Z(n-1) = v_5(n)$ ، واستنتج أن $Z$ تتخطى القيمة $5$ كليًا (احسب $Z(24)$ و $Z(25)$ )، و برهن على أنه لا يوجد عاملي ينتهي بخمسة أصفار بالضبط.

الجزء 3 — مبرهنة كومر.

برهن على أن $\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$ .
برهن على مبرهنة كومر: أن الحدّ ذا الرتبة $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$ .)
استنتج أنه من أجل $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، مستعادةً.)
برهن على أن $v_2\binom{2n}n = s_2(n)$ . واستنتج أن المعامل الثنائي المركزي زوجيّ دائمًا، وأن $\binom{2n}n \equiv 2 \pmod 4$ تحديدًا عندما يكون $n$ قوةً للعدد $2$ .
بيّن، باستعمال متطابقة فاندرموند (التمرين 2.7) والسؤال 13، أن $\binom{2p}p \equiv 2 \pmod p$ من أجل كل عدد أوليّ $p$ .
احسب $v_3\binom{1000}{500}$ مرتين: مرةً بمبرهنة كومر (اكتب $500$ في الأساس $3$ وعُدَّ الاحتفاظات في $500 + 500$ )، ومرةً بالصورة الرقمية لصيغة لوجاندر (احسب $s_3(500)$ و $s_3(1000)$ )؛ وتأكّد من أن الاثنتين تعطيان القيمة نفسها.

الجزء 4 — زوجية مثلث باسكال، وحاصر على كثافة الأعداد الأولية.

برهن على المعيار الرقمي: يكون $\binom nk$ فرديًا إذا وفقط إذا كان كل رقم ثنائي من $k$ أصغر من الرقم المقابل من $n$ أو مساويًا له. وصُغ وبرهن على المعيار المماثل للعبارة $p \nmid \binom nk$ في الأساس $p$ .
استنتج أن السطر $n$ من مثلث باسكال يحوي بالضبط $2^{s_2(n)}$ مدخلة فردية؛ وتحقق من ذلك على السطرين $4$ و $5$ .
استنتج أن كل المدخلات الداخلية $\binom nk$ (حيث $0 < k < n$ ) زوجية إذا وفقط إذا كان $n$ قوةً للعدد $2$ .
برهن على أن كل قوة أولية تقسم $\binom{m+n}m$ لا تفوق $m + n$ : أي إذا كان $p^a \mid \binom{m+n}m$ فإن $p^a \leq m + n$ . (كم حدًّا غير معدوم يمكن أن يحوي مجموع السؤال 11؟)
استنتج أن $\binom{2n}n$ يقسم $\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 — توليفة ختامية.

جد أصغر $n$ يجعل $n!$ ينتهي بعدد $2026$ صفرًا على الأقل. (قدّر $Z(n) \approx n/4$ ، ثم عدّل بالصيغة المضبوطة.)
تحقق متقاطع أخير: بيّن أن $7$ لا يقسم $\binom{100}{50}$ ، أولًا بكتابة $50$ في الأساس $7$ و التأكد من أن الجمع $50 + 50$ بلا احتفاظ، ثم بحساب $v_7(100!)$ و $v_7(50!)$ بصيغة لوجاندر.
أين استعملت المسألة بالضبط: (أ) وحدانية التفكيك؛ (ب) تفكيك القسمة الإقليدية $n = p^k n_1 + n_0$ ؛ (ج) حجة عدّ من الفصل 2؟ جملة واحدة لكلٍّ منها.
توليفة، في فقرة قصيرة: تحوّل صيغة لوجاندر سؤالًا في قابلية القسمة إلى حساب أرقام، و تقرأ مبرهنة كومر الجوابَ من احتفاظات عملية جمع واحدة — علّق على هذه الترجمة، وعلى تحققات السؤال 16، وعلى ما يوحي به حاصر السؤال 21 عن الأعداد الأولية (والعبارة الكاملة، وهي مبرهنة الأعداد الأولية، تتجاوز هذا المجلد بكثير؛ والنظير الكثيرحدودي لصندوق عدّة هذا الفصل هو الفصل 8).

حل

حل المسألة 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$ . ثم، بتطبيق صيغة لوجاندر ثلاث مرات،

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$ ، وهي قابلية القسمة المستعملة في المبرهنة 6.23.

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 يكون $\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$ قليلة لما بلغ المضاعف المشترك الأصغر هذا الحجم: فالنموّ الأسّي للمضاعف المشترك الأصغر أثر كمّي على وفرة الأعداد الأولية.

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}$ . وصيغة لوجاندر توافق ذلك: $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$ نفسه وجمعيّته، ومنه صيغة لوجاندر وكل استنتاج في قابلية القسمة (القضية 6.16). (ب) وأنتجت القسمة الإقليدية متطابقة البتر في السؤال 2 والتفكيك $m = p^km_1 + m_0$ الذي يعزل الاحتفاظ (السؤال 12). (ج) وأمّا العدّ: فعدّ مضاعفات $m$ (السؤال 4)، وجداء اختيارات الأرقام (السؤال 18)، وحاصر مجموع السطر $4^n \leq (2n+1)\binom{2n}n$ (السؤال 21) كلها حجج على نهج الفصل 2.

25. تحوّل صيغة لوجاندر السؤال «ما قوة $p$ التي تقسم $n!$ » إلى حساب أرقام في الأساس $p$ ؛ وتضغط مبرهنة كومر الجوابَ من أجل المعاملات الثنائية في احتفاظات عملية جمع واحدة — فقابلية القسمة، وهي في الظاهر خاصية إجمالية لأعداد ضخمة، تُقرأ محليًا رقمًا رقمًا. والسؤال 16 هو النموذج: أربعة احتفاظات، محسوبة باليد، تحدّد القوة المضبوطة للعدد $3$ في عدد ذي مئات الأرقام. ويبيّن السؤال 21 أن دائرة الأفكار نفسها تلامس مياهًا عميقة: فالحاصر الأدنى الأسّي للمقدار $\operatorname{lcm}(1, \dots, 2n)$ خطوة أولى ابتدائية كل الابتدائية نحو مبرهنة الأعداد الأولية، التي يقع برهانها بعيدًا خارج هذا المجلد. وصندوق العدّة كله — القسمة والقاسم المشترك الأكبر والتقييمات — يُعاد من أجل كثيرات الحدود في الفصل 8، حيث يكون نظير نشر الأرقام هو النشر بقوى $(X - a)$ .

المصطلحات المعرَّفة في هذا الفصل

عرض كل المصطلحات (395) في المسرد