رياضيات المرحلة الثانوية · Grades 10–12

29الحساب

يدرس الحساب الأعداد الصحيحة: قابلية القسمة، والأعداد الأولية، والبواقي. وقد عُدّ طويلًا أنقى الرياضيات البحتة، وهو اليوم يحمي كل دفعة عبر الإنترنت: فنظام التعمية RSA يقوم على مبرهنات بيزو وغاوس و فيرما المبرهَن عليها في هذا الفصل.

29.1 قابلية القسمة والقسمة الإقليدية

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

ليكن $a, b \in \Z$ . نقول إن $b$ يقسم $a$ ، ويُكتب $b \mid a$ ، إذا وُجد $k \in \Z$ حيث $a = kb$ . ونقول أيضًا إن $a$ مضاعف للعدد $b$ .

قضية 29.2

إذا كان $c \mid a$ و $c \mid b$ ، فإن $c$ يقسم كل تركيب صحيح $au + bv$ (حيث $u, v \in \Z$ ). وإذا كان $a \mid b$ و $b \mid a$ مع $a,b \in \N$ ، فإن $a = b$ . وإذا كان $a \mid b$ و $b \neq 0$ ، فإن $\abs a \leq \abs b$ .

برهان. اكتب $a = kc$ و $b = lc$ : فيكون $au + bv = (ku + lv)c$ . وتنتج النقطتان الأخريان من $\abs{a} = \abs{k}\,\abs{b}$ مع $\abs k \geq 1$ عندما يكون $b = ka \neq 0$ . ∎

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

ليكن $a \in \Z$ و $b \in \N^*$ . يوجد زوج وحيد $(q, r) \in \Z \times \N$ بحيث

a = bq + r \qquad\text{و}\qquad 0 \leq r < b .

ويكون $q$ هو خارج القسمة و $r$ هو الباقي.

برهان. الوجود. لمجموعة مضاعفات $b$ التي لا تتجاوز $a$ عنصر أكبري $bq$ (فهي غير خالية ومحدودة من الأعلى)؛ ضع $r = a - bq$ . وبالأكبرية، $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$ قيمته المطلقة أصغر من $b$ يجب أن يكون $0$ ، إذن $r = r'$ و $q = q'$ . ∎

29.2 الموافقات

تعريف 29.4 (الموافقة)

ليكن $n \in \N^*$ . يكون عددان صحيحان $a, b$ متوافقين بترديد $n$ ، ويُكتب $a \equiv b \pmod n$ ، إذا كان $n \mid (a - b)$ — وبصيغة مكافئة، إذا كان للعددين $a$ و $b$ الباقي نفسه في القسمة الإقليدية على $n$ .

قضية 29.5 (التوافق مع العمليات)

إذا كان $a \equiv b \pmod n$ و $c \equiv d \pmod n$ ، فإن

a + c \equiv b + d, \qquad ac \equiv bd, \qquad a^k \equiv b^k \ (k \in \N) \pmod n .

برهان. يقسم $n$ المقدار $(a-b) + (c-d) = (a+c) - (b+d)$ ، و $ac - bd = a(c - d) + d(a - b)$ مضاعف للعدد $n$ أيضًا. وتنتج قاعدة القوة بالتراجع من قاعدة الجداء. ∎

طريقة 29.6 (حساب القوى بترديد $n$ )

لحساب $a^k \bmod n$ ، ردّ الأساس بترديد $n$ ، ثم ابحث عن قوة صغيرة للعدد $a$ توافق $\pm1$ ، واستعملها لطيّ الأس. فمثلًا $2^{100} \bmod 7$ : بما أن $2^3 = 8 \equiv 1 \pmod 7$ و $100 = 3\times33 + 1$ ، فإن

2^{100} = \left(2^{3}\right)^{33} \times 2 \equiv 1^{33}\times 2 = 2 \pmod 7 .

29.3 القاسم المشترك الأكبر وبيزو وغاوس

تعريف 29.7 (القاسم المشترك الأكبر)

ليكن $a, b$ عددين صحيحين غير معدومين معًا. القاسم المشترك الأكبر $\gcd(a, b)$ هو أكبر عدد صحيح يقسم $a$ و $b$ معًا. وعندما يكون $\gcd(a,b) = 1$ ، يقال إن $a$ و $b$ أوليان فيما بينهما.

قضية 29.8 (خوارزمية إقليدس)

إذا كان $a = bq + r$ (حيث $b \neq 0$ )، فإن $\gcd(a, b) = \gcd(b, r)$ . ومنه فإن تكرار القسمة الإقليدية يحسب $\gcd(a,b)$ : فالقاسم المشترك الأكبر هو آخر باقٍ غير معدوم.

