مقدمة في نظرية الأعداد

استخدمنا الأعداد الطبيعية (Natural Numbers) لحل المسائل. وكانت هذه هي مجموعة الأعداد المناسبة للعمل بها في الرياضيات المتقطعة (Discrete Mathematics)، لأننا تعاملنا دائمًا مع عدد صحيح من الأشياء. لقد كانت الأعداد الطبيعية أداة. فلنتوقف الآن قليلًا لتفحّص هذه الأداة. ما الاكتشافات الرياضية التي يمكننا التوصل إليها عن الأعداد الطبيعية نفسها؟

هذا هو السؤال الرئيسي لنظرية الأعداد (Number Theory): فرع ضخم وعريق ومعقّد، وقبل كل شيء جميل، من فروع الرياضيات. تاريخيًا، عُرفت نظرية الأعداد بأنها ملكة الرياضيات، وكانت إلى حد كبير فرعًا من الرياضيات البحتة (Pure Mathematics)، تُدرَس لذاتها لا بوصفها وسيلة لفهم تطبيقات العالم الحقيقي. لكن هذا تغيّر في السنوات الأخيرة، مع اكتشاف تطبيقات لنظرية الأعداد. ولعل أشهر مثال على ذلك هو التشفير باستخدام RSA، إحدى الطرق المستخدمة لتشفير البيانات على الإنترنت. ونظرية الأعداد هي ما يجعل هذا ممكنًا.

ما أنواع الأسئلة التي تنتمي إلى مجال نظرية الأعداد؟ إليك مثالًا محفِّزًا. تذكّر أننا سألنا في دراستنا للاستقراء (Induction):

ما قيم الرسوم البريدية التي يمكن تكوينها بالضبط باستخدام طوابع من فئتي 5 سنتات و8 سنتات فقط؟

استطعنا إثبات إمكان تكوين أي مبلغ أكبر من 27 سنتًا. وقد تتساءل عما سيحدث إذا غيّرنا فئات الطوابع. ماذا لو كانت لدينا بدلًا منها طوابع من فئتي 4 سنتات و9 سنتات؟ هل يوجد مبلغ تصبح بعده جميع المبالغ ممكنة؟ حسنًا، يمكننا مرة أخرى استبدال طابعين من فئة 4 سنتات بطابع من فئة 9 سنتات، أو ثلاثة طوابع من فئة 9 سنتات بسبعة طوابع من فئة 4 سنتات. وفي كل حالة، يمكننا زيادة الرسوم البريدية سنتًا واحدًا. واستخدام هذا بوصفه حالة الاستقراء سيسمح لنا بإثبات إمكان تكوين أي مبلغ من الرسوم البريدية أكبر من 23 سنتًا.

ماذا لو كانت لدينا طوابع من فئتي سنتين و4 سنتات؟ يبدو الأمر هنا أقل تبشيرًا. إذا أخذنا عددًا من الطوابع ذات السنتين وعددًا من الطوابع ذات الـ4 سنتات، فماذا يمكننا أن نقول عن المجموع؟ هل يمكن أن يكون فرديًا في أي وقت؟ لا يبدو ذلك.

لماذا ينجح العددان 5 و8، وينجح العددان 4 و9، ولا ينجح العددان 2 و4؟ ما الخاصية التي تتميّز بها هذه الأعداد؟ إذا أعطيتك زوجًا من الأعداد، فهل يمكنك أن تخبرني فورًا إن كانا سينجحان أم لا؟ سنجيب عن هذه الأسئلة وعن غيرها، بعد أن نستقصي أولًا بعض الخصائص الأبسط للأعداد نفسها.

قسم فرعي: قابلية القسمة (Divisibility)

من السهل جمع الأعداد الطبيعية وضربها. وإذا وسّعنا اهتمامنا ليشمل جميع الأعداد الصحيحة (Integers)، يصبح الطرح سهلًا أيضًا (نحتاج إلى الأعداد السالبة حتى نستطيع طرح أي عدد من أي عدد آخر، حتى الأكبر من الأصغر). القسمة هي أول عملية تطرح تحديًا. إذا أردنا توسيع مجموعة أعدادنا بحيث تكون أي قسمة ممكنة (ربما باستثناء القسمة على 0)، فسنحتاج إلى النظر في الأعداد النسبية (Rational Numbers)، أي مجموعة جميع الأعداد التي يمكن كتابتها على هيئة كسور. لكن هذا سيذهب بنا بعيدًا جدًا، لذا سنرفض هذا الخيار.

في الواقع، من الجيد ألا يكون كل عدد قابلًا للقسمة على الأعداد الأخرى. فهذا يساعدنا على فهم بنية الأعداد الطبيعية، ويفتح الباب أمام كثير من الأسئلة والتطبيقات المثيرة للاهتمام.

إذا أُعطي العددان $a$ و$b$، فقد يكون ناتج $a \div b$ عددًا صحيحًا. في هذه الحالة، نقول إن $b$ يقسم $a$؛ وبالرموز نكتب $b \mid a\text{.}$ إذا صح ذلك، فإن $b$ قاسم (Divisor) أو عامل (Factor) للعدد $a$، و$a$ مضاعف (Multiple) للعدد $b\text{.}$ بعبارة أخرى، إذا كان $b \mid a$، فإن $a = bk$ لعدد صحيح ما $k$ (أي إن $a$ مضاعف ما للعدد $b$).

علاقة قابلية القسمة (Divisibility Relation).

إذا أُعطي العددان الصحيحان $m$ و$n$، نقول «$m$ يقسم $n$»، ونكتب:

$$\begin{equation*} m \mid n \end{equation*}$$

بشرط أن يكون $n \div m$ عددًا صحيحًا. ومن ثم فإن العبارات الآتية تعني الشيء نفسه:

1. $m \mid n\text{.}$
2. $n = mk$ لعدد صحيح ما $k\text{.}$
3. $m$ عامل (أو قاسم) للعدد $n\text{.}$
4. $n$ مضاعف للعدد $m\text{.}$

لاحظ أن $m \mid n$ عبارة، فهي إما صحيحة وإما خاطئة. أما $n \div m$ أو $n/m$، فهو عدد ما. إذا أردنا القول إن $n/m$ ليس عددًا صحيحًا، ومن ثم فإن $m$ لا يقسم $n$، فيمكننا كتابة $m \nmid n\text{.}$

مثال 6.2.1.

حدّد ما إذا كانت كل عبارة من العبارات الآتية صحيحة أم خاطئة.

