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

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

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 في حل المعادلة الديفونتية تأخذ الشكل

x=3+3k

حيث k عدد صحيح وبالتعويض في المعادلة الديفونتية عن x وحلها في y نجد أن

y=2k

وبهذا نكون قد حلينا المعادلة الديفونتية.

لو استخدمت 3y \equiv 6\;(\bmod 2) وبالتجريب على القيم 0,1 ستجد أن y=0 حلا وبالتالي قيم y في حلول المعادلة الديفونتية تعطى بالعلاقة

y=0+2k

حيث k عدد صحيح وبالتعويض في المعادلة الديفونتية عن y وحلها في x نجد أن

x=3+3k

إذا فأي من التطابقين الخطيين كافي لاستنتاج حل المعادلة الديفونتية.

إذا كانت الأعداد في معادلة تطابق الخطي كبيرة فنقوم بعملية القسمة لاستبدال المعادلة بأخرى

مثال 3: للمعادلة 91y \equiv 98\;(\bmod 119) سبعة حلول وذلك لأن العدد 7 القاسم المشترك الأكبر لمعمل y وللعدد المعيار يقسم العدد 98. اقسم على 7

13y \equiv 14\;(\bmod 17) \to 17y - 4y \equiv 17 - 3\;(\bmod 17)

إذا - 4y \equiv - 3\;(\bmod 17) ونجد أن

y=5, 22, 39, 56,73, 90, 107, ...

وهي الحلول المختلفة معيار 119 للمعادلة.

استخدام المعكوس الضربي معيارn في حل التطابق الخطي

مثال 4: حل المعادلة 37x \equiv 5\;(\bmod 53).

لنحل أولا المعادلة 37x \equiv 1\;(\bmod 53), وهي ليست سوى إيجاد معكس 37 معيار 53. بإضافة وطرح 16x للطرف الأيسر نجد

- 16x \equiv 1\; \equiv 54\;(\bmod 53)

بالقسمة على -2 لدينا

8x \equiv - 27 \equiv 26 \equiv 132\;(\bmod 53)

وبالقسمة على 4 لدينا

2x \equiv 33\; \equiv 86(\bmod 53)

إذا x \equiv 43(\bmod 53). أو 43 هو المعكوس الضربي للعدد 37 معيار 53.

عودة الآن للمعادلة الأصلية 37x \equiv 5\;(\bmod 53) واضرب في معكوس 73 .

37 \cdot 43x \equiv 5\; \cdot 43(\bmod 53) \to x \equiv 215(\bmod 53) \to x\equiv 3(\bmod 53)

إذا x=3 هو حل المسألة.

مسائل

* اثبت أن للمعادلة x^2 \equiv 1(\bmod p^k ) حلين مختلفين, حيث p أولي فردي, k صحيح موجب.

* إذا وجد للمعادلة x^2 \equiv a(\bmod p), متى يكون وحيدا ومتى يكون غير وحيد, حيث p أولي.

مراجع

http://www.libraryofmath.com/linear-congruences.html

http://www.math.okstate.edu