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

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

فليكن 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}}$

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

1. المعادلة $ax\equiv b{\pmod {n}}$ يوجد لها حل فقط إذا ${\mbox{GCD}}(a,n)|b$ .
2. المعادلة $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).

% 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}}$ علينا ايجاد كل الحلول:

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