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

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

## تعريفات

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

## مبرهنة

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

### برهان

نبدأ البرهان بأن نبين أنَّ $d\in \left\langle a\right\rangle$ وبما أنَّ $d={\mbox{GCD}}(a,n)$ لذا فانه حسب نظرية اقليدس الموسعة يوجد x,y عددان صحيحان حيث يتحقق $ax+ny=d$ لذا $ax\equiv d{\pmod {n}}$ لذا $d\in \left\langle a\right\rangle$ حسب التعريف.
بما أنَّ $d\in \left\langle a\right\rangle$ أيضا كل مضاعفاتها كذلك تابعة ل-$\left\langle a\right\rangle$ وبما ان مضاعفات مضاعفات a هي أيضا مضاعفات a لذا فان $\left\langle a\right\rangle$ يحوي المجموعة $\{0,d,2d,\cdots ,({\frac {n}{d}}-1)d\}$ وبالتي يتحقق $\left\langle d\right\rangle \subseteq \left\langle a\right\rangle$ .
يتبقى ان نبرهن أنَّ $\left\langle a\right\rangle \subseteq \left\langle d\right\rangle$ . إذا $m\in \left\langle a\right\rangle$ حينها يوجد x بحيث يتحقق $m=ax{\pmod {n}}$ لذا فانه يوجد عدد صحيح y حيث يتحقق $m=ax+ny$ . بما أنَّ $d|a$ وكذلك $d|n$ لذا فانه يتحقق $d|m$ لذا فانه يتحقق $d\in \left\langle d\right\rangle$ .
لذا فانه يتحقق أنَّ $\left\langle d\right\rangle =\left\langle a\right\rangle$ . ننتبه إلى انه بين 0 و- n-1 يوجد ${\frac {n}{d}}$ مضاغفات الرقم d لذا فانه يتحقق: $|\left\langle a\right\rangle |={\frac {n}{d}}$

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

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

## إنتاج الحلول
### على الاقل حل واحد

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

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

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

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

الآن بما انه يمكن إنتاج كل الحلول وقد برهنا على ذلك لذا فاننا الآن صار بيدينا كل المقومات لخوارزمية تنتج هذه الحلول وهي كالتالي: (الخوارزمية بلغة MATLAB).
تعقيد وقت الخوارزمية هو $O(\log n+{\mbox{gcd}}(a,n))$ وذلك لاننا استخدمنا خوارزمية اقليدس مرة ثم الحلقة (loop) استخدمناها d مرات.

## حالات خاصة

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

## امثلة

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

## انظر أيضا

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