التطابقات الخطية

Linear Congruence

تعريف 1: المعادلة التي على الصورة $ax \equiv b\;(\bmod n)$ تسمى تطابق خطي linear congruence.

في التطابقات الخطية نهتم بالبحث عن حل, أي تحديد قيمة أو قيم x التي تحقق المعادلة. بطبيعة الحال عندما يكون x حل للتطابق الخطي فإن كل عدد y من صف التكافؤ [x] هو حل أيضا. وكل هذه القيم ننظر لها كحل واحد نعبر عنه بقيمة واحده x فنقول x حلا للتطابق الخطي $ax \equiv b\;(\bmod n)$ . أي حل z لا يطابق x معيار n هو حل آخر للمعادلة.

إذا كان للتطابق الخطي $ax \equiv b\;(\bmod n)$ حل x فهذا يعني وجود صحيح k بحيث ax-b=kn والعكس صحيح فوجود مثل هذا العدد k محققا لهذه المساواة يعني بالضرورة أن x حلا للتطابق الخطي. هذا الارتباط الوثيق بين التطابقات الخطية والمعادلات الديفونتية الخطية ذات مجهولين يساعد في تحويل^[م] إحداهما إلى الأخرى في حالة براهين النظريات حول التطابقات الخطية أو للبحث عن أنسب الطرق لإيجاد الحل كما سنرى. البداية مع حقيقة بسيطة تبين متى يكون الحل وحيدا لمعادلة تطابق خطي في مجهول واحد.

حقيقة 1: إذا كان $(n,a) = 1$ فإنه يوجد للتطابق الخطي $ax \equiv b\;(\bmod n)$ حل وهذا الحل وحيد.

البرهان: بالاعتماد على متطابقة بيزوه هناك صحيحين c,d بحيث ac+nd=1. بالضرب في b ينتج

a(bc)+n(bd)=b

إذا $a(bc) \equiv b\;(\bmod n)$ وبالتالي x=bc حلا للمعادلة. الآن افرض أن هناك حل آخر y للمعادلة. إذا

ay=b (mod n)

وبالتالي $ay \equiv ax\;(\bmod n)$ وهذا يقتضي أن (x-y)a يقبل القسمة على n وحيث أن $(n,a) = 1$ فإن ما بداخل القوس^[م] x-y يقبل القسمة على n أي أن x, y متطابقين معيار n وبالتالي الحل وحيد.

عندما لا تكون a أولية نسبيا مع n فقد يكون للمعادلة $ax \equiv b\;(\bmod n)$ حلا وقد لا يكون, على سبيل المثال إذا أخذنا المعادلتين

2x=3 (mod 6)

2y=4 (mod 6)

فإن المعادلة الأولى ليس لها حل ويمكن اختبار ذلك يدويا على كل فصول التكافؤ معيار 6. في حين أن المعادلة الثانية لها حل بل أكثر من حل, تحديد لها حلين هما x=2,5. العدد x=8 ليس حلا ثالثا لأن مساو للعدد 2 معيار 6. فيما يأتي نقدم الشرط الذي يضمن وجود حل لمثل هذه المعادلات وعدد هذه الحلول.

نظرية 1: إذا كان $(n,a) = d$ فإنه يوجد للتطابق الخطي $ax \equiv b\;(\bmod n)$ حل إذا وفقط إذا كان d يقسم b وفي هذه الحالة فإن عدد الحلول المختلفة معيار n يعطى بالعلاقة

$x = x_0 + \frac{{nk}}{d},\quad k = 0,1,2, \ldots ,(d - 1)$

حيث $x_0$ أي حل للتطابق.

هذه النظرية تعميم للحقيقة السابقة, وتبين أن للمعادلة عدد d من الحلول المختلفة. مختلفا كل واحد غير مطابق للآخر معيار n. البرهان يعتمد أساسيا على معارفنا عن حلول المعادلة الديفونتية الخطية.

البرهان:

للمعادلة $ax \equiv b\;(\bmod n)$ حلا إذا وفقط إذا كان للمعادلة الديفونتية ax+ny=b حلا وهذه المعادلة لها حل إذا وفقط إذا كان d يقسم b. الآن ليكن $(x_0 ,y_0 )$ أحد حلول المعادلة الديفونتية فإن الحلول الأخرى تعطى بالعلاقة

$x_k = x_0 + \frac{n}{d}k,\quad \quad y_k = y_0 - \frac{a}{d}k$

حيث k عدد صحيح, انظر http://www.mathramz.com/math/linear_diophantine_equations

السؤال الآن: متى تكون القيم x غير متطابقة معيار n.

افرض أن $x_{k_1 } \equiv x_{k_2 } \;(\bmod n)$ باستخدام بعض خواص التطابقات نجد أن

$x_{k_1 } \equiv x_{k_2 } \;(\bmod n) \Leftrightarrow \frac{n}{d}(k_1 - k_2 ) = nh \Leftrightarrow k_1 - k_2 = dh \Leftrightarrow k_1 \equiv k_2 \;(\bmod d)$

إذا الحلول تتطابق معيار n إذا وفقط إذا كانت الأعداد k تتطابق معيار d وبذلك فإن الحلول المختلفة هي

$x = x_0 + \frac{{nk}}{d},\quad k = 0,1,2, \ldots ,(d - 1)$

وبهذا تثبت النظرية.

مثال 1: المعادلة $6x \equiv 15\;(\bmod 21)$ لها حل لأن $(6,21) = 3$ يقسم 15 وعدد الحلول 3. لإيجاد الحلول ابحث عن $x_0$ بالتعويض بأحد الأعداد 0,1,2,3,...,20 وستجد أن أول حل يصادفك هو x=6. إذا الحلول المختلفة هي

$x = x_0 + \frac{{nk}}{d} = 6 + 7k,\quad k = 0,1,2$

أي x=6, 13, 20.

ولكن ماذا لو كان العدد n كبيرا؟ في هذه الحالة يفضل تحويل^[م] التطابق الخطي إلى المعادلة الديفونتية ax+ny=b ثم استخدام خوارزمية إقليدس أو الخوارزمية الاقليدية الموسعة لإيجاد الحل $(x_0 ,y_0 )$ بدلا من التعويض الذي قمنا به في هذا المثال.

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

مثال 2: حل المعادلة الديفونتية 2x-3y=6. هنا لديك خيارين , أما نكتب $2x \equiv 6\;(\bmod 3)$ أو $3y \equiv 6\;(\bmod 2)$ . لنختار الأولى وبالتجريب على القيم 0,1,2 نجد أن x=3 حل لهذا التطابق وهو الحل الوحيد معيار 3 إذا كل القيم x في حل المعادلة الديفونتية تأخذ الشكل