نظرية التطابق الخطية

في الرياضيات ونظرية الاعداد , نظرية التطابق الخطية تجيب عن السؤال : هل يمكن حل تطابق خطي ؟ , ومعادلة التطابق الخطي هي من الصورة التالية :

فليكن a,b,n ثلاث اعداد طبيعية مُعروفة المعادلة هي : ${\displaystyle ax\equiv b{\pmod {n}}}$ والمسألة هي ايجاد كل x يحقق المعادلة .

تعريفات

نرمز ب- ${\displaystyle \left\langle a\right\rangle }$ مولد الزمرة الجزئية ل- ${\displaystyle \mathbb {Z} _{n}}$ التي تتولد بواسطة a . بما انه يتحقق ${\displaystyle \left\langle a\right\rangle =\{ax{\pmod {n}}:x>0\}}$ للمعادلة اعلاه يوجد حل فقط إذا ${\displaystyle b\in \left\langle a\right\rangle }$ . من مبرهنة لاجرانج ينص على ${\displaystyle |\left\langle a\right\rangle |}$ يُقسم n . سوف نستخدم المبرهنة التالية لتحديد عدد الحلول للمعادلة وايضا لتحديد إذا ما يمكن حلها اصلا .

مبرهنة

فليكن ${\displaystyle d={\mbox{GCD}}(a,n)}$ حينها ${\displaystyle \left\langle a\right\rangle =\left\langle d\right\rangle =\{0,d,2d,\cdots ,({\frac {n}{d}}-1)d\}}$ ولذا ${\displaystyle |\left\langle a\right\rangle |={\frac {n}{d}}}$

برهان

نبدأ البرهان بأن نبين أنَّ ${\displaystyle d\in \left\langle a\right\rangle }$ وبما أنَّ ${\displaystyle d={\mbox{GCD}}(a,n)}$ لذا فانه حسب نظرية اقليدس الموسعة يوجد x,y عددان صحيحان حيث يتحقق ${\displaystyle ax+ny=d}$ لذا ${\displaystyle ax\equiv d{\pmod {n}}}$ لذا ${\displaystyle d\in \left\langle a\right\rangle }$ حسب التعريف .

بما أنَّ ${\displaystyle d\in \left\langle a\right\rangle }$ أيضا كل مضاعفاتها كذلك تابعة ل-${\displaystyle \left\langle a\right\rangle }$ وبما ان مضاعفات مضاعفات a هي أيضا مضاعفات a لذا فان ${\displaystyle \left\langle a\right\rangle }$ يحوي المجموعة ${\displaystyle \{0,d,2d,\cdots ,({\frac {n}{d}}-1)d\}}$ وبالتي يتحقق ${\displaystyle \left\langle d\right\rangle \subseteq \left\langle a\right\rangle }$ .

يتبقى ان نبرهن أنَّ ${\displaystyle \left\langle a\right\rangle \subseteq \left\langle d\right\rangle }$ . إذا ${\displaystyle m\in \left\langle a\right\rangle }$ حينها يوجد x بحيث يتحقق ${\displaystyle m=ax{\pmod {n}}}$ لذا فانه يوجد عدد صحيح y حيث يتحقق ${\displaystyle m=ax+ny}$ . بما أنَّ ${\displaystyle d|a}$ وكذلك ${\displaystyle d|n}$ لذا فانه يتحقق ${\displaystyle d|m}$ لذا فانه يتحقق ${\displaystyle d\in \left\langle d\right\rangle }$ .

لذا فانه يتحقق أنَّ ${\displaystyle \left\langle d\right\rangle =\left\langle a\right\rangle }$ . ننتبه إلى انه بين 0 و- n-1 يوجد ${\displaystyle {\frac {n}{d}}}$ مضاغفات الرقم d لذا فانه يتحقق : ${\displaystyle |\left\langle a\right\rangle |={\frac {n}{d}}}$

تحديد إذا ما يوجد حلول وعددها