برهان. كل قاسم مشترك للعددين $a$ و $b$ يقسم $r = a - bq$ (القضية 29.2)، ومنه فهو قاسم مشترك للعددين $b$ و $r$ ؛ وبالعكس، لأن $a = bq + r$ . فللزوجين القواسم المشتركة نفسها، إذن القاسم المشترك الأكبر نفسه. وتنتهي الخوارزمية لأن البواقي تكوّن متتالية متناقصة تمامًا من الأعداد الصحيحة غير السالبة. ∎

مثال 29.9

$\gcd(252, 198)$ : $252 = 198 + 54$ ؛ و $198 = 3\times54 + 36$ ؛ و $54 = 36 + 18$ ؛ و $36 = 2 \times 18 + 0$ . ومنه $\gcd(252,198) = 18$ .

مبرهنة 29.10 (مساواة بيزو)

ليكن $a, b$ عددين صحيحين غير معدومين معًا، وليكن $d = \gcd(a,b)$ . يوجد $u, v \in \Z$ بحيث

au + bv = d .

وخاصة، يكون $a$ و $b$ أوليين فيما بينهما إذا وفقط إذا كان $au + bv = 1$ من أجل عددين صحيحين $u, v$ ما.

برهان. شغّل خوارزمية إقليدس بالمقلوب: فكل باقٍ تركيب صحيح للباقيين السابقين، والمعطيان الابتدائيان $a, b$ تركيبان من نفسيهما؛ وبالتعويض النازل، يكون آخر باقٍ غير معدوم $d$ تركيبًا صحيحًا للعددين $a$ و $b$ . (وفي المثال 29.9: $18 = 54 - 36 = 54 - (198 - 3\times54) = 4\times54 - 198 = 4(252 - 198) - 198 = 4\times252 - 5\times198$ .)

وأما التكافؤ: فإذا كان $\gcd(a,b) = 1$ ، أعطت مساواة بيزو $u, v$ ؛ وبالعكس، كل قاسم مشترك للعددين $a$ و $b$ يقسم $au + bv = 1$ ، فيفرض $\gcd(a,b) = 1$ . ∎

مبرهنة 29.11 (مبرهنة غاوس المساعدة)

ليكن $a, b, c \in \Z$ . إذا كان $a \mid bc$ و $\gcd(a, b) = 1$ ، فإن $a \mid c$ .

برهان. تعطي مساواة بيزو $au + bv = 1$ ؛ فاضرب في $c$ : $acu + bcv = c$ . وحدّا الطرف الأيسر مضاعفان للعدد $a$ (والثاني لأن $a \mid bc$ )، ومنه كذلك $c$ . ∎

نتيجة 29.12

إذا كان $a \mid c$ و $b \mid c$ و $\gcd(a,b) = 1$ ، فإن $ab \mid c$ .

برهان. اكتب $c = ak$ . ومن $b \mid ak$ و $\gcd(a,b)=1$ ، تعطي مبرهنة غاوس المساعدة أن $b \mid k$ ، وليكن $k = bl$ ؛ عندئذٍ $c = abl$ . ∎

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

تعريف 29.13 (العدد الأولي)

يكون العدد الصحيح $p \geq 2$ أوليًا إذا كانت قواسمه الموجبة الوحيدة هي $1$ و $p$ .

قضية 29.14

لكل عدد صحيح $n \geq 2$ قاسم أولي؛ وإذا لم يكن $n$ أوليًا، فله قاسم أولي $\leq \sqrt n$ . وإذا قسم عدد أولي $p$ جداءً $ab$ ، فإن $p \mid a$ أو $p \mid b$ (وهي مبرهنة إقليدس المساعدة).

برهان. أصغر قاسم $d \geq 2$ للعدد $n$ أولي (فأي قاسم فعلي للعدد $d$ سيكون قاسمًا أصغر للعدد $n$ ). وإذا كان $n = de$ مركّبًا مع $2 \leq d \leq e$ ، فإن $d^2 \leq de = n$ ، إذن $d \leq \sqrt n$ . وأما مبرهنة إقليدس المساعدة: فإذا كان $p \nmid a$ ، كان $\gcd(p, a) = 1$ (لأن قواسم $p$ الوحيدة هي $1$ و $p$ )، فتعطي مبرهنة غاوس المساعدة أن $p \mid b$ . ∎

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

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

برهان. إذا أُعطيت أي قائمة منتهية $p_1, \dots, p_k$ من الأعداد الأولية، فاعتبر $N = p_1 p_2 \cdots p_k + 1$ . عندئذٍ يقسم عدد أولي $p$ ما العدد $N$ ؛ لكن لا يقسم أي $p_i$ العدد $N$ (فالباقي $1$ )، إذن $p$ عدد أولي ليس في القائمة. فلا قائمة منتهية تستنفد الأعداد الأولية. ∎

مبرهنة 29.16 (المبرهنة الأساسية في الحساب)