1. $\displaystyle 4 \mid 20$
2. $\displaystyle 20 \mid 4$
3. $\displaystyle 0 \mid 5$
4. $\displaystyle 5 \mid 0$
5. $\displaystyle 7 \mid 7$
6. $\displaystyle 1 \mid 37$
7. $\displaystyle -3 \mid 12$
8. $\displaystyle 8 \mid 12$
9. $\displaystyle 1642 \mid 136299$

الحل.

1. صحيحة. العدد 4 «يدخل في» 20 خمس مرات دون باقٍ. بعبارة أخرى، $20 \div 4 = 5\text{,}$ وهو عدد صحيح. ويمكننا أيضًا تبرير ذلك بالقول إن $20$ مضاعف للعدد 4: $20 = 4\cdot 5\text{.}$
2. خاطئة. مع أن 20 مضاعف للعدد 4، فليس صحيحًا أن $4$ مضاعف للعدد 20.
3. خاطئة. $5 \div 0$ غير معرّف أصلًا، فضلًا عن أن يكون عددًا صحيحًا.
4. صحيحة. في الواقع، $x \mid 0$ صحيحة لكل $x\text{.}$ وذلك لأن 0 مضاعف لكل عدد: $0 = x\cdot 0\text{.}$
5. صحيحة. في الواقع، $x \mid x$ صحيحة لكل $x\text{.}$
6. صحيحة. العدد 1 يقسم كل عدد (عدا 0).
7. صحيحة. تعمل الأعداد السالبة دون أي مشكلة في علاقة قابلية القسمة. هنا $12 = -3 \cdot 4\text{.}$ وصحيح أيضًا أن $3 \mid -12$، وأن $-3 \mid -12\text{.}$
8. خاطئة. كل من 8 و12 يقبل القسمة على 4، لكن هذا لا يعني أن $12$ يقبل القسمة على $8\text{.}$
9. خاطئة. انظر أدناه.

يثير هذا المثال الأخير سؤالًا: كيف يمكن أن نقرّر ما إذا كان $m \mid n\text{?}$ بالطبع، إذا كانت لديك آلة حاسبة موثوقة، يمكنك أن تطلب منها قيمة $n \div m\text{.}$ وإذا أعطتك أي شيء غير عدد صحيح، فتعرف أن $m \nmid n\text{.}$ لكن هذا يبدو أشبه بالغش بعض الشيء: ليست لدينا القسمة، فهل ينبغي حقًا أن نستخدم القسمة للتحقّق من قابلية القسمة؟

مع أننا لا نعرف حقًا كيف نقسم، فإننا نعرف كيف نضرب. يمكننا محاولة ضرب $m$ في أعداد تتزايد تباعًا حتى نقترب من $n\text{.}$ إلى أي حد نقترب؟ نريد أن نتأكد من أننا إذا ضربنا $m$ في العدد الصحيح الأكبر التالي، تجاوزنا $n\text{.}$

مثلًا، لنجرب هذه الطريقة لنقرّر ما إذا كان $1642 \mid 136299\text{.}$ ابدأ بإيجاد مضاعفات العدد 1642:

$$\begin{equation*} 1642 \cdot 2 = 3284 \qquad 1642 \cdot 3 = 4926 \qquad 1642\cdot 4 = 6568 \qquad \cdots\text{.} \end{equation*}$$

جميع هذه القيم أصغر بكثير من 136299. أظن أن بإمكاننا القفز إلى الأمام قليلًا:

$$\begin{equation*} 1642 \cdot 50 = 82100 \qquad 1642 \cdot 80 = 131360 \qquad 1642 \cdot 85 = 139570\text{.} \end{equation*}$$

آه، إذن علينا البحث في موضع ما بين 80 و85. جرّب 83:

$$\begin{equation*} 1642 \cdot 83 = 136286\text{.} \end{equation*}$$

هل هذا أفضل ما يمكننا فعله؟ كم نبتعد عن القيمة المطلوبة، 136299؟ إذا طرحنا، نحصل على $136299 - 136286 = 13\text{.}$ لذا نعرف أننا لا نستطيع الانتقال إلى 84؛ إذ سيكون ذلك أكبر من المطلوب. بعبارة أخرى، وجدنا أن:

$$\begin{equation*} 136299 = 83 \cdot 1642 + 13\text{.} \end{equation*}$$

بما أن $13 \lt 1642\text{,}$ يمكننا الآن القول بثقة إن $1642 \nmid 136299\text{.}$

يتبيّن أن العملية التي اتّبعناها أعلاه يمكن تكرارها لأي زوج من الأعداد. يمكننا دائمًا كتابة العدد $a$ بوصفه مضاعفًا ما للعدد $b$، مضافًا إليه باقٍ ما. نعرف ذلك لأننا نعرف القسمة مع الباقي من المدرسة الابتدائية. وهذه ليست سوى طريقة للتعبير عنها باستخدام الضرب. وبسبب الطبيعة الإجرائية التي يمكن استخدامها لإيجاد الباقي، تُسمّى هذه الحقيقة عادةً خوارزمية القسمة (Division Algorithm):

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

إذا أُعطي أي عددين صحيحين $a$ و$b$، يمكننا دائمًا إيجاد عدد صحيح $q$ بحيث:

$$\begin{equation*} a = qb + r \end{equation*}$$

حيث $r$ عدد صحيح يحقّق $0 \le r \lt |b|$.

الفكرة هي أننا نستطيع دائمًا أخذ مضاعف كبير بما يكفي للعدد $b$، بحيث يكون الباقي $r$ أصغر ما يمكن. ونسمح بإمكان أن يكون $r = 0$، وفي هذه الحالة يكون لدينا $b \mid a\text{.}$

قسم فرعي: فئات البواقي (Remainder Classes)

تخبرنا خوارزمية القسمة بأن هناك $b$ بواقي ممكنة فقط عند القسمة على $b\text{.}$ إذا ثبّتنا هذا القاسم، يمكننا تجميع الأعداد الصحيحة بحسب الباقي. وتُسمّى كل مجموعة فئة بواقٍ بترديد $b$ (Remainder Class)، أو تُسمّى أحيانًا فئة بواقي (Residue Class).

مثال 6.2.2.

صف فئات البواقي بترديد $5\text{.}$

الحل. نريد تصنيف الأعداد بحسب ما سيكون باقي قسمتها على $5\text{.}$ نعرف من خوارزمية القسمة أن هناك 5 فئات بواقٍ بالضبط، لأن هناك 5 اختيارات فقط لما يمكن أن يكون عليه $r$ ($0 \le r \lt 5$).

انظر أولًا إلى $r = 0\text{.}$ نبحث هنا عن جميع الأعداد القابلة للقسمة على $5$، لأن $a = 5q+0\text{.}$ أي مضاعفات العدد 5. نحصل على المجموعة اللانهائية:

