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

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

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

تعريفات

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

مبرهنة

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

برهان

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

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

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

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

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

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

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

إنتاج الحلول

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

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

برهان:

بما أنَّ $a x \equiv d (\mod n)$ لذا:

$a x_{0} \equiv a x (\frac{b}{d}) (\mod n)$

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

\equiv b (\mod n)

من هذا ينبع أنَّ $x_{0}$ هو حل كذلك.

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

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

حالات خاصة

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

امثلة

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

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

انظر أيضا

مصادر

^ "معلومات عن نظرية التطابق الخطية على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 2020-03-19.

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

بوابة نظرية الأعداد

[1] "معلومات عن نظرية التطابق الخطية على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 2020-03-19.

[1]