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

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

فليكن 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 nd-1)d\}  ولذا  |\left \langle a \right \rangle|=\frac nd 
### برهان
نبدأ البرهان بأن نبين أنَّ  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 nd-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 nd  مضاغفات الرقم d لذا فانه يتحقق: |\left \langle a \right \rangle|=\frac nd
## تحديد إذا ما يوجد حلول وعددها
# المعادلة 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 bd \pmod n  .

**برهان:**

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


 ax_0\equiv ax(\frac bd) \pmod n 

: \equiv d(\frac bd)\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 nd في حين أنَّ d=\mbox{GCD}(a,n) .

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


```matlab
% ax=b mod n نريد ان نحل المعادلة 
function x=MLES(a,b,n)
% نحسب اولا القاسم المشترك الاكبر حسب الخوارزمية اقليدس الموسعة
[d,x1,y1]=egcd(a,n);
% هذه المصفوفة فيها نحفظ كل الحلول
x=zeros(1,d);
%حينها يوجد حلول b|d  اذا تحقق  
if mod(b,d)==0
    % الحل الاول حسب المبرهنة
    x0=mod(x1*b/d,n);
    % انتاج باقي الحلول
    for k=1:d
        x(1,k)=mod(x0+k*(n/d),n);
    end
else
    % لا يوجد حلول
    x=[];
end
end
```


تعقيد وقت الخوارزمية هو  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 bd \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} 

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


* introduction to algorithms , CE Leiserson, RL Rivest, C Stein, TH Cormen - 2001


تصنيف:حسابيات نمطية
تصنيف:مبرهنات في نظرية الأعداد