1. المعادلة ${\displaystyle ax\equiv b{\pmod {n}}}$ يوجد لها حل فقط إذا ${\displaystyle {\mbox{GCD}}(a,n)|b}$ .
2. المعادلة ${\displaystyle ax\equiv b{\pmod {n}}}$ يوجد لها d حلول عندما ${\displaystyle d={\mbox{GCD}}(a,n)}$ أو لا يوجد حلول البتة

المقولتان 1+2 بالواقع هما استنتاج من المبرهنة اعلاه .

إنتاج الحلول

على الاقل حل واحد

فليكن ${\displaystyle d=GCD(a,n)}$ ولنفرض أنَّ ${\displaystyle d=ax+ny}$ حيث أنَّ x,y عددان صحيحان، إذا d|b حينها أحد الحلول للمعادلة ${\displaystyle ax\equiv b{\pmod {n}}}$ هو ${\displaystyle x_{0}=x\cdot {\frac {b}{d}}{\pmod {n}}}$ .

برهان :

بما أنَّ ${\displaystyle ax\equiv d{\pmod {n}}}$ لذا :

من هذا ينبع أنَّ ${\displaystyle x_{0}}$ هو حل كذلك .

إنتاج كل الحلول

لنفرض أن ${\displaystyle ax\equiv b{\pmod {n}}}$ ولنفرض أنَّ ${\displaystyle x_{0}}$ هو حل للمسألة، حينها للمعادلة هذه يوجد d حلول التي هي : ${\displaystyle \forall i\in \{1,2,\cdots ,d-1\}\ x_{i}=x_{0}+i\cdot {\frac {n}{d}}}$ في حين أنَّ ${\displaystyle d={\mbox{GCD}}(a,n)}$ .

خوارزمية حل المعادلات

الان بما انه يمكن إنتاج كل الحلول وقد برهنا على ذلك لذا فاننا الان صار بيدينا كل المقومات لخوارزمية تنتج هذه الحلول وهي كالتالي : (الخوارزمية بلغة MATLAB ) .

تعقيد وقت الخوارزمية هو ${\displaystyle O(\log n+{\mbox{gcd}}(a,n))}$ وذلك لاننا استخدمنا خوارزمية اقليدس مرة ثم الحلقة(loop) استخدمناها d مرات.

حالات خاصة

عندما ${\displaystyle GCD(a,n)=1}$ حينها يوجد حل واحد للمعادلة، كما انه يوجد حالة اخرى هي عندما b=1 حينها الحل المطلوب هو مقلوب العدد a ويمكن حسابه بواسطة خوارزمية اقليدس الموسعة فقط وهذا يجعل إنتاجه اسرع .

امثلة

معطاه المعادلة ${\displaystyle 35x\equiv 10{\pmod {50}}}$ علينا ايجاد كل الحلول :

1. نريد ان نحسب ${\displaystyle {\mbox{GCD}}(35,50)}$ والذي هو 5 , كما نحسب x و- y حيث أنَّ 35x+50y=5 , لذا فان قيمتهما هي x=3,y=-2 .
2. نفحص هل b|d ? حسب المعادلة b=10 و- d=5 . لذا فان الجواب نعم ولذا يوجد 5 حلول (حسب المبرهنات )
3. أول حل هو : ${\displaystyle x_{0}=x\cdot {\frac {b}{d}}{\pmod {n}}=3\cdot {\frac {10}{5}}{\pmod {50}}=6{\pmod {50}}}$
4. اما باقي الحلول فهي :
   • ${\displaystyle 6+1\cdot 10{\pmod {50}}=16{\pmod {50}}}$
   • ${\displaystyle 6+2\cdot 10{\pmod {50}}=26{\pmod {50}}}$
   • ${\displaystyle 6+3\cdot 10{\pmod {50}}=36{\pmod {50}}}$
   • ${\displaystyle 6+4\cdot 10{\pmod {50}}=46{\pmod {50}}}$

مقالات ذات صلة

• مبرهنة الباقي الصيني
• خوارزمية أقليدس
• زمرة دائرية

مصادر

موسوعات ذات صلة :

• موسوعة نظرية الأعداد