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

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

فليكن a,b,n ثلاث اعداد طبيعية مُعروفة المعادلة هي:  والمسألة هي ايجاد كل x يحقق المعادلة.

تعريفات 
نرمز ب-  مولد الزمرة الجزئية ل-  التي تتولد بواسطة 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

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