نظرية التطابق الخطية
المحتويات
قبل الخوض في التفاصيل، في الرياضيات ونظرية الاعداد، نظرية التطابق الخطية تجيب عن السؤال: هل يمكن حل تطابق خطي؟ , ومعادلة التطابق الخطي هي من الصورة التالية:
إضافةً إلى ذلك، فليكن a,b,n ثلاث اعداد طبيعية مُعروفة المعادلة هي: والمسألة هي ايجاد كل x يحقق المعادلة.
خوارزمية حل المعادلات
- % ax=b mod n نريد ان نحل المعادلة
- function x=MLES(a,b,n)
- % نحسب اولا القاسم المشترك الاكبر حسب الخوارزمية اقليدس الموسعة
- [d,x1,y1]=egcd(a,n);
- % هذه المصفوفة فيها نحفظ كل الحلول
- x=zeros(1,d);
- 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
وفي هذا الصدد، الآن بما انه يمكن إنتاج كل الحلول وقد برهنا على ذلك لذا فاننا الآن صار بيدينا كل المقومات لخوارزمية تنتج هذه الحلول وهي كالتالي: (الخوارزمية بلغة MATLAB).
إنتاج كل الحلول
وفي هذا السياق، لنفرض أن ولنفرض أنَّ هو حل للمسألة، حينها للمعادلة هذه يوجد d حلول التي هي: في حين أنَّ .
end
وفي السياق ذاته، تعقيد وقت الخوارزمية هو وذلك لاننا استعملنا خوارزمية اقليدس مرة ثم الحلقة (loop) استعملناها d مرات.
حالات خاصة
كذلك، عندما حينها يوجد حل واحد للمعادلة، كما انه يوجد حالة أخرى هي عندما b=1 حينها الحل المطلوب هو مقلوب العدد a ويمكن حسابه بواسطة خوارزمية اقليدس الموسعة فقط وهذا يجعل إنتاجه اسرع.
برهان
وعلى صعيد آخر، بما أنَّ كذلك كل مضاعفاتها كذلك تابعة ل- وبما ان مضاعفات مضاعفات a هي كذلك مضاعفات a لذا فان يحوي المجموعة وبالتي يتحقق .
وفي هذا السياق، لذا فانه يتحقق أنَّ . ننتبه إلى انه بين 0 و- n-1 يوجد مضاغفات الرقم d لذا فانه يتحقق:
ومن جهة أخرى، يتبقى ان نبرهن أنَّ . إذا حينها يوجد x بحيث يتحقق لذا فانه يوجد عدد صحيح y حيث يتحقق . بما أنَّ وكذلك لذا فانه يتحقق لذا فانه يتحقق .
وعلى صعيد آخر، نبدأ البرهان بأن نبين أنَّ وبما أنَّ لذا فانه حسب نظرية اقليدس الموسعة يوجد x,y عددان صحيحان حيث يتحقق لذا لذا حسب التعريف.
على الاقل حل واحد
- برهان:
- بما أنَّ لذا:
- من هذا ينبع أنَّ هو حل كذلك.
وعلى صعيد آخر، فليكن ولنفرض أنَّ حيث أنَّ x,y عددان صحيحان، إذا d – b حينها أحد الحلول للمعادلة هو .
تحديد إذا ما يوجد حلول وعددها
- المعادلة يوجد لها حل فقط إذا .
- المعادلة يوجد لها d حلول عندما أو لا يوجد حلول البتة
- المقولتان 1+2 بالواقع هما استنتاج من المبرهنة اعلاه.
- إنتاج الحلول
امثلة
معطاه المعادلة علينا ايجاد كل الحلول:
وفي هذا الصدد، نريد ان نحسب والذي هو 5 , كما نحسب x و- y حيث أنَّ 35x+50y=5 , لذا فان قيمتهما هي x=3,y=-2 .
- أول حل هو:
- اما باقي الحلول فهي:
- انظر كذلك
- مبرهنة الباقي الصيني
- خوارزمية أقليدس
- زمرة دائرية
تعريفات
مبرهنة
فليكن حينها ولذا
كذلك، نرمز ب- مولد الزمرة الجزئية ل- التي تتولد بواسطة a . بما انه يتحقق للمعادلة اعلاه يوجد حل فقط إذا . من مبرهنة لاجرانج ينص على يُقسم n . سوف نستعمل المبرهنة التالية لتحديد عدد الحلول للمعادلة وايضا لتحديد إذا ما يمكن حلها اصلا.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