مرجع
آخر الزيارات

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

490 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: في الرياضيات ونظرية الاعداد، نظرية التطابق الخطية تجيب عن السؤال: هل يمكن حل تطابق خطي؟. تتناول المقالة 9 أقسام، منها «خوارزمية حل المعادلات»، «إنتاج كل الحلول» و«end».
المحتويات
  1. خوارزمية حل المعادلات
  2. إنتاج كل الحلول
  3. end
  4. حالات خاصة
  5. برهان
  6. على الاقل حل واحد
  7. تحديد إذا ما يوجد حلول وعددها
  8. امثلة
  9. تعريفات

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

إضافةً إلى ذلك، فليكن 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 . سوف نستعمل المبرهنة التالية لتحديد عدد الحلول للمعادلة وايضا لتحديد إذا ما يمكن حلها اصلا.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.