بسم الله الرحمن الرحيم هذه هي المحاضرة الثامنة
مساق رياضيات منفصلة طلاب وطالبات الجامعة
الإسلامية قسم الحوسبة المتنقلة كلية العلوم وكلية
تكنولوجيا المعلومات المحاضرة اليوم إن شاء الله
هنحكي عن اللي هو Section 4.4 اللي هو solving
congruences أو حل التطابقات هنحل .. هنحكي عن شغلتين
في حل التطابقات أول شيء حل تطابق خطية لحالها و
بعدين حل system of linear congruences أو اللي هي
تطابقات آنية في آن واحد لمجموعة من التطابقات و
هنشوف كيف اللي هو نستخدم ال chinese remainder
theorem والـ back substitution method يعني
طريقتين هنحل فيهم التطابقات الأنية في البداية
خليني نتعرف شو معناه الـ Linear congruences
congruences شيء مشابه لللي هي الـ Linear equations
ولكن بتظهر بدل علامة المساواة بتظهر علامة اللي
هي التطابق وبتظهر اللي هو المقياس بالضبط ايش
بنقول؟ بنقول a congruence of the form اللي هي Ax
طابق B modulo M هذه اللي هي بنسميها Linear
congruences لأن X عبارة عن أس واحد وعندي الـ a والـ
b بتكون أعداد معطية والـ m عدد معطي والمطلوب اللي
هو إيجاد قيمة المجهول x هذه بنسميها اللي هي linear
congruences حل الـ linear congruences هو كما يلي
اللي هو بنقصد في حل الـ congruence ax طابق b
modulo m هي إيجاد كل قيم x اللي هي بتحقق اللي هي
التطابق اللي عندي الآن قبل ما نشوف كيف نحل
التطابقات الخطية خلينا نتطلع بس على شغلة اللي هي
بتلزمنا في حل التطابقات اللي هو بنقول عن an
integer a bar such that a bar في a طابق الواحد
modulo m بنسمي في هذه الحالة اللي هو الـ a bar هو
عبارة عن الـ inverse للـ a modulo m إذاً العدد اللي
بنجيبه لما نضربه في الـ A يطابق الواحد modulo M
بنقول عنه هذا A bar اللي هو عبارة عن الـ inverse للـ
A الـ inverse of A modulo M خلينا نتطلع على مثال
بسيط الآن بقول لي عندي خمسة هي inverse of تلاتة
modulo سبعة الخمسة هي inverse للتلاتة modulo سبعة
يعني الخمسة معكوس التلاتة بالنسبة للمقياس السبعة
لأن لو ضربنا الخمسة في التلاتة بخمستعش الخمستعش
دائماً طابق الواحد modulo سبعة عارفين ايش معنى تطابق
الواحد modulo سبعة يعني الخمستعش لو شيلنا مضاعفات
السبعة منها هنلاقي بضل المتبقي بس واحد ماشي الحل
فعشان يكون 15 طابق الواحد modulo سبعة الآن عند الـ
linear congruencies هتنستخدمها هنستخدم في إيجاد
قيمة الـ X فيها اللي هو الـ inverse تبع العنصر
هنستعين فيه لإيجاد اللي هو الحل في الأول خلينا
نشوف هالنظرية اللي بتشرّع لنا اللي هو اللي هي إن
يكون فيه الـ congruence حل أو اللي مالهاش بس قبل ما
ناخد نظرية بتشرّع لنا إن العدد له اللي هو inverse
ولا مالقوش تقولنا نظرية if a and m are relatively
prime integers إذا كان الـ a والـ m العدد ومقياسه
are relatively prime integers and M أكبر من واحد
then an inverse of A modulo M exists يعني دائماً
دوم لما يكون العامل المشترك بين الـ A والـ M
بساوي واحد بتضمن وجود اللي هو inverse للـ A
modulo M ماشي الحال خلينا نشوف مثالنا هنا
الخمسة
is an inverse of تلاتة modulo M modulo السبعة هذه
وجدناها احنا قبل شوية نلاحظ إن اللي هو الخمسة والـ
لي هي التلاتة اللي بدنا نوجد لها inverse هي
والسبعة ايه شمالها relatively prime الآن this
اللي هو inverse is unique unique بس ايه شماله؟
modulo سبعة يعني وحيد بالنسبة لمقياس سبعة، ايش يعني؟
يعني اللي هو من واحد لعند سبعة مافيش غير inverse
واحد للتلاتة modulo اللي هو سبعة اللي هو مين لجناه
خمسة لكن في غيره بعد السبعة كل الأعداد اللي هي لما
نضيف لها نضيف مضاعفات السبعة على الخمسة بتطلع برضه
ايش عبارة عن inverse ايش يعني؟ يعني الخمسة لجناه
اللي هو inverse للتلاتة modulo سبعة الآن لو ضفنا على
السبعة الخمسة كمان سبعة بصير اتناشر برضه inverse
للتلاتة التسعة اتعش برضه inverse للتلاتة لو طرحنا
سبعة من الخمسة نقص اتنين برضه inverse لمين للتلاتة
modulo سبعة إذا نقصد احنا الـ uniqueness بعنوان هذا
يعني أنه يوجد inverse واحد
A bar أقل من M وهو inverse لـ A modulo M وكل inverse آخر
لـ A modulo M بيكون طابق لـ A bar modulo M الـ 12 والـ نقص 2
والـ 19 وكل هذول برضه بيكونوا inverse للتلاتة
modulo 7 لأن اللي هنا كلهم بطابقوا من الخمسة اللي
لجيناها modulo 7
طيب شوف خلونا نجد كيف نجد الـ inverse اللي هو للعدد
لأي عدد بدنا إياه بالنسبة لقياس معين الـ Euclidean
algorithm اللي هي خوارزمية القسمة الأوروبية
coefficients اللي هو بتعطينا gives us a systematic
approach to find اللي هو ايش to find inverse كيف؟
اللي هو .. اللي هو كمالي ابني يجيب .. يطلب إن هو
فيلم تلقى find an inverse of 3 modulo 7 العدد
عشان إن صغير سهل إن نعملهم .. نوددهم زي قبل ما
شوية بالتحذير أو كده بس ما ينفعش بالتحذير الآن بدنا
نودي الطريقة .. نلاقي طريقة لإيجادها الطريقة عن
طريقة الـ Euclidean القسمة أول حاجة نعمل مشترك اللي
على بين 3 و 7 بيساوي واحد إذا مضمون من النظرية اللي
هي واحد إن نلاقي inverse للتلاتة modulo منين سبعة
يعني الـ inverse modulo of تلاتة modulo سبعة exist
always خلينا نشوف كيف بدنا نوجده الآن بتيجي السبعة
بتيجي اسمها التلاتة سبعة بيساوي 2 في تلاتة
والمتبقي ايش واحد الآن جهزة الآن الواحد هو عبارة
عن العامل المشترك الأعلى بين التلاتة والسبعة هذا
عارفينه احنا من قبل اللي هي الطريقة الآن واحد بقت
وع صورة Linear combination من التنين اللي هي
بيزوتز كوفيه عن طريق اللي هو ايه اللي هي بيزوتز
كوفيه coefficients بيصير عند الواحد بيساوي بنجلها
ده بيصير نقص اتنين في تلاتة زائد واحد في سبعة الآن
أنا مين اللي بده اوجدله اللي هو الـ inverse التلاتة
modulo مين modulo السبعة معامل التلاتة في هذا الـ
linear combination اللي هو نقص اتنين هو اللي هيطلع
لنا اللي هو مين الإنفرس المطلوب and see that نقص
اتنين and واحد هي الـ Bezout coefficients اللي
معامل التلاتة هو عبارة عن نقص اتنين هو اللي هيكون
inverse of تلاتة modulo مين modulo سبعة إذا الأمر سهل
عشان نوجد الـ inverse بس بنيجي اللي هو بنكتب الـ ..
بناخد .. بنكتب الـ .. الواحد اللي هو المشترك الأعلى
بينهمأزالينا الـ combination بين التلاتة والسبعة
كيف هذا بطريقة اللي هو الـ division algorithm اللي
اتعلمناها وبكون معامل اللي هو التلاتة هو عبارة عن
الـ inverse للتلاتة modulo السبعة الآن اللي جينا نقص
اتنين إذا بلاقي البجيهات كلها اللي بدك تضيف على
السبعة على نقص اتنين سبعة بيطلع الخمسة اضيف عليه
كمان سبعة بيطلع اتناشر اضيف عليه كمان سبعة بيطلع
تسعة عشر لو طرحت منه سبعة بيطلع نقص تسعة كل هذول
هو عبارة عن Inverses اللي هي التلاتة modulo سبعة
لكن واحد منهم الـ unique هو الخمسة اللي من الواحد
لعند مين لعند السبعة زي ما حكينا قبل شوية الآن
ناخد مثال على أعداد كبيرة نشوف كيف نوجده ناخد
المثال الثاني هذا find an inverse of 101 modulo
4620 نشوف الآن ايش اللي بنسويه الطريقة كمالي
باجي بقسم هذا على 101 بطريقة الـ Euclidean اللي هو الـ division
algorithm لما أصل في الآخر للمتبقي صفر بيكون أول
واحد قبل المتبقي صفر هو الـ greatest common divisor
زي ما قلنا قبل هيك، بنّه بتجيب اللي هو الـ grades
common divisor as a linear combination of الاثنين
وبكون المعامل الـ 101 هو الـ inverse المطلوب، خلّينا
نشوف الكلام هذا عمليًا الآن، أولًا استخدم الـ
Euclidean algorithm to show that الـ greatest common divisor
بين هذول العددين بيساوي واحد، ايش بنسوي؟ بنقسم هذا
على هذا، جسمنا على 101، حصل قسم 45، المتبقي 75، باجي جسم
101 على 75، بيطلع المتبقي 26، بعاود الـ 75 بنفس الطريقة
على الـ 26، بيطلع المتبقي 23، الـ 26 مع الـ 23، بضل المتبقي
3، الـ 23 مع الـ 3، بضل المتبقي 2، هذا عارفين، عشان هيك
أنا من السرعة، اللي هي التلاتة مع الاتنين، بطلع
المتبقي واحد، الاتنين اللي هو مع اللي هو الواحد
اللي هو بضلّش متبقي، فبكون أول واحد قبل اللي هو ما ضلّش
متبقي، هو ده العام المشترك الأعلى بين العددين اللي
هو 4621، الآن بده
مش هنا، أنا مش غرضي بس أوجد العام المشترك الأعلى
بين الواحد، لأ، غرضي أن أكتب الواحد، بالرجوع زي ما كنا
نرجع قبل هيك، أزلنا الـ combination من الـ 4621
والـ 101، وعارفين الطريقة احنا، واحد بتساوي تلاتة ناقص
واحد في واحد في اتنين، الآن الاتنين هنا بجيبه من
هنا، بجيبه هذا ناقص هذا، وبعوّض عنهم، وبافردها الآن
اللي بيطلع عندي هو، 4621 ناقص 13 في
8 في 3، بتجيب الآن قيمة من التلاتة، بشيل
التلاتة، وبجيب قيمة تهيئتها، وبنعوّضها، وبضلّ باستمر
كل شغل بتجيبها من اللي جابلها، لما نقصل في الآخر
لآخر لينا الـ combination، بيطلع واحد، بسّوء ناقص تلاتة
35 في 4621 زائد 1601 في 101، لاحظ أنا أنا قدرت أكتب الواحد
بأزالي بالـ Bézout، الـ Bézout الـ coefficient سيها مقصّ
35 و 1601 لـ 4621 و 101، يعني واحد لينا
combination من هذا ومن هذا، بيكون معامل الـ 101
اللي هو 1601 هو اللي is an inverse of 101 mod
4621، ولو جيت أنت تتأكد من كلامك، اضرب الـ 1601 في الـ
101، هتلاقي بيطلع الرقم هذا، هذا الرقم لو جسمته على
4621، هيطلع المتبقي واحد، يعني هذا يطابق الواحد mod
4621، إذا فعلاً هذا عبارة عن الـ inverse لهذا mod
4621، حسب ما عرفنا قبل بشوية، هكذا فإننا وجدنا
الانفرس لأعداد أو أرقام كبيرة، الآن بدنا نستخدم
الانفرس لإيجاد الـ linear congruences، بدنا نستخدم
الانفرس في إيجاد الـ linear congruences، ايش الفكرة؟
نشوف كيف نستخدم الانفرس في إيجاد الـ linear congruences، ايش الفكرة؟
نشوف كده ايش الفكرة في استخدام الانفرس، نستطيع
تحسين الانفرس Ax، ويطابق بـ mod By multiplying
both sides by A bar، الـ A bar اللي هي من الـ inverse
لو ضربناها من الجهتين في A bar، فبيصير A bar في A في
X بيساوي A bar في B، لأن A في A bar في X، الـ A في A
bar ما هي بطابق الواحد، يعني وكأننا بنكون شيلنا
الـ A في الـ A bar، وصار في عندي الواحد لحاله، يعني
صارت الـ X قاعدة لحالها، يعني صارت الـ X بتساوي A bar
في B modulo M، هي الحل، بتنشوف كيف، What are the
solutions of the congruence 3x يطابق 4
mod 7؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟يطابق
4 mod 7؟ يطابق
4، الآن واضح إنه اللي هو صار عندي الواحد هو الـ
greatest common divisor بين التلاتة وبين السبعة
وبيساوي 7 ناقص 2 في 3، يعني طلع عندي ناقص
2 هو الـ inverse للي هو التلاتة modulo 7
زي ما احنا اتعلمنا الآن، بضرب الجهتين في ناقص 3
اضرب هنا في ناقص 3 وهنا في ناقص 2 اللي هو
الـ inverse، ناقص 2 في ناقص 2 بيصير عبارة عن
ناقص 2 في 3 يطابق ناقص 2 في 4 mod
7، الآن ايش هذه عبارة عن ناقص 6 يطابق ناقص
8 mod 7، الـ ناقص 6 هي الواحد، هي تطابق
الواحد، لإنه هي ناقص 2، ناقص 3 الـ inverse وهذا
الفكرة أصلًا، الآن ناقص 6 يطابق الواحد mod 7، لأن
ناقص 6 ناقص 1 تصبح ناقص 7، السبعة تجسم ناقص
7، إذا فعلاً كلامنا صحيح، إذا ناقص 6 بيصير
مكانها اللي هي عبارة عن 1، لأن الواحد يطابق ناقص
6، فبيصير عند الـ X يطابق ناقص 8 mod 7
الآن ناقص 8 اللي هي شيله، ضفّوله 7، بيصير عندّه
اللي هو ناقص 1، لو ضفّنوله 7، بتصير 6،
طب مش اللي بيسويه بالإضافات، بالإضافات، ما هو إضافات
الـ 7، أي إضافة للسبعة تطابق صفر mod 7، كيف
يعني؟ ايش اللي بقوله؟ ده نشوف، لإن هذه الـ ناقص
8 يطابق الـ 6 mod 7، ايش عرفك الـ 6؟
ضفت على الـ 7 على الـ ناقص، الآن ضفت اللي هي مضاعفات
الـ 7، 7 و 7، 14، 14 ناقص 8
بتطلع 6، عشان هيك طلعت 6، طب بتطلع هذا الكلام
صحيح؟ اه، مضمون، ليش؟ تعال، 7 بتجسم ناقص 8،
ناقص 6، اللي ناقص 14، الـ 7 بتجسم مين؟ ناقص
14، يعني دائماً دائماً لو كان عندي 3، خلينا
نقول 3، 3 لو ضفّنلها 7، بيصير 10، الـ 10
يطابق الـ 3 mod 7، اللي هو ضفّنلها كمان 7
اللي هي 17، و 17 يطابق الـ 3 mod
7، يعني دائماً يا جماعة، الآن العدد لو ضفّت له جد ما
ضفته من المقياس بظلّ يطابق نفسه، يعني لو كان عندنا في
الأصل 5، وضفّنلها 7، بيصير 12، ويطابق 5
وضفّنلها كمان 7، بيصير 19، ويطابق 5، ولو
طرحت منه 7، برضه بتظلّ المتطابقات، عشان هيك هذه
بتساعدنا كثير بعد شوية في حلّ المتطابقات، إذا صار
عند الـ X يطابق الـ 6 mod مين؟ mod 7، ومنه بيكون
الـ solutions are the integers اللي هي مدام x يطابق
الـ 6، إذا صار عند الـ 6، واللي هو ضفّله 7، اللي
هي 7 بيصير 6 و 7 اللي هي 13، ضفّله
كمان 7 بيصير اللي هو 13 و 7، 20، اطرح
منه 7، من الـ 6 بتطلع ناقص 1، اطرح منه كمان
7، ناقص 8، اطرح منه كمان 7 بيصير ناقص 15
إذا كل دولة اللي هنحلّ الـ x يطابق الـ 7، أو حلّ
الـ x يطابق الـ 6 modulo 7
الآن بعد شوية هتلاقيني بقى أريحكم في الحل هذا، يعني
بدون حتى ما نستخدم اللي هو الـ inverses وكده
هتلاقيني باستخدم اللي هو طريقة اللي هي بتعتمد على
مضاعفات السبعة، بنضيف أو نطرح، وبنخلي الـ X لحاله، و
الباقي هان لحاله، فبتكون الحلول سهلة بعد شوية إن
شاء الله، هنشوف هذه الطريقة في الـ Chinese remainder
theorem، اللي هو نثبت هذه الطريقة اللي أخذناها الآن
إن شاء الله، وبعد شوية نشوف الـ Chinese remainder
يعني، خلّينا نجي لـ Chinese remainder theorem، أو
نظرية الباقي الصينية، المشهورة في بعض المثال كانت
تطرح قديمًا، أحد المثال هو أحد العلماء الصينيين، Sun
Tzu، states the following، بيقول اللي بدي عدد اللي هو
يقبل القسمة على 3، والمتبقي له 2، وهو نفسه لو
قسمته على 5، المتبقي 3، وهو نفسه لو قسمته
على 7، المتبقي 2، بيقول ايش هذا العدد؟
الآن طبعًا اللي هو الفكرة الآن ايش هي؟ إن احنا بنحول
اللي هي الحديث هذا إلى تطابقات، ايش علاقة الموضوع
بالتطابقات؟ احنا بنقول دائماً إن العدد دائماً يطابق
اللي هو المتبقي له لو قسمناه على عدد ما، يعني الآن
لو أجينا قسمنا عدد على اللي هو 3، وكان المتبقي
2، معناته صار العدد يطابق الـ 2 mod 3
عشان هي فرضنا، نفرض إن العدد اسمه X، هذا الـ X إذا
قسمته على ثلاثة هيظل اثنان عشان هيك اختارت له
التطابق X تطابق اثنين مدولة ثلاثة بس هو قال طب أنا
بدي العدد نفسه يقبل ما يلي أنه لو اجيت قسمته على
خمسة يظل المتبقي ثلاثة ما دام يقبل اللي بدك تقسمه
على الـ X تقسمه على خمسة و يظل ثلاثة معناته هذا الـ
X حيطابق المتبقي له الثلاثة مقياس مين؟ مقياس الخمسة
اللي قسمته عليه لأ و طلب كمان أكثر من هيك قال لأ بدي
نفس العدد اللي هو لو قسمته على سبعة يظل المتبقي
اثنان ترجمها برضه لصورة المتطابق احنا نقول الـ X
بيطابق المتبقي modulo المقسوم عليه اللي هو مين؟
السبعة عشان هيك قال اللي هي الـ X اللي أنتو
طلبتوها يا جماعة اللي لو قسمناها ثلاثة بيظل اثنان و
قسمناها خمسة بيظل ثلاثة و قسمناها سبعة بيظل اثنان
نحن نترجمها إلى اللي هو system of linear
congruences اللي هو X وطابق اثنين modulo ثلاثة X
وطابق الثلاثة modulo خمسة X وطابق الاثنين modulo
سبعة يعني X وطابق اللي هو المتبقي modulo المقسوم
عليه لما نقسم X على ثلاثة X تطابق اللي هو الثلاثة
المتبقية لما نقسم X على خمسة X تطابق اللي هي
المتبقي اثنان لما نقسمها على سبعة فاتحولت إلى
تطابقات اللي هي ده تنحل في نفس الوقت عشان هي كانت
نسميها system of linear congruences وهذه اللي هي
اللي بيحلها عادة اسمها الـ Chinese remainder
theorem اللي الآن احنا هندرس إيه اللي هو كيف اللي
هي إيش النظرية بتقول متى بيكون حل و كيف بنحل اللي
هو التطابقات The Chinese remainder theorem بتقول ما
يلي بالضبط Theorem 2 بتقول let M1, M2, Mn be
pairwise relatively prime positive integers
greater than one يعني هدول M1 و M2, Mn كلهم
positive integer أكبر من واحد و relatively prime
ونفترض a1 و a2 و aN are arbitrary integers، then
the system X تطابق الـ a1 a1 عدد، X تطابق الـ a2 a2
عدد، X تطابق الـ aN aN عدد، طبعاً هذه مدولة M1 و
هذه مدولة M2 ومدولة MN لو كان في عندي system of
linear congruences بالشكل هذا و كلهم المجهول فيهم
X و الـ M1 و الـ M2 و الـ MN كلهم relatively prime
بتقولك الـ Chinese remainder theorem إذا يوجد حل
مشترك وحيد لهذه المجموعات اللي هو has a unique
solution modulo M اللي هو Mم1 م2 في مين؟ في Mn يعني
بتقولك الآن اللي هي chinese remainder theorem لو
كان عندك فيه system من اللي هو الـ linear
congruences هذه تطابق أي واحد مدولة m واحد والـ X
تطابق اثنين مدولة m اثنين تطابق en modulo mn هذه
بيكون solution unique لها مدولة m بس بشرط أن m1 و
m2 و mn يكون in pair wise relatively prime يعني كل
اثنتين مع بعض العامل المشترك الأعلى بينهم بيساوي
واحد that is there is a solution x زي ما بقول x
أكبر أو يساوي صفر أو أصغر من M يعني لأنه مدولة M يعني
من عند الصفر لعند الـ M أو من عند الواحد لعند الـ M
نفسها أو من الصفر لعند الـ M ناقص واحد and all
other solutions are congruent مدولة M to this
solution يعني أي solution ثاني هتلاقيه هيلاقيه
اللي هو العدد اللي لاجيناه زائد اللي هو مضاعفات من
الـ M يعني يطابق الـ M اللي هو Modulo .. يطابق الـ ..
الـ .. الـ X Modulo اللي هي الـ M الآن نشوف كيف بدنا
نستخدم الـ Chinese remainder theorem to find a
solution الآن تركز معايا هذه الـ .. الـ .. الـ ..
التطابقات اللي موجودة عندك بدك توجد الحل المشترك
بينهم أولاً نسمي m واحد capital m واحد اللي هي
عبارة عن حاصل الضرب هذا m على m واحد m اثنين
capital m اثنين capital بتساوي m على m اثنين
small m ثلاثة capital بتساوي m على m ثلاثة
small وهكذا لما نخلص على كل المعادلات إذا وكأن كل
معادلة .. كل تطابقة من هدول بجيبلهم M و M كبيرة
هذا هي .. هتلزمني بعد شوية ركز فيها بعد ما سميتها
بدي آجي أحل التطابقة التالية التطابقة اللي هي مايا
ليه M1 في Y1 تطابق الواحد مدولة مين؟ M1 مين M1 هذه
اللي هي تبعت هذه من M1 هذه اللي قسمتها على M1 small
M على M1 small إذا بعد ما قسمت هذه بحل التطابقات
التالية طبعاً التطابقات هدولة هيكون عددهن لأن قلت
Mk و Yk تطابق الواحد مدولة Mk حيث اللي هي Yk مجهول
هو اللي بتوجد من حل هذه والـ k هذه من واحد لعند n
بعدد مين؟ اللي هي التطابقات اللي موجودة في الأصل
إذا بدي الآن الخطوة اللي بعدها بعد ما سميت الـ mk
بالطريقة هذه بدي أحل التطابق mk في yk mk بتكون
معطية عدد أو جدناه و الـ yk هو المجهول اللي بده
يجده تطابق الواحد modulo mk بعد ما حل التطابق هذه
وجد الـ yk يعني أنا بدأ أوجد الـ y1 و الـ y2 لعند الـ
yn بعد موجودة هنا بقول the unique solution modulo
m is given by إذن هذا قانون حيطلع عليه إيش؟ اللي هو
الـ solution x بتساوي a1 m1 a1 هذا اللي أنا ظهرته الـ
M1 هذه مين؟ اللي هي من هنا الـ Y1 اللي هي اللي
بتغلبنا هذه اللي هي الـ solution اللي هنجدها الآن
زائد نفس الشيء لمين؟ للمعادلة الثانية A2 اللي هي في
A2 هنا طيب مضروبة في M2 M2 هذه اللي جبناها من هنا
الـ Y2 اللي جبناها من هنا لما أصل لآخر معادلة
اللي هي AN في MN تبعتها في YN تبعتها اللي حليتها
هنا فبتطلع هذه هي الـ X اللي أمامي هي عبارة عن الـ
solution الـ unique solution لأ الـ system هذا كله
مدولة مدولة m وحاصل الضرب الكلية الآن هي الثلاثة
خطوات اللي بدنا نختوها من أجل حل اللي هو system of
linear equations تسمية mk أول شيء وبعدين نحل هذه
التطابقة وبعدين نعوض في هذه بيكون خلصنا اللي هو
حلنا اللي هو سؤال الـ Chinese remainder theorem
والآن نيجي إلى اللي هو مثال عملي لتطبيقه خلّيني أنا
أشوف مثال عملي على اللي هو chinese remainder
theorem بقول consider the three congruences from
some two problem two problem اللي قبل شوية عرضناها
يعني X تطابق الاثنين مدولة ثلاثة X تطابق الثلاثة
مدولة خمسة X تطابق الاثنين مدولة سبعة الآن هذه
بتمثلي A1 هذه بتمثلي A2 هذه بتمثلي A3 اللي هحتاجين
بعد شوية هذه M1 هذه M2 هذه M3 خلّينا نشوف الآن بدنا
ناخد اللي هو الـ .. الـ M اللي هي حاصل ضرب ثلاثة في
خمسة في سبعة mات مع بعض يعني M هذه هي ثلاثة في
خمسة في سبعة اللي هي مئة وخمسة منها بدنا نحسب الـ
M واحد capital زي ما شوفنا قبل شوية M واحد capital
هي عبارة عن اللي هو المئة وخمسة بنجسمها على
الثلاثة بيطلع جداش خمسة وثلاثين M اثنين capital
هذه اللي هي المئة وخمسة مجسمة على الخمسة هذه اللي
هي بيطلع واحد وعشرين M3 هي 105 عالية 7 اللي هنا
بتطلع جداش 15 الآن نيجي للخطوة المركزية المهمة لأن
we solve the congruences التالية بدنا نحل المين
اللي هو M1 Y1 تطابق الواحد مدولة M1 الآن M1 جداش
أودتنا هي اللي هي عبارة عن 35 يصير 35 Y1 تطابق
الواحد مدولة ومين؟ M1 اللي هي جداش 3 بدنا نحل هذه الآن
طريقة الحل هذه ماعنش نقعد ندور على اللي هو الـ
inverse لهذا ومش عارف إيش لأ لأ لأ أسهل لكم كثير
كثير كثير اللي هو إيش؟ من نيجي بنشيل من خمسة و
ثلاثين كل مضاعفات من الثلاثة الآن بنشيل من هذه
اللي هو عبارة عن مضاعفات الثلاثة أقرب شيء للثلاثة
خمسة وثلاثين يعني على الثلاثة بتطلع اللي هي
المتبقي جداش اثنان لأنه بيصير 11 والمتبقي اللي هو 2
يعني بقسم 35 على 3 بيطلع اللي هو عدد مدولة المتبقي
المتبقي هو اللي بيبقى بيبقى بيضل لأن هذا الـ 35
بيصير يطابق المتبقي 32 مدولة مدولة اللي هي الثلاثة
ماشي الحال إذا انطلقنا من 35 مضاعفات الثلاث اللي
هي 33 اللي هي بيبقى الجداد 2 بيصير 2 Y1 تطابق الآن
الواحد بيصير اثنين و أي واحد وطابق الواحد بس
عشان أنا بتدجسم بعد شوية بدي أحول الواحد لرقم زوجي
ايش أحول رقم زوجي؟ واحد بطابقه الآن بضيف له ثلاثة
أو بطرح منه ثلاثة بيصير اللي هو عدد زوجي طب بنفع
آه لأن لو ضفت له ثلاثة بيصير الأربعة الأربعة بتطابق
الواحد مدله مين مدله ثلاثة إذا أنت لها نوّهان ضيف زي
ما بدك من مضاعفات الثلاث أو اطرح مضاعفات الثلاث
للوصول للأعداد القليلة اللي بتقدر تستخدمها زي ما
بدك بظل نفس ال issue متطابق
بينفع تجسم إذا العامل المشترك الأعلى بين اللي بده
يجسمه وبين الثلاث ايش بيساوي واحد وهي العامل
المشترك الأعلى بين الثلاث وبين الواحد بين الـ 3 و
بين الـ 2 و 1 إذا أنا بقول شيء سهولة بقول على 2
بظهر Y1 على 2 بظهر 2 فبيصير Y1 تطابق الـ 2 مدلة 3
هي عبارة عن حل الـ congruence هذه شايفين مثلًا حل
الـ linear congruence أسهل من ما نقعد نودد ال
inverse زي ما قلنا قبل شوية نيجي الآن نعملها مع
الأولى و نعملها مع التالية باجي بقول M2 في Y2
تطابق الواحد مدلة M2 مين M2 هيها 21Y2 مين هي
المجهول الآن يصبح 21 Y2 تطابق الواحد مضله مين أما
2 small هي هادي هيها هادي هي بيصير مضله خمسة الآن
نحلها لحسن حظنا هادي أصلًا لو شيلنا منها مضاعفات
الخمسة اللي هي عشرين بظل بس مين واحد فبتظل Y2
تطابق الواحد مضله خمسة يعني بس اشتغلت على هادي قلت
بما أن الواحد والعشرين تطابق الواحد اللي هو إذا صار
عندي الـ y .. ال 21 y2 تطابق ال y2 حطيت مكانها
يعني بمعنى آخر شلت مضاعفات ال 21 اللي هي عشرين ضلت
واحدة واحد صار y2 و هو اللي جاهز صار y2 تطابق
الواحد و دولة خمسة اللي ما استبعبش هذه خلينا اللي
بعدها الآن نعمل M3 Y3 تطابق الواحد يعني بعدد مين
التطابقات اللي موجودة الآن M3 اللي هي مين عبارة عن
أوجدناها اللي هي خمسة عشر يصير خمسة عشر Y3 المجهول
تطابق الواحد موضله مين موضله سبعة السبعة مين
السبعة اللي هي ال M3 اللي عندي طبعًا ليش أنت بتحل
هدولة .. هدولة في القانون .. هدولة حالهن .. هن
اللي بدنا نعوض من حالهن هنا بتطلع ليه اللي هو مين
اللي هي الحل العام حسب اللي هو مين الطريقة تبعت
Chinese remainder theorem إذا صار عندي الآن Y1 وY3
هذا آسف مش Y1 وY3 وطبعًا كل واحد مدله مين مدله سبعة
إذا صار هي عندي Y1 هنا و Y2 هنا و Y3 هنا دلت علي
العملية الأخيرة هي عملية التعويض بكون أوجدت الحل
النهائي X بتساوي A1 M1 Y1 A2 M2 Y2 زي A3 MY3 هي
قانوننا اللي هو قانون اللي هو بيجيب لحل ال system
كله بعد ما تأكدنا ال 3 وال5 وال7 اللي تيبل براين
بكون هذا هو حل ال system A1 مين هي؟ هي هالتنينام
واحد أو أوجدناها اللي هي خمسة وثلاثين Y واحد هم اللي
حللناها عشان خطر الاثنين فبيصير اثنين في خمسة و
ثلاثين في اثنين اثنين هي الاثنين اثنين لها ثلاثة
الآن مضروبة في مين في و ام اثنين اللي هي جديش واحد
و عشرين هاي واحد وعشرون في واي اثنين اللي هي
أوجدناها اللي هي واحد زاد ثلاثة هاي ثلاثة اللي
هي برضه جديش اثنين مضبوط هاي اثنين في مين في
خمسة عشر اللي هي ام ثلاثة في واي ثلاثة اللي هي
أوجدناها بتساوي واحد طلع عندي الرقم ثلاثة وثلاثين إذا
X بيثاور 233 لكن أنا بدخلي هذا العدد من أعداد
1 لعند 105 أو من 0 لعند 104 ماشي فبشيل منه كل
مضاعفات 105 مضاعفات الـ 105 مضاعفات الـ 210 مضاعفات
الـ 230 مضاعفات الـ 230 مضاعفات الـ 230 مضاعفات
الـ 230 مضاعفات الـ 230 لكن .. لكن .. لكن عندي اللي
هو عدد لانهائي من الحلول اللي هي اللي متطابقات هن
زي الـ 233 و زي لما نزيد 105 لها بيصير 338 و لو
طرحنا 105 و لو طرحنا 105 بيطلع عندك اللي هو كل
اللي بيطابق هنا الـ 23 مدلة 105 هي عبارة عن حلول
لهذا الـ System أو اختصارًا اختزالًا نختزل الحل في X
تو تطابق الـ 23 مدلة 105 و اللي بده يوجد الأرقام زي
ما بده بيوجدها بضيف 105ات و يطرح 105ات بكون we have
shown that 23 is the smallest positive integer
that is simultaneous solution اللي هو يعني هو 23
هو عبارة عن أصغر عدد بيجسم اللي هما ايش اللي هي
الثلاث و المتبقي اثنين و بيجسم الخمسة و المتبقي
ثلاثة و بيجسم السبعة و المتبقي جديش اثنين أو هو
عبارة عن الحل العام لهذا ال system of linear
equations طيب نيجي الآن إلى اللي هو طريقة ثانية لحل
اللي هي المعادلات التطابقات الهالية حاجة اسمها
الـ back substitution نشوف كيف بدنا نحل الآن بدنا نحل
اللي هو system of linear congruences باستخدام حاجة
اسمها ال back substitution الـ back substitution
اللي هي بتعتمد أنه بنحول ال linear congruences إلى
معادلات ومن ثم بنبدأ نعوض ونرجع و نرجع لما نصل
لحل النهائي نشوف كيف برضه اللي هو إن شاء الله
الطريقة سهلة لو تابعوا معايا هتلاقوا حالكم تعرفوا
تحلو إن شاء الله example use the method of back
substitution to find all integers x such that أوجد
كل الأعداد x التي تحقق x وطابق الواحد مدلة خمسة أو
x وطابق الاثنين مدلة خمسة وفي نفس الوقت x وطابق
الثلاثة مدلة سبعة يعني بدنا نحل العاملة هذه اللي هو
ال system of linear congruences شوفوا الأول نبدأ
في الأولى الآن x تطابق الواحد من دول الخمسة الغرض
إيجاد قيمة x يا جماعة since x تطابق الواحد من دول
الخمسة إذا حسب المفهوم اللي هو التطابق بتكون
الخمسة بتجسم ال x ناقص واحد ايش معناه الخمسة
بتجسم ال x ناقص واحد يعني ال x ناقص واحد بتساوي
خمسة في some integer mean T يعني x ناقص واحد بتساوي
خمسة في T اللي هو حيث T عدد صحيح ماشي الآن so بس
بتدنجل الواحد هنا بيصير x بتساوي خمسة زائد ايش زائد
T الآن صارت عندي خمسة بالساوية X بالساوية خمسة
زائد T بتعوض عن قيمة X هنا لأن ده وجود الحل
المشترك هذه حققت المعادلة الأولى أو التطابق الأولى
هذه حققت التطابق الأولى بتعوضها هنا عشان تحقق
التطابق الثانية طيب إذا عوضولي في هذه عن قيمة خمسة
T زائد واحد Substituting into X في التطابق اثنين
مدلة ستة هذه yields بنتجلي خمسة T زائد واحد مكان
ال X تطابق الاثنين مدلة ستة انجلي هذا على الجهة هذه
بيصير ليه خمسة T تطابق الواحد مدله ايش مدله ستة
لأنه اثنين ناقص واحد بيطلع واحد الآن زي ما عملنا
قبل بشوية بدي أشيل من هذه مضاعفات ال .. من مضاعفات
الستة -6-6-6
-6-6-6
-6-6-6-6-6-6
-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6-6
الآن ناقص واحد أنا ما بديش يامودب سالب بدي يامودب
الآن بضيف على الناقص واحد اللي هو ستة أو مضاعفات
الستة صح آه طبعًا انفجنا علي هذا الكلام أنه بيطلع
متطابق لما نضيف المضاعفات المقياس ستة وناقص واحد
بيطلع خمسة إذا T تطابق الخمسة modulo 6 إذا T
تبعتنا هادي الجنه بتحقق T بطابق الخمسة modulo 6
طيب هذه الآن بدي أكتبها على صورة معادلة زي ما عملت
في مين؟ في الـ X اللي فوق اللي أنصرت X اللي عندنا
حققت هذه وهي حققت هذه بس خلّيني أكمل T تطابق
الخمسة modulo ستة أيش معناته؟ يعني الستة بتجسم الـ
T ناقص خمسة يعني الـ T ناقص خمسة بالساوية ستة في
U مثلا أو T بتساوية ستة U زائد خمسة زي ما عملت فوق
بالظبط بدي أعمل في هذه بالطريقة اللي حكيت عنها فوق
بتجسم الـ 6 بـ T-5 إذا الـ T-5 بيساوي 6 في U نجلت
الخمسة هنا صارت T بيساوي 6 U زائد خمسة where U
أشماله is an integer الـ T اللي طلعت عندي هنا بدي
أرد اللي هي أعوضها في اللي هي الـ T اللي عندي اللي
هي بدي أعوض substituting
this back into X بتساوي خمسة T زائد واحد لإن عندي
اللي هي ال X عندي جدش قيمة طلعت اللي بالأحمر هذه
خمسة T زائد واحد بعد ما وجدنا T اللي هي اللي صارت
تتحقق هذه التطابق اللي هي حققت التطابق هذه صار عندى
اعوض عن T بقيمتها 6U زائد خمسة هان بيصير X بتساوي
شيل ال T وحط 6U زائد خمسة بتطلع عبارة عن خمسة في
هذا المقدار زائد واحد اضربه جوا بيصير ثلاثين U
زائد خمسة وعشرين واحد بيطلع زائد إيه؟ ستة وعشرين إذا
صارت عندى X بتساوي ثلاثين U زائد ستة وعشرين صارت
هذه حققت هذه و حققت هذه دلنا نشوف كيف تتحقق هذه و
نكون أوجدنا الحل المشترك الآن الخطوة الثالثة مكررة
يعني مشابه للسابق insert this into X طابق 3 مدل 7
بعد ما عوضناها نعوضها نعوض الآن في الأخيرة X طابق
3 مدل 7 شيل اللي هي ال X هذه و حط قيمته اللي
أوجدناها هذه فوق بصير 30U زي 26 تطابق من التلاتة
مدرس سبعة بدنا نحل هذا زي ما حلنا اللي قبل solving
this بيعطيني الان الـ 26 من جلها بيصير ناقص 26 و في
عندي 3 بيصير ناقص 23 صارت 30 U تطابق ناقص 23 و دول
7 الان هذه بدنا نحلها بدنا نحلها لإيجاد ال inverse
زي ما قلنا شيل المضاعفات اللي هي السبعة أجرب اشي
30 على 7 بتطلع 4 في 7 ب 28 و بزيد 2 خلاص عند ال 2
إذا شيلت 28 بظل 2 U لان ناقص تلاتة و عشرين و نضيف
مضاعفات السبعة لكي نضيف أقرب رقم لكي نضغر قيمة
الرقم
21 من مضاعفات السبعة و 21 من مضاعفات السبعة و 21
من مضاعفات السبعة و 21 من مضاعفات السبعة و 21 من
مضاعفات السبعة و 21 من مضاعفات السبعة و 21 من
مضاعفات السبعة و 21 من مضاعفات السبعة و 21 من مض
التلاتين يو حطينا اتنين يو اللي أنا عملت هيك عشان
أنا عارف إنه أنا بتخليها ده اللي هو طلع عند اتنين
بتخليها ده برضه بيطلع فيه زوجي عشان اللي هو اجسم
الجهتين على اتنين و يظل ال يو لحالها بنفع اه لان
أهم المشتركة الأعلى بين السبعة و اتنين واحد بنجسم
على اتنين بيطلع يو تطابق الناقص واحد مضول سبعة
الناقص واحد ضيفله سبعة بيصير اللي هو ستة بيصير due
تطابق الستة modulo من modulo سبعة احنا اضافة اللي
هو اضافة اللي هي مضاعفات او طرح مضاعفات العدد اللي
هو المقياس لأي من الطرفين طبعا منضيف سبعة you هنا
أو أربع طاش you ومش سبعة لحالها واما هنا منضيف
السبعة وكذا عسى انه يظل المتطابقات بتنطلع عند U
ترابق الستة مضلوا سبعة بنعمل هذه زي ما عملنا اللي
فوق اللي هو سبعة بتجسم ال U نقص ستة معناته اللي هو
ال U نقص ستة بساوية سبعة V يعني ال U بساوية سبعة V
زائد ستة where V is an integer الآن بدأ أعوض عن ال
U في من؟ في ال X هنابصير عند ال X بتساوي شيل ال U
وحط قيمتها اللي هي 7V زائد 6 بصير ال X بتساوي اللي
هي بدل 30U 30 في 7V زائد 6 زائد 26 وضربها بتطلع
210U زائد 30 في 6 ال 180 و 26 بتطلع 206 يعني
اتصلعت عندي الآن X بتساوي 210U زائد 206 وهذه طبعا
نتيجة الحل في الأولى وفي التانية وفي التالتة يعني
ال X اللي عند هذه حققت هذه وحققت هذه وحققت هذه
معناته ال X اللي طلعت هنا هي عبارة عن حل
المتطابقات كلها اللي هي التلاتة في نفس الوقت يعني
صارت عند X بتساوي 210 U زي 206 هي عبارة عن الحلول
حيث U is an integer الان هادى بنقدر نكتبها على صورة
ايش تطابقة اللى هى ايش أصل التطابقة X تطابق الـ
206 modulo 210 ايش عرفك هاي X ناقص 206 اللى هو 210
بتجسمها 210 بتجسم X ناقص 26 يعني X ناقص 26 بساوية
210 في some number سمينا U هو فعلا صارت عند X
بساوي 210 U زائد 206 إذا هذه x بتساوي 210 u زائد
206 هي نفس التعبير اللي بنقوله x تطابق ال 206
modulo 210 ليش لإن زي ما قلت X تطابق الـ 206 مده
210 معناته 210 تقسم ال X ناقص 206 وزي ما عملنا
بسير X ناقص 206 تساوي 210 في U التي تساوي 210 في U
زائد 206 إذا هذه هي هذا التعبير وهذا معناته أنه
اللي هي الأرقام مائتين وستة وبعدين ضيف كمان مائتين
وعشرة بيصير أربعمائة وست عشر وضيف كمان مائتين وعشرة
بيصير كده بيصير كده كلهين حلول مشتركة لهذه التطابق
وهذا حل اللي كلهين ولو لاحظت حتة تجي المائتين
وعشرة هي عبارة عن ستة في خمسة في سبعة ستة في خمسة
في تلاتين و تلاتة في سبعة في متين و عشرة إذا صار
عنده X وطابق متين و ستة مدله متين و عشرة و هيك
بيكون احنا حللنا اللي هي ال system of linear
equations بواسطة حاجة اسم ال back substitution و
هذا هو ال homework اللي مطلوب منكم حل السؤال الأول
و التاني و التالت بسلامونيه و إلى لقاء آخر السلام
عليكم و رحمة الله وبركاته