في الرياضيات ونظرية الاعداد، نظرية التطابق الخطية تجيب عن السؤال: هل يمكن حل تطابق خطي؟ , ومعادلة التطابق الخطي هي من الصورة التالية:
فليكن a,b,n ثلاث اعداد طبيعية مُعروفة المعادلة هي: والمسألة هي ايجاد كل x يحقق المعادلة.[1]
تعريفات[عدل]
نرمز ب- مولد الزمرة الجزئية ل- التي تتولد بواسطة a . بما انه يتحقق للمعادلة اعلاه يوجد حل فقط إذا . من مبرهنة لاجرانج ينص على يُقسم n . سوف نستخدم المبرهنة التالية لتحديد عدد الحلول للمعادلة وايضا لتحديد إذا ما يمكن حلها اصلا.
مبرهنة[عدل]
فليكن حينها ولذا
برهان[عدل]
نبدأ البرهان بأن نبين أنَّ وبما أنَّ لذا فانه حسب نظرية اقليدس الموسعة يوجد x,y عددان صحيحان حيث يتحقق لذا لذا حسب التعريف.
بما أنَّ أيضا كل مضاعفاتها كذلك تابعة ل- وبما ان مضاعفات مضاعفات a هي أيضا مضاعفات a لذا فان يحوي المجموعة وبالتي يتحقق .
يتبقى ان نبرهن أنَّ . إذا حينها يوجد x بحيث يتحقق لذا فانه يوجد عدد صحيح y حيث يتحقق . بما أنَّ وكذلك لذا فانه يتحقق لذا فانه يتحقق .
لذا فانه يتحقق أنَّ . ننتبه إلى انه بين 0 و- n-1 يوجد مضاغفات الرقم d لذا فانه يتحقق:
تحديد إذا ما يوجد حلول وعددها[عدل]
- المعادلة يوجد لها حل فقط إذا .
- المعادلة يوجد لها d حلول عندما أو لا يوجد حلول البتة
المقولتان 1+2 بالواقع هما استنتاج من المبرهنة اعلاه.
إنتاج الحلول[عدل]
على الاقل حل واحد[عدل]
فليكن ولنفرض أنَّ حيث أنَّ x,y عددان صحيحان، إذا d|b حينها أحد الحلول للمعادلة هو .
برهان:
بما أنَّ لذا:
من هذا ينبع أنَّ هو حل كذلك.
إنتاج كل الحلول[عدل]
لنفرض أن ولنفرض أنَّ هو حل للمسألة، حينها للمعادلة هذه يوجد d حلول التي هي: في حين أنَّ .
خوارزمية حل المعادلات[عدل]
الآن بما انه يمكن إنتاج كل الحلول وقد برهنا على ذلك لذا فاننا الآن صار بيدينا كل المقومات لخوارزمية تنتج هذه الحلول وهي كالتالي: (الخوارزمية بلغة 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
تعقيد وقت الخوارزمية هو وذلك لاننا استخدمنا خوارزمية اقليدس مرة ثم الحلقة (loop) استخدمناها d مرات.
حالات خاصة[عدل]
عندما حينها يوجد حل واحد للمعادلة، كما انه يوجد حالة أخرى هي عندما b=1 حينها الحل المطلوب هو مقلوب العدد a ويمكن حسابه بواسطة خوارزمية اقليدس الموسعة فقط وهذا يجعل إنتاجه اسرع.
امثلة[عدل]
معطاه المعادلة علينا ايجاد كل الحلول:
- نريد ان نحسب والذي هو 5 , كما نحسب x و- y حيث أنَّ 35x+50y=5 , لذا فان قيمتهما هي x=3,y=-2 .
- نفحص هل b|d ? حسب المعادلة b=10 و- d=5 . لذا فان الجواب نعم ولذا يوجد 5 حلول (حسب المبرهنات)
- أول حل هو:
- اما باقي الحلول فهي:
انظر أيضا[عدل]
مصادر[عدل]
- introduction to algorithms , CE Leiserson, RL Rivest, C Stein, TH Cormen - 2001