كل عدد صحيح $n \geq 2$ جداء أعداد أولية، وهذا التحليل وحيد إلى غاية ترتيب العوامل:

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}, \qquad p_1 < p_2 < \dots < p_r \text{ أعداد أولية},\ \alpha_i \geq 1 .

برهان. الوجود، بالتراجع القوي: فالعدد $n$ الأولي تحليله نفسه؛ وإلا فإن $n = de$ مع $2 \leq d, e < n$ ، ويتحلّل كلاهما بفرضية التراجع. والوحدانية: لنفترض $p_1\cdots p_s = q_1 \cdots q_t$ (أعدادًا أولية، مع السماح بالتكرار). فحسب مبرهنة إقليدس المساعدة، يقسم $p_1$ عددًا ما $q_j$ ، وبما أنه أولي، فإن $p_1 = q_j$ ؛ فاختصر وكرّر. وينطبق التحليلان حدًا بحد. ∎

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

ليكن $p$ عددًا أوليًا وليكن $a \in \Z$ حيث $p \nmid a$ . عندئذٍ

a^{p-1} \equiv 1 \pmod p .

ومن أجل كل $a \in \Z$ (بلا فرض الأولية فيما بينهما)، $a^p \equiv a \pmod p$ .

برهان. اعتبر الأعداد الصحيحة $p - 1$ التالية $a, 2a, 3a, \dots, (p-1)a$ بترديد $p$ . فلا واحد منها $\equiv 0$ (إذ لو كان $p \mid ka$ مع $1 \leq k \leq p-1$ ، لفرضت مبرهنة إقليدس المساعدة أن $p \mid k$ ، وهذا مستحيل)، وهي متمايزة مثنى مثنى بترديد $p$ (إذ لو كان $ka \equiv la$ ، لكان $p \mid (k - l)a$ ، إذن $p \mid k - l$ ، إذن $k = l$ ). ومنه فهي، بترديد $p$ ، الأعداد $1, 2, \dots, p-1$ بترتيب ما. وبضرب كل الموافقات:

a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p .

وبما أن $p$ لا يقسم أيًا من $1, \dots, p-1$ ، فإن الاستعمال المتكرر لمبرهنة إقليدس المساعدة يسمح باختصار $(p-1)!$ ، فيبقى $a^{p-1} \equiv 1$ . وتنتج الصورة الثانية بالضرب في $a$ (وهي بديهية عندما يكون $p \mid a$ ). ∎

مثال 29.18 (تطبيق في التعمية)

تجعل مبرهنة فيرما رفع القوى بترديد $n$ قابلًا للعكس عندما تُختار الأسس اختيارًا مناسبًا — وهذا قلب نظام التعمية RSA. فمع $p, q$ عددين أوليين كبيرين و $n = pq$ ، يُنشَر $n$ وأس $e$ ؛ ويكون التعمية $x \mapsto x^e \bmod n$ . أما فكّ التعمية فيقتضي أسًا $d$ حيث $ed \equiv 1 \pmod{(p-1)(q-1)}$ ، ولا يستطيع حسابه إلا من يعرف $p$ و $q$ — واستعادة $p, q$ من $n$ تعني تحليل عدد طوله مئات الأرقام، وهو ما لا تفعله أي خوارزمية معروفة في زمن معقول.

29.5 تمارين

تمرين 29.1 ★

احسب خارج قسمة وباقي القسمة الإقليدية للعدد $2026$ على $17$ ، وللعدد $-2026$ على $17$ .

حل

حل التمرين 29.1.

$17 \times 119 = 2023$ ، إذن $2026 = 17 \times 119 + 3$ : فخارج القسمة $119$ والباقي $3$ . وأما من أجل $-2026$ : $-2026 = 17\times(-120) + 14$ (وفعلًا $17 \times 120 = 2040$ و $2040 - 2026 = 14$ ): فخارج القسمة $-120$ والباقي $14$ (إذ يجب أن يقع الباقي في $\intco{0}{17}$ ، فهو ليس $-3$ ).

تمرين 29.2 ★

ما باقي $7^{100}$ بترديد $10$ ؟ (أي ما آخر رقم في $7^{100}$ ؟)

حل

حل التمرين 29.2.

بترديد $10$ : $7^2 = 49 \equiv 9 \equiv -1$ . ومنه $7^{100} = \left(7^2\right)^{50} \equiv (-1)^{50} = 1 \pmod{10}$ : فآخر رقم في $7^{100}$ هو $1$ .

تمرين 29.3 ★

باستعمال خوارزمية إقليدس، احسب $\gcd(1071, 462)$ ، وأوجد عددين صحيحين $u, v$ حيث $1071u + 462v = \gcd(1071, 462)$ .

حل

حل التمرين 29.3.