$$\begin{equation*} \{\ldots, -15, -10, -5, 0, 5, 10, 15, 20, \ldots\}\text{.} \end{equation*}$$

لاحظ أننا نُدرج الأعداد الصحيحة السالبة أيضًا.

انظر بعد ذلك إلى $r = 1\text{.}$ ما الأعداد الصحيحة التي يكون باقي قسمتها على 5 هو 1؟ من المؤكد أن 1 كذلك، وكذلك 6 و11. وماذا عن الأعداد السالبة؟ علينا الحذر هنا: ليس باقي قسمة $-6$ هو 1. يمكننا كتابة $-6 = -2\cdot 5 + 4$ أو $-6 = -1 \cdot 5 - 1\text{,}$ لكن واحدة فقط من هاتين الصيغتين حالة «صحيحة» لخوارزمية القسمة: $r = 4$، لأننا نحتاج إلى أن يكون $r$ غير سالب. لذا، للحصول على $r = 1$، نأخذ في الواقع $-4$، أو $-9$، وهكذا. ومن ثم نحصل على فئة البواقي:

$$\begin{equation*} \{\ldots, -14, -9, -4, 1, 6, 11, 16, 21, \ldots\}\text{.} \end{equation*}$$

بقيت ثلاث فئات أخرى. فئات البواقي للأعداد $2$ و$3$ و$4$ هي، على الترتيب:

$$\begin{equation*} \{\ldots, -13, -8, -3, 2, 7, 12, 17, 22,\ldots\} \end{equation*}$$ $$\begin{equation*} \{\ldots, -12, -7, -2, 3, 8, 13, 18, 23, \ldots\} \end{equation*}$$ $$\begin{equation*} \{\ldots, -11, -6, -1, 4, 9, 14, 19, 24, \ldots\}\text{.} \end{equation*}$$

لاحظ في المثال السابق أن كل عدد صحيح ينتمي إلى فئة بواقٍ واحدة بالضبط. والصياغة الاصطلاحية لهذا هي أن فئات البواقي بترديد $b$ تشكّل تقسيمًا (Partition) للأعداد الصحيحة.

¹

يمكن تطوير نظرية رياضية للتقسيمات، وإثبات عبارات عن جميع التقسيمات عمومًا، ثم تطبيق تلك الملاحظات على حالتنا هنا.

أهم حقيقة عن التقسيمات هي أنه يمكن تعريف علاقة تكافؤ (Equivalence Relation) انطلاقًا من تقسيم: وهي علاقة بين أزواج من الأعداد تتصرف، في جميع الجوانب المهمة، مثل علاقة «يساوي».

²

مرة أخرى، توجد نظرية رياضية لعلاقات التكافؤ تنطبق على حالات أكثر بكثير من الحالة التي ننظر إليها هنا. انظر القسم الفرعي.

إذا وضعنا جانبًا كل هذه اللغة الاصطلاحية الممتعة، فالفكرة بسيطة حقًا. إذا انتمى عددان إلى فئة البواقي نفسها، فهما متماثلان على نحو ما. أي إنهما متماثلان من حيث القسمة على $b$. في الحالة السابقة التي فيها $b = 5$، فإن العددين $8$ و$23$، مع أنهما ليسا العدد نفسه، متماثلان عندما يتعلق الأمر بالقسمة على 5، لأن باقي كليهما $3\text{.}$

اختيار القاسم مهم: العددان $8$ و$23$ متماثلان من حيث القسمة على $5$، لكنهما ليسا متماثلين من حيث القسمة على $7$، لأن باقي قسمة $8$ على 7 هو 1، بينما باقي قسمة 23 هو 2.

مع وضع كل هذا في الاعتبار، لنقدّم بعض الرموز. نريد أن نقول إن $8$ و23 متماثلان في الأساس، رغم أنهما غير متساويين. وسيكون من الخطأ القول إن $8 = 23\text{.}$ بدلًا من ذلك، نكتب $8 \equiv 23\text{.}$ لكن هذا ليس صحيحًا دائمًا. إنه يصح إذا كنا نفكّر في القسمة على 5، لذا نحتاج إلى التعبير عن ذلك برمز ما. وما سنكتبه بالفعل هو:

$$\begin{equation*} 8 \equiv 23 \pmod{5} \end{equation*}$$

وتُقرأ «8 يطابق 23 بترديد 5» (Congruent Modulo 5)، أو باختصار «بترديد 5». ويمكننا عندئذ، بالطبع، ملاحظة أن:

$$\begin{equation*} 8 \not\equiv 23 \pmod{7}\text{.} \end{equation*}$$

التطابق بترديد $n$ (Congruence Modulo n).

نقول إن $a$ يطابق $b$ بترديد $n$، ونكتب:

$$\begin{equation*} a \equiv b \pmod{n} \end{equation*}$$

بشرط أن يكون للعددين $a$ و$b$ الباقي نفسه عند القسمة على $n\text{.}$ بعبارة أخرى، بشرط أن ينتمي $a$ و$b$ إلى فئة البواقي نفسها بترديد $n\text{.}$

تعرّف كتب كثيرة التطابق بترديد $n$ بطريقة مختلفة قليلًا. فهي تقول إن $a \equiv b \pmod{n}$ إذا وفقط إذا كان $n \mid a-b\text{.}$ بعبارة أخرى، يطابق عددان أحدهما الآخر بترديد $n$ إذا كان الفرق بينهما مضاعفًا للعدد $n\text{.}$ فأي التعريفين صحيح؟ يتبيّن أن الأمر لا يهم؛ فهما متكافئان.

لمعرفة السبب، انظر إلى عددين $a$ و$b$ يطابق أحدهما الآخر بترديد $n\text{.}$ عندئذ يكون للعددين $a$ و$b$ الباقي نفسه عند القسمة على $n\text{.}$ لدينا:

$$\begin{equation*} a = q_1 n + r \qquad\qquad b = q_2 n + r\text{.} \end{equation*}$$

قيمتا $r$ هنا متساويتان بالفعل. انظر إلى ما نحصل عليه عندما نأخذ الفرق بين $a$ و$b$:

$$\begin{equation*} a-b = q_1n + r - (q_2n + r) = q_1n - q_2 n = (q_1-q_2)n\text{.} \end{equation*}$$

إذن $a-b$ مضاعف للعدد $n$، أو على نحو مكافئ، $n \mid a-b\text{.}$

