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

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

فليكن a,b,n ثلاث اعداد طبيعية مُعروفة المعادلة هي: $ax\equiv b(\mathrm{mod}n)$ والمسألة هي ايجاد كل x يحقق المعادلة.

تعريفات

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

مبرهنة

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

برهان

نبدأ البرهان بأن نبين أنَّ $d\in ⟨a⟩$ وبما أنَّ $d=\text{GCD}(a,n)$ لذا فانه حسب نظرية اقليدس الموسعة يوجد x,y عددان صحيحان حيث يتحقق $ax+ny=d$ لذا $ax\equiv d(\mathrm{mod}n)$ لذا $d\in ⟨a⟩$ حسب التعريف.

بما أنَّ $d\in ⟨a⟩$ أيضا كل مضاعفاتها كذلك تابعة ل-$⟨a⟩$ وبما ان مضاعفات مضاعفات a هي أيضا مضاعفات a لذا فان $⟨a⟩$ يحوي المجموعة $\{0,d,2d,\cdots ,(\frac{n}{d}-1)d\}$ وبالتي يتحقق $⟨d⟩\subseteq ⟨a⟩$ .

يتبقى ان نبرهن أنَّ $⟨a⟩\subseteq ⟨d⟩$ . إذا $m\in ⟨a⟩$ حينها يوجد x بحيث يتحقق $m=ax(\mathrm{mod}n)$ لذا فانه يوجد عدد صحيح y حيث يتحقق $m=ax+ny$ . بما أنَّ $d|a$ وكذلك $d|n$ لذا فانه يتحقق $d|m$ لذا فانه يتحقق $d\in ⟨d⟩$ .

لذا فانه يتحقق أنَّ $⟨d⟩=⟨a⟩$ . ننتبه إلى انه بين 0 و- n-1 يوجد $\frac{n}{d}$ مضاغفات الرقم d لذا فانه يتحقق: $\left|⟨a⟩\right|=\frac{n}{d}$

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

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

المقولتان 1+2 بالواقع هما استنتاج من المبرهنة اعلاه.

إنتاج الحلول

على الاقل حل واحد

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

برهان:

بما أنَّ $ax\equiv d(\mathrm{mod}n)$ لذا:

$a{x}_0\equiv ax(\frac{b}{d})(\mathrm{mod}n)$

$\equiv d(\frac{b}{d})(\mathrm{mod}n)$

$\equiv b(\mathrm{mod}n)$

من هذا ينبع أنَّ $x_0$ هو حل كذلك.

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

لنفرض أن $ax\equiv b(\mathrm{mod}n)$ ولنفرض أنَّ $x_0$ هو حل للمسألة، حينها للمعادلة هذه يوجد d حلول التي هي: $\mathrm{\forall }i\in \{1,2,\cdots ,d-1\}{x}_i=x_0+i\cdot \frac{n}{d}$ في حين أنَّ $d=\text{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+\text{gcd}(a,n))$ وذلك لاننا استخدمنا خوارزمية اقليدس مرة ثم الحلقة (loop) استخدمناها d مرات.

حالات خاصة

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

امثلة

معطاه المعادلة $35x\equiv 10(\mathrm{mod}50)$ علينا ايجاد كل الحلول:

1. نريد ان نحسب $\text{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}(\mathrm{mod}n)=3\cdot \frac{10}{5}(\mathrm{mod}50)=6(\mathrm{mod}50)$
4. اما باقي الحلول فهي:
   • $6+1\cdot 10(\mathrm{mod}50)=16(\mathrm{mod}50)$
   • $6+2\cdot 10(\mathrm{mod}50)=26(\mathrm{mod}50)$
   • $6+3\cdot 10(\mathrm{mod}50)=36(\mathrm{mod}50)$
   • $6+4\cdot 10(\mathrm{mod}50)=46(\mathrm{mod}50)$

انظر أيضا

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

مصادر

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