بخوارزمية إقليدس: $1071 = 2\times462 + 147$ ؛ و $462 = 3\times147 + 21$ ؛ و $147 = 7\times21 + 0$ . إذن $\gcd = 21$ .

وبالتعويض بالمقلوب: $21 = 462 - 3\times147 = 462 - 3(1071 - 2\times462) = 7\times462 - 3\times1071$ . ومنه $u = -3$ و $v = 7$ : $1071\times(-3) + 462\times7 = 21$ .

تمرين 29.4 ★

بيّن أنه من أجل كل $n \in \Z$ ، يكون $n^2$ موافقًا $0$ أو $1$ بترديد $4$ . واستنتج أن عددًا صحيحًا $\equiv 3 \pmod 4$ لا يكون أبدًا مجموع مربعين.

حل

حل التمرين 29.4.

كل عدد صحيح $\equiv 0, 1, 2$ أو $3 \pmod 4$ ، وبالتربيع: $0^2 \equiv 0$ و $1^2 \equiv 1$ و $2^2 = 4 \equiv 0$ و $3^2 = 9 \equiv 1$ . إذن $n^2 \equiv 0$ أو $1 \pmod 4$ . ومجموع مربعين يوافق عندئذٍ $0 + 0$ أو $0 + 1$ أو $1 + 1$ ، أي $0$ أو $1$ أو $2 \pmod 4$ — ولا يوافق $3$ أبدًا.

تمرين 29.5 ★★

بيّن أنه من أجل كل $n \in \N$ ، يقبل $n(n+1)(2n+1)$ القسمة على $6$ .

حل

حل التمرين 29.5.

قابلية القسمة على $2$ : من بين $n$ و $n + 1$ ، واحد زوجي. وقابلية القسمة على $3$ : إذا كان $n \equiv 0$ ، فإن $3 \mid n$ ؛ وإذا كان $n \equiv 1 \pmod 3$ ، فإن $2n + 1 \equiv 3 \equiv 0$ ؛ وإذا كان $n \equiv 2$ ، فإن $n + 1 \equiv 0$ . وفي كل الحالات يقسم $3$ الجداء. وبما أن $\gcd(2,3) = 1$ ، تعطي النتيجة 29.12 أن $6 \mid n(n+1)(2n+1)$ . (وهذا يعيد أيضًا البرهان على أن $\frac{n(n+1)(2n+1)}{6}$ ، وهو مجموع مربعات التمرين 20.1، عدد صحيح.)

تمرين 29.6 ★★

حل في $\Z$ الموافقة $5x \equiv 3 \pmod{11}$ . (إرشاد: أوجد مقلوب $5$ بترديد $11$ .)

حل

حل التمرين 29.6.

نبحث عن مقلوب $5$ بترديد $11$ : فبالتجريب (أو بمساواة بيزو)، $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$ . وبضرب الموافقة في $9$ :

x \equiv 9 \times 3 = 27 \equiv 5 \pmod{11}.

والحلول هي الأعداد الصحيحة $x = 5 + 11k$ حيث $k \in \Z$ . (وللتحقق: $5\times5 = 25 \equiv 3 \pmod{11}$ .)

تمرين 29.7 ★★

حل في $\Z \times \Z$ المعادلة الديوفانتية

17x - 40y = 1,

ثم صِف كل حلول $17x - 40y = 6$ .

حل

حل التمرين 29.7.

$\gcd(17, 40) = 1$ ، إذن توجد حلول. وبخوارزمية إقليدس: $40 = 2\times17 + 6$ ؛ و $17 = 2\times6 + 5$ ؛ و $6 = 5 + 1$ . وبالتعويض بالمقلوب: $1 = 6 - 5 = 6 - (17 - 2\times6) = 3\times6 - 17 = 3(40 - 2\times17) - 17 = 3\times40 - 7\times17$ . ومنه $17\times(-7) - 40\times(-3) = 1$ : أي الحل الخاص $(x_0, y_0) = (-7, -3)$ .

والحل العام للمعادلة $17x - 40y = 1$ : بطرح العلاقة الخاصة، $17(x + 7) = 40(y + 3)$ ؛ وبما أن $\gcd(17, 40) = 1$ ، تعطي مبرهنة غاوس المساعدة أن $40 \mid x + 7$ ، إذن $x = -7 + 40k$ ثم $y = -3 + 17k$ حيث $k \in \Z$ (وكلها تتحقق).

وأما من أجل $17x - 40y = 6$ ، فاضرب الحل الخاص في $6$ : $(x_1, y_1) = (-42, -18)$ ، ويعطي الاستدلال نفسه

x = -42 + 40k, \qquad y = -18 + 17k, \qquad k \in \Z .

(فمثلًا $k = 2$ : $x = 38$ و $y = 16$ ؛ وفعلًا $17\times38 - 40\times16 = 646 - 640 = 6$ .)