من جهة أخرى، إذا افترضنا أولًا أن $n \mid a-b$، ومن ثم $a-b = kn$، فانظر إلى ما يحدث إذا قسمنا كل حد على $n\text{.}$ ستترك قسمة $a$ على $n$ باقيًا ما، وكذلك قسمة $b$ على $n\text{.}$ لكن قسمة $kn$ على $n$ ستترك باقيًا مقداره 0. لذا يجب أن يلغي الباقيان في الطرف الأيسر أحدهما الآخر. أي إن الباقيين يجب أن يكونا متساويين.

وعليه لدينا:

التطابق وقابلية القسمة.

لأي أعداد صحيحة $a$ و$b$ و$n$، لدينا:

$$\begin{equation*} a \equiv b \pmod{n} \qquad \text{ إذا وفقط إذا } \qquad n \mid (a-b)\text{.} \end{equation*}$$

سيكون من المفيد أيضًا الانتقال ذهابًا وإيابًا بين التطابقات والمعادلات المعتادة. والحقيقة السابقة تساعد في ذلك. نعرف أن $a \equiv b \pmod{n}$ إذا وفقط إذا كان $n \mid a-b$، وإذا وفقط إذا كان $a-b = kn$ لعدد صحيح ما $k\text{.}$ بإعادة ترتيب تلك المعادلة، نحصل على $a = b + kn\text{.}$ بعبارة أخرى، إذا طابق $a$ و$b$ أحدهما الآخر بترديد $n$، فإن $a$ يزيد بمقدار $b$ على مضاعف ما للعدد $n\text{.}$ وهذا يتوافق مع ملاحظتنا السابقة بأن جميع الأعداد في فئة بواقٍ معيّنة تزيد بالمقدار نفسه على مضاعفات $n\text{.}$

التطابق والمساواة.

لأي أعداد صحيحة $a$ و$b$ و$n$، لدينا:

$$\begin{equation*} a \equiv b \pmod{n} \qquad \text{ إذا وفقط إذا } \qquad a = b + kn \mbox{ لعدد صحيح ما } k\text{.} \end{equation*}$$

قسم فرعي: خصائص التطابق

قلنا سابقًا إن التطابق بترديد $n$ يتصرف، في جوانب مهمة كثيرة، بالطريقة نفسها التي تتصرف بها المساواة. وتحديدًا، يمكننا إثبات أن التطابق بترديد $n$ علاقة تكافؤ، وهذا يتطلب التحقّق من الحقائق الثلاث الآتية:

التطابق بترديد $n$ علاقة تكافؤ.

إذا أُعطيت أي أعداد صحيحة $a$ و$b$ و$c$، وأي عدد صحيح موجب $n$، فإن الآتي يصح:

1. $a \equiv a \pmod{n}\text{.}$
2. إذا كان $a \equiv b \pmod{n}$، فإن $b \equiv a \pmod{n}\text{.}$
3. إذا كان $a \equiv b \pmod{n}$ و$b \equiv c \pmod{n}$، فإن $a \equiv c \pmod{n}\text{.}$

بعبارة أخرى، التطابق بترديد $n$ انعكاسي (Reflexive)، ومتناظر (Symmetric)، ومتعدٍّ (Transitive)، ولذلك فهو علاقة تكافؤ.

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

انظر بعد ذلك إلى كيفية تصرّف التطابق عند إجراء العمليات الحسابية الأساسية. نعرف بالفعل أنك إذا طرحت عددين متطابقين، ستكون النتيجة مطابقة للعدد 0 (أي مضاعفًا للعدد $n$). ماذا لو جمعنا شيئًا يطابق 1 مع شيء يطابق 2؟ هل سنحصل على شيء يطابق 3؟

التطابق والحساب.

افترض أن $a \equiv b \pmod{n}$ و$c \equiv d \pmod{n}\text{.}$ عندئذ يصح الآتي:

1. $a+c \equiv b+d \pmod{n}\text{.}$
2. $a-c \equiv b-d \pmod{n}\text{.}$
3. $ac \equiv bd \pmod{n}\text{.}$

قد تكون الحقائق السابقة مكتوبة بطريقة غريبة بعض الشيء، لكن الفكرة بسيطة. إذا كان لدينا تطابق صحيح، وأضفنا الشيء نفسه إلى الطرفين، تظل النتيجة تطابقًا صحيحًا. يبدو هذا كما لو كنا نقول:

إذا كان $a \equiv b \pmod{n}$، فإن $a+c \equiv b+c \pmod{n}\text{.}$

وهذا صحيح أيضًا بالطبع؛ فهو الحالة الخاصة التي فيها $c = d\text{.}$ لكن ما لدينا يعمل بصورة أعم. فكّر في التطابق على أنه «مساواة في الأساس». إذا كان لدينا عددان متساويان في الأساس، وأضفنا إلى الطرفين شيئًا متماثلًا في الأساس، فستكون النتيجة متساوية في الأساس.

يبدو هذا معقولًا. هل هو صحيح حقًا؟ لنثبت الحقيقة الأولى:

البرهان.

افترض أن $a \equiv b \pmod{n}$ و$c \equiv d \pmod{n}\text{.}$ هذا يعني أن $a = b + kn$ و$c = d + jn$، لعددين صحيحين $k$ و$j\text{.}$ اجمع هاتين المعادلتين:

$$\begin{equation*} a+c = b+d + kn + jn\text{.} \end{equation*}$$

لكن $kn + jn = (k+j)n$، وهو مجرد مضاعف للعدد $n\text{.}$ لذا فإن $a+c = b+d + (j+k)n$، أو بعبارة أخرى، $a+c \equiv b+d \pmod{n}\text{.}$

يمكن إثبات الحقيقتين الأخريين بطريقة مشابهة.

إحدى النتائج المهمة لهذه الحقائق عن التطابقات هي أننا نستطيع، في الأساس، استبدال أي عدد في تطابق بأي عدد آخر يطابقه. إليك بعض الأمثلة لترى كيف يعمل ذلك (ولماذا):

مثال 6.2.3.

أوجد باقي قسمة $3491$ على $9\text{.}$

الحل. يمكننا إجراء القسمة المطوّلة، لكن هناك طريقة أخرى. نريد إيجاد $x$ بحيث $x \equiv 3491 \pmod{9}\text{.}$ الآن $3491 = 3000 + 400 + 90 + 1\text{.}$ وبالطبع $90 \equiv 0 \pmod 9$، لذا يمكننا استبدال 90 في المجموع بـ0. لماذا يجوز ذلك؟ نحن نطرح في الواقع الشيء «نفسه» من الطرفين:

$$\begin{equation*} \begin{aligned}x \amp \equiv 3000 + 400 + 90 + 1 \pmod 9 \\ - ~~ 0 \amp \equiv 90 \pmod 9 \\ x \amp \equiv 3000 + 400 + 0 + 1\pmod 9. \end{aligned} \end{equation*}$$

لاحظ بعد ذلك أن $400 = 4 \cdot 100$، وأن $100 \equiv 1 \pmod 9$ (لأن $9 \mid 99$). لذا يمكننا في الواقع استبدال 400 بالعدد 4 ببساطة. مرة أخرى، نحتكم إلى قولنا إننا نستطيع استبدال العناصر المتطابقة، لكننا نحتكم حقًا إلى الخاصية 3 المتعلقة بحساب التطابقات: نعرف أن $100 \equiv 1 \pmod{9}$، لذا إذا ضربنا الطرفين في $4$، نحصل على $400 \equiv 4 \pmod 9\text{.}$

وبالمثل، يمكننا استبدال 3000 بالعدد 3، لأن $1000 = 1 + 999 \equiv 1 \pmod 9\text{.}$ لذا يصبح تطابقنا الأصلي:

$$\begin{equation*} x \equiv 3 + 4 + 0 + 1 \pmod 9 \end{equation*}$$ $$\begin{equation*} x \equiv 8 \pmod 9\text{.} \end{equation*}$$

إذن باقي قسمة $3491$ على 9 هو 8.

ينبغي أن يقنعك المثال السابق بصحة اختبار قابلية القسمة المعروف للعدد 9: يقبل مجموع أرقام عددٍ القسمة على 9 إذا وفقط إذا كان العدد الأصلي يقبل القسمة على 9. بل نعرف الآن أكثر من ذلك: أي عدد يطابق مجموع أرقامه بترديد 9.

³

يصح هذا للعدد 3 أيضًا، لكنه بالتأكيد لا يصح لأي ترديد (Modulus) عمومًا.

لنجرّب مثالًا آخر.

مثال 6.2.4.

أوجد الباقي عند قسمة $3^{123}$ على 7.

الحل. بالطبع، نعمل بالتطابق لأننا نريد إيجاد أصغر $x$ موجب بحيث $x \equiv 3^{123} \pmod 7\text{.}$ اكتب أولًا $3^{123} = (3^3)^{41}\text{.}$ لدينا:

$$\begin{equation*} 3^{123} = 27^{41} \equiv 6^{41} \pmod 7\text{,} \end{equation*}$$

لأن $27 \equiv 6 \pmod 7\text{.}$ ولاحظ أيضًا أن $6^2 = 36$ يطابق 1 بترديد 7. ومن ثم يمكننا التبسيط أكثر:

$$\begin{equation*} 6^{41} = 6\cdot (6^2)^{20} \equiv 6 \cdot 1^{20} \pmod 7\text{.} \end{equation*}$$

لكن $1^{20} = 1$، لذا انتهينا:

$$\begin{equation*} 3^{123} \equiv 6 \pmod 7\text{.} \end{equation*}$$

في المثال السابق، نستخدم حقيقة أنه إذا كان $a \equiv b \pmod n$، فإن $a^p \equiv b^p \pmod n\text{.}$ وهذا ليس سوى تطبيق الخاصية 3 مرات عديدة.

رأينا حتى الآن كيف نجمع ونطرح ونضرب باستخدام التطابقات. فماذا عن القسمة؟ هناك سبب لانتظارنا قبل مناقشتها. يتبيّن أننا لا نستطيع القسمة ببساطة. بعبارة أخرى، حتى لو كان $ad \equiv bd \pmod n$، فإننا لا نعرف أن $a \equiv b \pmod n\text{.}$ انظر مثلًا إلى:

$$\begin{equation*} 18 \equiv 42 \pmod 8\text{.} \end{equation*}$$

هذا صحيح. والآن يقبل كل من $18$ و$42$ القسمة على 6. لكن:

$$\begin{equation*} 3 \not\equiv 7 \pmod 8\text{.} \end{equation*}$$

مع أن هذا لا ينجح، لاحظ أن $3 \equiv 7 \pmod 4\text{.}$ لا نستطيع قسمة $8$ على 6، لكننا نستطيع قسمة 8 على أكبر عامل مشترك للعددين $8$ و$6\text{.}$ هل يحدث هذا دائمًا؟

افترض أن $ad \equiv bd \pmod n\text{.}$ بعبارة أخرى، لدينا $ad = bd + kn$ لعدد صحيح ما $k\text{.}$ بالطبع، يقبل $ad$ القسمة على $d$، وكذلك $bd\text{.}$ لذا يجب أن يقبل $kn$ القسمة على $d$ أيضًا. وإذا لم يكن للعددين $n$ و$d$ عوامل مشتركة (عدا 1)، فلا بد أن يكون $d \mid k\text{.}$ لكن عمومًا، إذا حاولنا قسمة $kn$ على $d$، فلا نعرف أننا سنحصل على مضاعف صحيح للعدد $n\text{.}$ فقد يُقسَم جزء من $n$ أيضًا. ولضمان ذلك، لنقسم من $n$ أكبر قدر نستطيعه. خذ أكبر عامل لكل من $d$ و$n$، واختزله من $n\text{.}$ وستأتي بقية عوامل $d$ من $k$، دون مشكلة.

سنسمّي أكبر عامل لكل من $d$ و$n$ بالرمز $\gcd(d,n)$، وهو القاسم المشترك الأكبر (Greatest Common Divisor). في مثالنا السابق، $\gcd(6,8) = 2$، لأن أكبر قاسم مشترك للعددين 6 و8 هو 2.

التطابق والقسمة.

افترض أن $ad \equiv bd \pmod n\text{.}$ عندئذ $a \equiv b \pmod{\frac{n}{\gcd(d,n)}}\text{.}$

إذا لم يكن للعددين $d$ و$n$ عوامل مشتركة، فإن $\gcd(d,n) = 1$، ومن ثم $a \equiv b \pmod n\text{.}$

مثال 6.2.5.

بسّط التطابقين الآتيين باستخدام القسمة: (أ) $24 \equiv 39 \pmod 5$، و(ب) $24 \equiv 39 \pmod{15}\text{.}$

الحل. (أ) يقبل كل من $24$ و$39$ القسمة على $3$، وليس للعددين $3$ و$5$ عوامل مشتركة، لذا نحصل على:

$$\begin{equation*} 8 \equiv 13 \pmod 5\text{.} \end{equation*}$$

(ب) يمكننا مرة أخرى القسمة على 3. لكن إجراء ذلك دون تمحيص يعطينا $8 \equiv 13 \pmod{15}$، الذي لم يعد صحيحًا. بدلًا من ذلك، علينا أيضًا قسمة الترديد 15 على أكبر عامل مشترك للعددين $3$ و$15$، وهو $3\text{.}$ نحصل مرة أخرى على:

$$\begin{equation*} 8 \equiv 13 \pmod 5\text{.} \end{equation*}$$

قسم فرعي: حل التطابقات

الآن، بعد أن أصبحت لدينا بعض القواعد الجبرية التي تحكم علاقات التطابق، يمكننا محاولة إيجاد مجهول في تطابق. مثلًا، هل توجد قيمة لـ$x$ تحقّق:

$$\begin{equation*} 3x + 2 \equiv 4 \pmod{5}\text{,} \end{equation*}$$

وإذا وُجدت، فما هي؟

في هذا المثال، بما أن الترديد صغير، يمكننا ببساطة تجربة كل قيمة ممكنة لـ$x\text{.}$ هناك في الحقيقة 5 قيم فقط ينبغي النظر فيها، لأن أي عدد صحيح يحقّق التطابق يمكن استبداله بأي عدد صحيح آخر يطابقه بترديد 5. هنا، عندما يكون $x = 4$، نحصل على $3x + 2 = 14$، وهو بالفعل يطابق 4 بترديد 5. وهذا يعني أن كلًا من $x = 9$ و$x = 14$ و$x = 19$، وهكذا، سيكون حلًا أيضًا، لأن استبدال أي عدد في تطابق بعدد يطابقه لا يغيّر صحة التطابق، كما رأينا سابقًا.

لذا، في هذا المثال، احسب ببساطة $3x + 2$ لقيم $x \in \{0,1,2,3,4\}\text{.}$ يعطي هذا 2 و5 و8 و11 و14، على الترتيب، ولا يطابق 4 من بينها إلا 14.

لنرَ أيضًا كيف يمكنك حل هذا باستخدام قواعدنا لجبر التطابقات. ستكون طريقة كهذه أبسط بكثير من أسلوب التجربة والخطأ إذا كان الترديد أكبر. أولًا، نعرف أننا نستطيع طرح 2 من الطرفين:

$$\begin{equation*} 3x \equiv 2 \pmod{5}\text{.} \end{equation*}$$

ثم، لقسمة الطرفين على 3، نضيف أولًا 0 إلى الطرفين. بالطبع، في الطرف الأيمن، نريد أن يكون ذلك الصفر هو 10 (نعم، $10$ هو بالفعل 0، لأنهما متطابقان بترديد 5). وهذا يعطي:

$$\begin{equation*} 3x \equiv 12 \pmod{5}\text{.} \end{equation*}$$

اقسم الآن الطرفين على 3. بما أن $\gcd(3,5) = 1$، لا نحتاج إلى تغيير الترديد:

$$\begin{equation*} x \equiv 4 \pmod{5}\text{.} \end{equation*}$$

لاحظ أن هذا يعطي في الواقع الحل العام (General Solution): لا يقتصر الأمر على إمكان أن يكون $x = 4$، بل يمكن أن يكون $x$ أي عدد يطابق 4. يمكننا ترك الحل هكذا، أو كتابة «$x = 4 + 5k$ لأي عدد صحيح $k$».

مثال 6.2.6.

حل التطابقات الآتية لإيجاد $x\text{.}$

1. $7x \equiv 12 \pmod{13}\text{.}$
2. $84x - 38 \equiv 79 \pmod{15}\text{.}$
3. $20x \equiv 23 \pmod{14}\text{.}$

الحل.

1. كل ما نحتاج إلى فعله هنا هو قسمة الطرفين على 7. نضيف 13 إلى الطرف الأيمن مرارًا حتى نحصل على مضاعف للعدد 7 (إضافة 13 مثل إضافة 0، لذا فهذا جائز). نحصل على $25$ و$38$ و$51$ و$64$ و$77$ — وجدناه. إذن لدينا:

   $$\begin{equation*} \begin{aligned}7x \amp \equiv 12 \pmod{13} \\ 7x \amp \equiv 77 \pmod{13} \\ x \amp \equiv 11 \pmod{13}. \end{aligned} \end{equation*}$$

2. هنا، بما أن لدينا أعدادًا أكبر من الترديد، يمكننا اختزالها قبل تطبيق أي عمليات جبرية. لدينا $84 \equiv 9$ و$38 \equiv 8$ و$79 \equiv 4\text{.}$ ومن ثم:

   $$\begin{equation*} \begin{aligned}84x - 38 \amp \equiv 79 \pmod{15} \\ 9x - 8 \amp \equiv 4 \pmod{15} \\ 9x \amp \equiv 12 \pmod{15} \\ 9x \amp \equiv 72 \pmod{15}. \end{aligned} \end{equation*}$$

   حصلنا على 72 بإضافة $0 \equiv 60 \pmod{15}$ إلى طرفي التطابق. اقسم الآن الطرفين على 9. لكن بما أن $\gcd(9, 15) = 3$، يجب أن نقسم الترديد على 3 أيضًا:

   $$\begin{equation*} x \equiv 8 \pmod 5\text{.} \end{equation*}$$

   إذن الحلول هي القيم التي تطابق 8، أو على نحو مكافئ 3، بترديد 5. وهذا يعني أن هناك، بمعنى ما، 3 حلول بترديد 15: وهي 3 و8 و13. يمكننا كتابة الحل:

   $$\begin{equation*} x \equiv 3 \pmod{15}; ~~ x \equiv 8 \pmod{15}; ~~x \equiv 13 \pmod{15}\text{.} \end{equation*}$$

3. اختزل أولًا بترديد 14:

   $$\begin{equation*} 20x \equiv 23 \pmod{14} \end{equation*}$$ $$\begin{equation*} 6x \equiv 9 \pmod{14}\text{.} \end{equation*}$$

   يمكننا الآن قسمة الطرفين على 3، أو محاولة زيادة 9 بمضاعف للعدد 14 للحصول على مضاعف للعدد 6. إذا قسمنا على 3، نحصل على:

   $$\begin{equation*} 2x \equiv 3 \pmod{14}\text{.} \end{equation*}$$

جرّب الآن إضافة مضاعفات 14 إلى 3، أملًا في الحصول على عدد نستطيع قسمته على 2. لن ينجح ذلك! في كل مرة نضيف فيها 14 إلى الطرف الأيمن، تظل النتيجة فردية. لن نحصل أبدًا على عدد زوجي، لذا لن نتمكن أبدًا من القسمة على 2. ومن ثم لا توجد حلول للتطابق.

يوضّح التطابق الأخير أعلاه كيف قد لا تكون للتطابقات حلول. وكان بإمكاننا في الواقع ملاحظة ذلك فورًا. انظر إلى التطابق الأصلي:

$$\begin{equation*} 20x \equiv 23 \pmod{14}\text{.} \end{equation*}$$

إذا كتبناه على هيئة معادلة، نحصل على:

$$\begin{equation*} 20x = 23 + 14k\text{,} \end{equation*}$$

أو على نحو مكافئ $20x - 14k = 23\text{.}$ يمكننا أن نرى بسهولة أنه لن يكون لهذه المعادلة حل في الأعداد الصحيحة. فالطرف الأيسر سيكون زوجيًا دائمًا، لكن الطرف الأيمن فردي. وستحدث مشكلة مشابهة إذا كان الطرف الأيمن يقبل القسمة على أي عدد لا يقبل الطرف الأيسر القسمة عليه.

لذا، عمومًا، إذا أُعطي التطابق:

$$\begin{equation*} ax \equiv b \pmod{n}\text{,} \end{equation*}$$

وكان $a$ و$n$ يقبلان القسمة على عدد لا يقبل $b$ القسمة عليه، فلن توجد حلول. وفي الواقع، لا نحتاج إلا إلى التحقّق من قاسم واحد للعددين $a$ و$n$: القاسم المشترك الأكبر. ومن ثم يمكن التعبير عن هذا بإيجاز أكبر كما يأتي:

تطابقات لا حلول لها.

إذا كان $\gcd(a,n) \nmid b$، فإن $ax \equiv b \pmod{n}$ لا حلول له.

قسم فرعي: حل المعادلات الديوفانتية الخطية (Linear Diophantine Equations)

تتعامل الرياضيات المتقطعة مع أعداد صحيحة من الأشياء. لذا، عندما نريد حل المعادلات، فإننا نبحث عادةً عن حلول صحيحة. وأول من درس المعادلات التي لا يُراد منها إلا حلول صحيحة هو الرياضي اليوناني ديوفانتوس الإسكندري في القرن الثالث، ولذلك تُسمّى المعادلات الديوفانتية (Diophantine Equations). ولعل أشهر مثال على معادلة ديوفانتية هو $a^2 + b^2 = c^2\text{.}$ وتُسمّى الحلول الصحيحة لهذه المعادلة ثلاثيات فيثاغورس (Pythagorean Triples). عمومًا، حل المعادلات الديوفانتية صعب (بل ثبت أنه لا توجد خوارزمية عامة لتقرير ما إذا كان لمعادلة ديوفانتية حل، وهي نتيجة تُعرف باسم مبرهنة ماتياسيفيتش (Matiyasevich’s Theorem)). سنحصر اهتمامنا في المعادلات الديوفانتية الخطية، التي يسهل التعامل معها بدرجة كبيرة.

المعادلات الديوفانتية.

تُسمّى المعادلة في متغيّرين أو أكثر معادلة ديوفانتية إذا كانت الحلول الصحيحة وحدها موضع الاهتمام. وتأخذ المعادلة الديوفانتية الخطية الصورة $a_1x_1 + a_2x_2 + \cdots + a_nx_n = b$، لثوابت $a_1,\ldots, a_n, b\text{.}$

حل المعادلة الديوفانتية هو حل للمعادلة يتكوّن من أعداد صحيحة فقط.

لدينا الأدوات التي نحتاج إليها لحل المعادلات الديوفانتية الخطية. وسنأخذ، بوصفها مثالًا رئيسيًا، المعادلة:

$$\begin{equation*} 51x + 87y = 123\text{.} \end{equation*}$$

ستكون الاستراتيجية العامة تحويل المعادلة إلى تطابق، ثم حل ذلك التطابق.

⁴

ليست هذه بالتأكيد الطريقة الوحيدة للعمل. من التقنيات الأكثر شيوعًا تطبيق الخوارزمية الإقليدية (Euclidean Algorithm). قد تكون طريقتنا أسرع قليلًا، وهي معروضة هنا أساسًا من أجل التنويع.

لنعمل على هذا المثال بالتحديد لنرى كيف يمكن أن تسير الأمور.

تحقّق أولًا مما إذا كان من المحتمل ألا توجد حلول لأن قاسمًا للعددين $51$ و$87$ ليس قاسمًا للعدد $123\text{.}$ في الحقيقة، لا نحتاج إلا إلى التحقّق مما إذا كان $\gcd(51, 87) \mid 123\text{.}$ هذا القاسم المشترك الأكبر هو 3، ونعم، $3 \mid 123\text{.}$ عند هذه النقطة، يمكننا إخراج هذا القاسم المشترك الأكبر عاملًا مشتركًا. لذا سنحل بدلًا من ذلك:

$$\begin{equation*} 17x + 29y = 41\text{.} \end{equation*}$$

لاحظ الآن أنه إذا كانت هناك حلول، فلا بد أن يكون لطرفي المعادلة الباقي نفسه عند تلك القيم لـ$x$ و$y$، أيًا كان العدد الذي نقسم عليه. وتحديدًا، إذا قسمنا الطرفين على 17، يجب أن نحصل على الباقي نفسه. لذا يمكننا أن نكتب بثقة:

$$\begin{equation*} 17x + 29y \equiv 41 \pmod{17}\text{.} \end{equation*}$$

نختار 17 لأن باقي $17x$ سيكون 0. وهذا سيسمح لنا باختزال التطابق إلى متغيّر واحد فقط. وكان بإمكاننا أيضًا الانتقال إلى تطابق بترديد 29، مع أن هناك عادةً سببًا وجيهًا لاختيار العدد الأصغر، لأن ذلك سيسمح لنا باختزال المعامل الآخر. في حالتنا، نختزل التطابق كما يأتي:

$$\begin{equation*} \begin{aligned}17x + 29y \amp \equiv 41 \pmod{17} \\ 0x + 12y \amp \equiv 7 \pmod{17} \\ 12 y \amp \equiv 24 \pmod{17} \\ y \amp \equiv 2 \pmod{17}. \end{aligned} \end{equation*}$$

عند هذه النقطة، نعرف أن $y = 2 + 17k$ يصلح لأي عدد صحيح $k\text{.}$ إذا لم نرتكب خطأ، فينبغي أن نستطيع التعويض بهذا في معادلتنا الديوفانتية الأصلية لإيجاد $x$:

$$\begin{equation*} \begin{aligned}17x + 29(2 + 17k) \amp = 41\\ 17x \amp = -17 - 29\cdot 17k\\ x \amp = -1-29k. \end{aligned} \end{equation*}$$