تمرين 29.8 ★★

بيّن أن $\sqrt2$ عدد أصم، باستعمال وحدانية التحليل إلى عوامل أولية (قارن أس $2$ في طرفي $a^2 = 2b^2$ ).

حل

حل التمرين 29.8.

لنفترض $\sqrt2 = \frac ab$ حيث $a, b \in \N^*$ ؛ عندئذٍ $a^2 = 2b^2$ . وفي تحليل مربع إلى عوامل أولية، يكون كل أس زوجيًا؛ إذن أس $2$ في $a^2$ زوجي، بينما هو فردي في $2b^2$ (فهو أكبر بواحد من عدد زوجي). وتحليلان للعدد نفسه بأسّين مختلفين للعدد $2$ يناقضان الوحدانية في المبرهنة 29.16. ومنه لا يوجد كسر كهذا: $\sqrt2 \notin \Q$ .

تمرين 29.9 ★★★

ليكن $p$ عددًا أوليًا.

بيّن أنه من أجل $1 \leq k \leq p - 1$ ، يقسم $p$ المقدار $\dbinom{p}{k}$ . (إرشاد: استعمل $k\binom pk = p\binom{p-1}{k-1}$ و التمرين 27.7، ومبرهنة غاوس المساعدة.)
استنتج، بالتراجع على $a \geq 0$ ، برهانًا آخر لمبرهنة فيرما الصغرى على الصورة $a^p \equiv a \pmod p$ .

حل

حل التمرين 29.9.

1. من $k\binom pk = p \binom{p-1}{k-1}$ ، يقسم $p$ المقدار $k\binom pk$ . ومن أجل $1 \leq k \leq p-1$ ، يكون $p \nmid k$ ويعطي كون $p$ أوليًا أن $\gcd(p, k) = 1$ ، إذن تعطي مبرهنة غاوس المساعدة أن $p \mid \binom pk$ .

2. بالتراجع على $a$ . من أجل $a = 0$ : $0^p \equiv 0$ . ولنفترض $a^p \equiv a \pmod p$ . فبمبرهنة ثنائي الحد،