وجدنا الآن جميع حلول المعادلة الديوفانتية. لكل $k$، سيحقّق $x = -1-29k$ و$y = 2 + 17k$ المعادلة. ويمكننا التحقّق من هذا في بعض الحالات. إذا كان $k = 0$، فالحل هو $(-1,2)$، ونعم، $-17 + 2\cdot 29 = 41\text{.}$ وإذا كان $k = 3$، فالحل هو $(-88, 53)\text{.}$ وإذا كان $k = -2$، نحصل على $(57, -32)\text{.}$

لتلخيص هذه العملية، لحل $ax + by = c$، نقوم بالآتي:

1. نقسم طرفي المعادلة على $\gcd(a,b)$ (إذا لم يترك هذا الطرف الأيمن عددًا صحيحًا، فلا توجد حلول). لنفترض أن $ax + by = c$ قد اختُزلت بالفعل بهذه الطريقة.

2. نختار الأصغر بين $a$ و$b$ (هنا، افترض أنه $b$)، ونحوّل إلى تطابق بترديد $b$:

   $$\begin{equation*} ax + by \equiv c \pmod{b}\text{.} \end{equation*}$$

   سيُختزل هذا إلى تطابق في متغيّر واحد، هو $x$:

   $$\begin{equation*} ax \equiv c \pmod{b}\text{.} \end{equation*}$$

3. نحل التطابق كما فعلنا في القسم السابق. اكتب حلك على هيئة معادلة، مثل:

   $$\begin{equation*} x = n + kb\text{.} \end{equation*}$$

4. نعوّض بهذا في المعادلة الديوفانتية الأصلية، ونحل لإيجاد $y\text{.}$

5. إذا أردنا معرفة الحلول في نطاق معيّن (مثلًا، $0 \le x, y \le 20$)، نختار قيمًا مختلفة لـ$k$ حتى نحصل على جميع الحلول المطلوبة.

إليك مثالًا آخر:

مثال 6.2.7.

كيف يمكنك تكوين مبلغ 6.37 دولارات باستخدام طوابع من فئتي 5 سنتات و8 سنتات فقط؟ ما أصغر عدد من الطوابع وأكبر عدد منها يمكن أن تستخدمه؟

الحل. نحتاج أولًا إلى معادلة ديوفانتية. سنعمل بأعداد السنتات. ليكن $x$ عدد الطوابع من فئة $5$ سنتات، وليكن $y$ عدد الطوابع من فئة 8 سنتات. لدينا:

$$\begin{equation*} 5x + 8y = 637\text{.} \end{equation*}$$

حوّل إلى تطابق وحلّه:

$$\begin{equation*} \begin{aligned}8y \amp \equiv 637 \pmod{5}\\ 3y \amp \equiv 2 \pmod 5\\ 3y \amp \equiv 12 \pmod 5\\ y \amp \equiv 4 \pmod 5. \end{aligned} \end{equation*}$$

إذن $y = 4 + 5k\text{.}$ وعندئذ $5x + 8(4+5k) = 637$، ومن ثم $x = 121 - 8k\text{.}$

هذا يعني أن إحدى طرق تكوين مبلغ 6.37 دولارات هي أخذ 121 طابعًا من فئة 5 سنتات و4 طوابع من فئة 8 سنتات. لإيجاد أصغر عدد من الطوابع وأكبر عدد منها، جرّب قيمًا مختلفة لـ$k\text{.}$

$k$	$(x,y)$	الطوابع
-1	(129, -1)	غير ممكن
0	(121, 4)	125
1	(113, 9)	122
2	(105, 13)	119
$\vdots$	$\vdots$	$\vdots$

هذا ليس مفاجئًا. فالحصول على أكبر عدد من الطوابع يعني أن لدينا أكبر عدد ممكن من الطوابع ذات الـ5 سنتات، والحصول على أصغر عدد من الطوابع يتطلب أقل عدد من الطوابع ذات الـ5 سنتات. ولتقليل عدد الطوابع ذات الـ5 سنتات، نريد اختيار $k$ بحيث يكون $121-8k$ أصغر ما يمكن (مع بقائه موجبًا). عندما يكون $k = 15$، يكون لدينا $x = 1$ و$y = 79\text{.}$

إذن، لتكوين مبلغ 6.37 دولارات، يمكنك استخدام عدد من الطوابع لا يقل عن 80 طابعًا (طابع واحد من فئة 5 سنتات و79 طابعًا من فئة 8 سنتات)، ولا يزيد على 125 طابعًا (121 طابعًا من فئة 5 سنتات و4 طوابع من فئة 8 سنتات).

باستخدام هذه الطريقة، ما دمت تستطيع حل التطابقات الخطية في متغيّر واحد، يمكنك حل المعادلات الديوفانتية الخطية في متغيّرين. لكن هناك أوقاتًا يتطلب فيها حل التطابق الخطي عملًا كثيرًا. مثلًا، افترض أنك تحتاج إلى حل:

$$\begin{equation*} 13x \equiv 6 \pmod{51}\text{.} \end{equation*}$$

يمكنك الاستمرار في إضافة 51 إلى الطرف الأيمن حتى تحصل على مضاعف للعدد 13: ستحصل على 57 و108 و159 و210 و261 و312، والعدد 312 هو أول هذه الأعداد الذي يقبل القسمة على 13. تنجح هذه الطريقة، لكنها تتطلب حقًا عملًا أكثر من اللازم. بدلًا من ذلك، يمكننا التحويل مرة أخرى إلى معادلة ديوفانتية:

$$\begin{equation*} 13x = 6 + 51k\text{.} \end{equation*}$$

حل الآن هذه كما فعلنا في هذا القسم. اكتبها على هيئة تطابق بترديد 13:

$$\begin{equation*} \begin{aligned}0 \amp \equiv 6 + 51k \pmod{13}\\ -12k \amp \equiv 6 \pmod{13}\\ 2k \amp \equiv -1 \pmod{13}\\ 2k \amp \equiv 12 \pmod{13}\\ k \amp \equiv 6 \pmod{13}. \end{aligned} \end{equation*}$$

ومن ثم $k = 6 + 13j\text{.}$ ارجع الآن وأوجد $x$:

$$\begin{equation*} \begin{aligned}13x \amp = 6 + 51(6+13j)\\ x \amp = 24 + 51j. \end{aligned} \end{equation*}$$

بالطبع، يمكنك إجراء هذا الانتقال ذهابًا وإيابًا بين التطابقات والمعادلات الديوفانتية بقدر ما تشاء. وإذا استخدمت هذه التقنية وحدها، فستعيد في الأساس تنفيذ الخوارزمية الإقليدية، وهي طريقة أكثر شيوعًا لحل المعادلات الديوفانتية.