(a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \pmod p,

إذ تنعدم كل الحدود الوسطى بترديد $p$ حسب النقطة 1. وبفرضية التراجع، $(a+1)^p \equiv a + 1 \pmod p$ . وهذا يبرهن على أن $a^p \equiv a$ من أجل كل $a \in \N$ ، وتنتج الحالة $a < 0$ بكتابة $a \equiv a + kp$ من أجل ممثل موجب مناسب.

تمرين 29.10 ★★★

(مسألة البواقي الصينية.) أوجد كل الأعداد الصحيحة $n$ التي تحقق

n \equiv 2 \pmod 3, \qquad n \equiv 3 \pmod 5, \qquad n \equiv 2 \pmod 7 .

(إرشاد: حل الشرطين الأولين، ثم أدخل الثالث؛ ومعاملات بيزو تساعد.)

حل

حل التمرين 29.10.

$n \equiv 2 \pmod 3$ و $n \equiv 3 \pmod 5$ : اكتب $n = 2 + 3s$ ؛ عندئذٍ $2 + 3s \equiv 3 \pmod 5$ ، أي $3s \equiv 1 \pmod 5$ . ومقلوب $3$ بترديد $5$ هو $2$ (لأن $3\times2 = 6 \equiv 1$ )، إذن $s \equiv 2 \pmod 5$ ، وليكن $s = 2 + 5t$ ، فيكون $n = 8 + 15t$ : أي إن الشرطين الأولين يعنيان $n \equiv 8 \pmod{15}$ .

وبإضافة $n \equiv 2 \pmod 7$ : $8 + 15t \equiv 2 \pmod 7$ ، و $15 \equiv 1 \pmod 7$ ، إذن $t \equiv -6 \equiv 1 \pmod 7$ ، وليكن $t = 1 + 7u$ . ومنه $n = 23 + 105u$ :

n \equiv 23 \pmod{105}.

(وللتحقق: $23 = 3\times7 + 2 = 5\times4 + 3 = 7\times3 + 2$ .)

29.6 مسألة: الشيفرات السرية وأرقام التحقق

مسألة 29.1

مسألة نهاية الأسبوع — الموافقات تحرس كل رمز شريطي وكل بطاقة ائتمان، ومبرهنة فيرما الصغرى تدير قفل أسرار العالم

تباهى هاردي سنة 1940 بأن نظرية الأعداد “غير ملوَّثة” بالتطبيقات. وبعد ثمانين سنة، يكذّبه كل صفير رمز شريطي، وكل دفعة ببطاقة ائتمان، وكل رسالة معمّاة — وبأدوات هذا الفصل بالضبط: الموافقات (القضية 29.5)، ومقلوبات بيزو (المبرهنة 29.10)، ومبرهنة فيرما الصغرى (التمرين 29.9). وتتحقق هذه المسألة من الشيفرات، وتكسر نسخة لعبة من القفل، وتتعلم لماذا يصمد القفل الحقيقي.

الجزء الأول — التمكّن من الموافقات.

احسب $2026 \bmod 7$ ؛ ثم آخر رقم في $7^{100}$ (أوجد دورة قوى $7$ بترديد $10$ ).
رفع القوى السريع (الطريقة 29.6): احسب $5^{117} \bmod 13$ (انطلق من $5^2 \equiv -1$ ).
حل $3x \equiv 5 \pmod 7$ .
شغّل خوارزمية إقليدس على $(97, 35)$ ، ثم عوّض بالمقلوب لإيجاد عددين صحيحين $u, v$ حيث $97u + 35v = 1$ ، ثم استنتج مقلوب $35$ بترديد $97$ .
صُغ بدقة متى يكون $a$ قابلًا للقلب بترديد $n$ ، و أي مبرهنة تسلّم المقلوب.

الجزء الثاني — أرقام التحقق.

الترميز ISBN ذو العشرة أرقام: يجب أن تحقق الأرقام العشرة $d_1 \dots d_{10}$ لشيفرة كتاب العلاقة $10d_1 + 9d_2 + \dots + 2d_9 + 1d_{10} \equiv 0 \pmod{11}$ . تحقق من الشيفرة الحقيقية $0\,306\,40615\,2$ .
برهن على أن مخطط ISBN يكشف كل خطأ في رقم واحد: فإذا تغيّر رقم بمقدار $d \not\equiv 0$ ، تغيّر المجموع المرجَّح بالمقدار $w d$ حيث $1 \leq w \leq 10$ — فلماذا لا يمكن أن يكون هذا أبدًا $\equiv 0 \pmod{11}$ (المبرهنة 29.11)؟
برهن على أنه يكشف أيضًا كل تبادل بين رقمين متجاورين (متمايزين). ثم فسّر سرّ التصميم: أي خاصية للعدد $11$ جعلت البرهانين يفلحان، وما الذي قد يسوء مع الترديد $10$ ؟
ترجّح الرموز الشريطية EAN ذات الثلاثة عشر رقمًا الأرقام بالأوزان $1, 3, 1, 3, \dots$ بترديد $10$ . احسب رقم التحقق الذي يكمل $978\,2940199\,05$ . وأي التبادلات المتجاورة يعجز هذا الترميز عن كشفها؟ (ومتى يكون $2(a - b) \equiv 0 \pmod{10}$ ؟)
تستعمل بطاقات الائتمان مخطط لوهن: من اليمين، ضاعف كل رقم ثانٍ (مع طرح $9$ عندما يتجاوز الضعف $9$ )، ثم اجمع كل شيء، واشترط أن يكون المجموع مضاعفًا للعدد $10$ . تحقق من الرقم الاختباري $4539\,1488\,0343\,6467$ .
في جملة واحدة: ماذا اشترى الترديد الأولي للترميز ISBN مما لا يستطيعه EAN ومخطط لوهن المقيَّدان بالعدد $10$ ؟

الجزء الثالث — قفل فيرما.

مصيدة قبل الكنز: احسب $2^{10} \bmod 341$ ، واستنتج $2^{340} \bmod 341$ — ثم حلّل $341$ . فماذا يقول هذا المثال (وهو عدد فيرما الأولي الكاذب) عن استعمال مبرهنة فيرما الصغرى اختبارًا للأولية؟
نظام RSA مصغَّرًا: خذ $p = 3$ و $q = 11$ ، فيكون $n = 33$ و $(p-1)(q-1) = 20$ ؛ والأس العلني هو $e = 3$ . أوجد الأس السري $d$ حيث $3d \equiv 1 \pmod{20}$ (بمنهج السؤال 4).
عمِّ الرسالة $m = 4$ : احسب $c = m^3 \bmod 33$ .
فكّ التعمية: احسب $c^d \bmod 33$ (باستعمال $c \equiv -2 \pmod{33}$ ) واستعد الرسالة.
لماذا ينجح فكّ التعمية دائمًا: بيّن أن $m^{21} \equiv m$ بترديد $3$ وبترديد $11$ معًا (بمبرهنة فيرما الصغرى في كل عالم)، ثم اختم بترديد $33$ (إذ تلصق المبرهنة 29.11 الموافقتين). وأين دخلت الصورة الخاصة $1 + 20k$ للمقدار $21 = ed$ ؟
أمان القفل: الجميع يعرف $n$ و $e$ ؛ و استعادة $d$ تقتضي $(p-1)(q-1)$ ، ومنه عوامل $n$ . وعددنا $33$ يتحلّل بالنظر — فلماذا يحمي المخطط نفسه، مع $n$ من ستمئة رقم، مصارف العالم؟ (جملة واحدة عن اللاتناظر بين الضرب والتحليل.)

الجزء الرابع — الكلاسيكيات.

عدّ الجنود الصيني القديم (قارن التمرين 29.10): عدد من الجنود يترك الباقي $2$ عند اصطفافهم صفوفًا من $3$ ، والباقي $3$ عند اصطفافهم صفوفًا من $5$ . أوجد كل الأعداد الممكنة، وفسّر لماذا يكون الجواب وحيدًا بترديد $15$ .
براهين من سطر واحد أخيرًا: انطلاقًا من $10 \equiv 1 \pmod 9$ ، برهن على أن كل عدد يوافق مجموع أرقامه بترديد $9$ ؛ ومن $10 \equiv -1 \pmod{11}$ ، استخرج قاعدة المجموع المتناوب من أجل $11$ . (وقد برهن الكتاب السابق على هاتين بجبر صريح — فاعجب من الضغط.)
الخاتمة — هاردي في مواجهة الرمز الشريطي: لخّص عدّة الفصل (حساب الموافقات، ومقلوبات بيزو، ومبرهنة فيرما الصغرى، ولصق الترديدين الأوليين فيما بينهما) وأين انطبق كل منها في هذه المسألة؛ ثم أعطِ الحكم الحديث على “غير ملوَّثة”.

حل

حل المسألة 29.1.

1. $2026 = 289 \times 7 + 3$ : $2026 \equiv 3 \pmod 7$ . وقوى $7$ بترديد $10$ : $7, 9, 3, 1$ ، ودورتها طولها $4$ ؛ و $100 \equiv 0 \pmod 4$ : فآخر رقم في $7^{100}$ هو $1$ .

2. $5^2 = 25 \equiv -1 \pmod{13}$ ، إذن $5^{116} = \left(5^2\right)^{58} \equiv (-1)^{58} = 1$ و $5^{117} \equiv 5 \pmod{13}$ .

3. مقلوب $3$ بترديد $7$ هو $5$ (لأن $15 \equiv 1$ ): $x \equiv 5 \times 5 = 25 \equiv 4 \pmod 7$ .

4. $97 = 2 \times 35 + 27$ ؛ و $35 = 27 + 8$ ؛ و $27 = 3 \times 8 + 3$ ؛ و $8 = 2 \times 3 + 2$ ؛ و $3 = 2 + 1$ . وبالتعويض بالمقلوب: $1 = 97 \times 13 + 35 \times (-36)$ . إذن $35 \times (-36) \equiv 1 \pmod{97}$ : فمقلوب $35$ هو $-36 \equiv 61 \pmod{97}$ .

5. يكون $a$ قابلًا للقلب بترديد $n$ بالضبط عندما يكون $\gcd(a, n) = 1$ : فمساواة بيزو تعطي $au + nv = 1$ ، أي $au \equiv 1$ ؛ وبالعكس، وجود مقلوب يفرض أن يقسم القاسم المشترك الأكبر $1$ .

6. $0{\cdot}10 + 3{\cdot}9 + 0{\cdot}8 + 6{\cdot}7 + 4{\cdot}6 + 0{\cdot}5 + 6{\cdot}4 + 1{\cdot}3 + 5{\cdot}2 + 2{\cdot}1 = 132 = 12 \times 11 \equiv 0 \pmod{11}$ : صحيحة.

7. يتغيّر المجموع بالمقدار $wd$ حيث $1 \leq w \leq 10$ و $1 \leq \abs d \leq 9$ : وبما أن $11$ أولي ولا يقسم أيًا من العاملين، فلا يمكنه أن يقسم الجداء (المبرهنة 29.11 / القضية 29.14): فلا يعود المجموع المتغيّر $\equiv 0$ أبدًا: أي إن كل خطأ في رقم واحد يشغّل الإنذار.

8. تبادل رقمين متجاورين $a, b$ (وزناهما $w + 1, w$ ) يغيّر المجموع بالمقدار $(w+1)b + wa - (w+1)a - wb = b - a \not\equiv 0$ من أجل $a \neq b$ : فيُكشف. والسرّ هو أولية العدد $11$ : فبترديد $10$ ، تنعدم جداءات مثل $5 \times 2$ مع أن كلا العاملين غير معدوم، فقد ينزلق خطأ قدره $\pm 2$ عند الوزن $5$ (أو تبادل غير محظوظ) دون أن يُكشف.

9. المجموع المرجَّح للأرقام الاثني عشر: $119$ ؛ و يجب أن يكمله رقم التحقق إلى مضاعف للعدد $10$ : أي $1$ (والشيفرة الكاملة $978\,2940199\,051$ ). ويفوت الترميز EAN التبادلات المتجاورة التي فيها $2(a - b) \equiv 0 \pmod{10}$ ، أي $\abs{a - b} = 5$ : فتبادل $2$ و $7$ مثلًا يمر دون أن يُرى — وهو ثمن الترديد الودود $10$ .

10. بمضاعفة كل رقم ثانٍ من اليمين وطيّه ( $16 \to 7$ ، وهكذا)، يبلغ المجموع $80 \equiv 0 \pmod{10}$ : فتُقبل البطاقة الاختبارية.

11. مع ترديد أولي يكون كل وزن قابلًا للقلب، فتُكشف كل الأخطاء المفردة وكل التبادلات المتجاورة — وهي رفاهية ISBN؛ أما مخططات الترديد $10$ فتحتفظ بأرقام ودودة للإنسان وتقبل بقعة عمياء قصيرة.

12. $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1 \pmod{341}$ ، ومنه $2^{340} = \left(2^{10}\right)^{34} \equiv 1$ . ومع ذلك فإن $341 = 11 \times 31$ مركّب: فهو يجتاز اختبار فيرما عند الأساس $2$ وهو ليس أوليًا. والعبرة: أن موافقة فيرما لازمة لا كافية — فاختبار الأولية يحتاج إلى أدوات أحدّ (وينالها، في الكتب الجامعية).

13. $3d \equiv 1 \pmod{20}$ : أي $d = 7$ (لأن $21 = 20 + 1$ ).

14. $c = 4^3 = 64 \equiv 31 \pmod{33}$ .

15. $31 \equiv -2$ : فإن $(-2)^7 = -128$ ، و $-128 + 4 \times 33 = 4$ : فيفكّ النص المعمّى إلى $m = 4$ . والقفل يدور.

16. بترديد $3$ : إذا كان $3 \nmid m$ ، فإن $m^2 \equiv 1$ (بفيرما)، إذن $m^{21} = m \cdot \left(m^2\right)^{10} \equiv m$ ؛ وإذا كان $3 \mid m$ ، فالطرفان $\equiv 0$ . وبترديد $11$ : $m^{10} \equiv 1$ أو $11 \mid m$ ، و $m^{21} = m \cdot \left(m^{10}\right)^2 \equiv m$ . فيقسم كل من $3$ و $11$ المقدار $m^{21} - m$ ، وبما أنهما أوليان فيما بينهما فإن جداءهما $33$ يقسمه أيضًا (بمبرهنة غاوس المساعدة): $m^{21} \equiv m \pmod{33}$ . وقد بُني الأس $ed = 21 = 1 + 20k$ بحيث يختفي أسّا فيرما ( $2$ و $10$ ، وكلاهما يقسم $20$ ).

17. ضرب عددين أوليين طول كل منهما $300$ رقمًا يستغرق ميكروثانية؛ أما استعادتهما من جداءهما فتهزم كل خوارزمية معروفة وكل حواسيب العالم — فالقفل طريق باتجاه واحد. (وعددنا $n = 33$ هو الطريق بمقياس اللعبة، يُمشى في الاتجاهين.)

18. باختبار البواقي (أو بالبناء بمساواة بيزو): $n \equiv 8 \pmod{15}$ : فالأعداد $8, 23, 38, 53, \dots$ والوحدانية بترديد $15$ : فحلان يختلفان بمضاعف للعدد $3$ وللعدد $5$ ، ومنه للعدد $15$ (لأن $3$ و $5$ أوليان فيما بينهما، بغاوس). والقائد الذي معه $1000$ جندي يعلن “ $8$ ” بثلاثة اصطفافات سريعة — وهي حيلة عدّ الرؤوس القديمة.

19. $10 \equiv 1 \pmod 9$ يعطي $10^k \equiv 1$ ، إذن $\sum d_k 10^k \equiv \sum d_k$ : أي إن العدد ومجموع أرقامه متوافقان بترديد $9$ (وبترديد $3$ ). و $10 \equiv -1 \pmod{11}$ يعطي $\sum d_k 10^k \equiv \sum (-1)^k d_k$ : وهي القاعدة المتناوبة. قاعدتان من الطفولة، سطر واحد لكل منهما.

20. حوّلت الموافقات البواقي إلى حساب (الجزء الأول)؛ وسكّت مساواة بيزو المقلوبات التي تحل الموافقات الخطية وتعطي $d$ في نظام RSA (السؤالان 4 و 13)؛ وفتحت مبرهنة فيرما الصغرى القفل وأغلقته (السؤالان 15–16)؛ ولصق الترديدين الأوليين فيما بينهما عدّ الجنود وأتمّ البرهان (السؤالان 16 و 18). والحكم على هاردي: فأنقى مبرهنة عرفها صارت اليوم تحرس كل شراء — فالنقاء، مع الوقت، هو أكثر ما يقبل التطبيق.

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

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