بسم الله الرحمن الرحيم الحمد لله رب العالمين
والصلاة والسلام على سيد المرسلين سيدنا محمد على
آله وصحبه أجمعين هذه هي المحاضرة الرابعة في مساق
قياضيات منفصلة لطلاب وطالبات الجامعة الإسلامية
كلية ال IT قسم الحوسبة المتنقلةالمحاضرة اليوم هي
المحاضرة الأولى أيضا في chapter 4 وهو المعنوان ب
number theory and cryptography اللي هي بنقصد فيها
نظرية الأعداد والترميز والترميز هو عبارة عن تطبيق
على نظرية الأعداد ال section الأول اللي هنتحدث عنه
اليوم اللي هو divisibility and modular arithmetic
اللي هو شو معناته القسمة أو قابلية القسمة وحنشوف
دالتين واحدة دالة اسمها المد وواحدة دالة اسمها
dive ونشوف إيش اللي بنقصد فيهمالان نحكي اول شيء عن
ال division الان ال division اللي هي القسمة نشوف
شو معناته ال a divides b ايش معناته انه عدد يقسم
عدد اخر اسمه b طبعا حديثنا كله بصب بس اللي هو في
ال integers يعني احنا كل الاعداد اللي بنتناولها
اليوم هي عبارة عن اعداد صحيحةالان بنقول if a and b
are integers يعني لو كان عندي a و b عبارة عن أعداد
صحيحة with a لا تساوي سفر مدام قال with a لا تساوي
سفر شكلنا هنقسم على a لأن القسم على a مرفوض فعشان
هيك مفترضين ان a لا تساوي سفرالان بيقول then a
divides b يعني بيقول ان a تقسم b شو معنى a تقسم b
اللي هو if there exists an integer c such that ال
b بتساوي ال a في c في هذه الحالة بيقول a divides b
يعني اكترنا نكتب بي على صورة a في integer اخر او
في عدد صحيح اخر زي ما نقول ستة بتساوي اتنين فتلاتة
فبتكون التنين تقسم من الستة يعني بمعنى اخر a
divides b اللي هو a is a factor of b يعني a عامل
من عوامل bأو divisor of B أو قاسم من قواسم الـ B
إذا لما نقول A divides B بنقصد أنه A عامل من عوامل
B وبنقصد A قاسم من قواسم ال B أو بنقصد B عبارة عن
من مضاعفات الـ A يعني B is multiple of A كل
التعبير الثلاثة دول A قاسم من قاسم الـ B أو A عامل
من عوامل الـ B أو B من مضاعفات الـ A كلها المقصود
فيها أن A divides Bما هي الـ notation تبعتها؟ نقول
a divides b وهي a وهي عصرها بينهم b شكل العصرها هي
شبه عمودية يعني a divides b denotes that a divides
b أو a تقسم بي الان قلنا ان a تقسم بي معناته ان ال
a عامل من عامل بي يعني لو جينا جسمنا ال b على ال a
هتطلع integerيعني الآن لما نقول a تقسم b بنعني انه
على طول العدد b على العدد a فده مائل يعني بيقولك
بي على العدد a هيطلع اشمال و انتجر زي مهنا هاي مش
هاد معناه a تقسم b يعني الان b على a هتطلع ال c
يعني انتجر إذا من الآن و طالع مجرد نقول a تقسم b
معناته ال b على ال a هو عبارة عن عدد صحيحطب لو
بدنا نقول a does not divide b نرمز بالرمزية ده a
وهي الشحطة الأولى وهي فجهها شحطة تانية يعني a does
not divide b يعني a لا تقسم ال b ناخد أمثل عددية
الان المثال الأول determine whether التلاتة بتقسم
السابعة and whether التلاتة بتقسم أطنعاشلأ احنا
على طول الحد ما نشوف على طول التلاتة متقسمش السبعة
ليش لأن السبعة على التلاتة مش عدد صحيح اذا التلاتة
does not divide بيه اذا اكيد ال solution هنقوله
التلاتة لا تقسم السبعة because اللي هو السبعة على
التلاتة ليست عدد صحيحلأن تلاتة بتقسم 12 كلكم قال
هل جيت 12 ع تلاتة أربعة يعني التلاتة لازم تقسم من
12 إذا أكيد تلاتة بتقسم 12 لأن 12 ع تلاتة هي عبارة
عن إيش طلعت الأربعة أو بمعنى أخر 12 بتساوي 3 في 4
زي ما عملنا في ال A ال B بتساوي A في C إذا التلاتة
تقسم من 12 إذا الكلام سهل طيب نيجي لخواص ال
divisibility أو خواص قابلية ال A أو خواص القسمة
نشوفاللي قال لو كان عند A وB وC عبارة عن integers
أعداد صحيحة والـ A لا تساوي سفر لأن شكل اللي هنقسم
على الـ A عشان يجي الـ A لا تساوي السفر الآن بقول
لي لو A بتجسم الـ Bوالـ a بتجسم ال c أكيد ال a
هتجسم ال b زائد ال c كلام منطقي خد مثلا اتنين
بتجسم الستة و اتنين بتجسم العشرة اذا اتنين بتجسم
الستة زاد العشرة اللي هي الست عشر اكيد اتنين بتجسم
الست عشر اذا دائما ال a بتجسم ال b و ال a بتجسم ال
c هذولة بخزن المعلومة بتعطينا ان ال a بتجسم ال b
زاد ال cهنروح لبعد من هيك بعد شوية الان a بتجسم ال
b أكيد ال a هتجسم ال b في خمسة و ال b في ستة و ال
b في سبعة و ال b في تمانية يعني أكيد ال a بتجسم ال
b في c لكل انتجار cو100 مثال نستطيع أن نقولها يعني
اتنين بتقسم الستة اكيد اتنين بتقسم الستة في تلاتة
اللي هي 18 اتنين بتقسم الستة في خمسة في تلاتين
اتنين بتقسم الستة في مليون اذا اتنين هتقسم ال B في
C اللي هو في حال اتنين بتقسم ال Bالان الخاصية هذه
التلاتة اللى بنسميها خاصية التحدي ال A بتجسم ال B
و ال B بتجسم ال C مع بعض هدولة لازم يعطلنا ال A
بتجسم ال C هذا الكلام سهل برضه لإن ال A بتجسم ال
.. خلنا نقول ال 2 بتجسم ال 6 و ال 6 بتجسم ال 24
إذا أكيد ال 2 بتجسم ال 24التلاتة بتجسم الستة
والستة بتجسم التمنتاش اذا التلاتة بتجسم من
التمنتاش اذا خاصية التعد متحققة ايضا لان نتيجة
للنظرية اللي فوق اللي هو طبعا هذه كان البرهان
المطلوب لكن احنا لسبب الظروف الآن اعطيناكم بيها
بدون برهان وهنا حكينا امثلة عددية عليها المهم نفهم
ايش اللي هو الخواصة دي نيجي لل Corollaryأو النتيجة
للtheorem اللي عندنا بقول لو كان a و b و c عبارة
عن أعداد صحيحة و ال a لا يساوي c يعني ال f a and b
and c are integers و ال a لا تساوي سفر such that
ال a divides ال b و ال a divides ال c يعني ال a
بتقسم ال b و ال a بتقسم ال cإذا الـ A هتقسم مش بس
الـ B زائد الـ C لأ هتقسم أي linear combination
بينهم يعني هندمج هذه و هذه مع بعض و نحصل ان الـ A
بتقسم الـ B M زائد الـ C N لكل M و N ايش ال linear
combination هذا بنسميه ال M B زائد ال N C عبارة عن
linear combination بين الـ B و مين و الـ C إذا
بنقول ما ياليا يا جماعةإنه لو الـ A بتقسم الـ B و
الـ A بتقسم الـ C حيكون عند الـ A بتقسم أي Linear
combination M B زائد مين M C where M and N
integers يعني ناخد مثال عند الـ 3 بتقسم 12 و الـ 3
بتقسم الـ 15 أكيد الـ 3 بتقسم 12 في M زائد 15 في N
لكل ال integers M و Nانت جرب حط اي integers بيجي
على بالك ام و ان هتلاقي التلاتة بتجسم 12 ام زاد 15
ام ناخد مثلًا
التلاتة بتجسم التمانية وسبعين اكيد لان التمانية
وسبعة وخمسة عشر وجرب اعداد زي ما بدك هتلاقي مادامة
التلاتة بتجسم اتناش والتلاتة بتجسم الخمسة عشر
التلاتة هتجسم اي linear combination بين اتناش
وخمسة عشر ايش linear combination يعني اتناش فئام
زي خمسة عشر فئام لكل integers oneطيب الان نجي ل
division algorithm او اللي بنسميها خوارزمية القسمة
خوارزمية القسمة مش غريبة علينا بنعرفها بنعرفها من
و احنا صغار الان لو جلك اجسملي العشر على الخمسة
هتقولي العشر على الخمسة بيساو اتنين بقولك في متبقى
جسم هتقولي لايعني و كأنه العشر لما جسمت على خمسة
طلعت ناتج قسم اتنين ولا يودد متبقى قسمها يعني
متبقى القسمها سفر لكن لو قلتلك ديبل 11 على خمس على
خمسة هتقول 11 على خمسة بيساوي اتنين و بيزيد واحد
هذا الواحد هو متبقى قسمهاوالاتنين هي ناتج القسمة
هذا اللي بتقوله بالظبط ال division algorithm when
an integer is divided by a positive integer there
is a quotient and remainder يعني في ذاتج قسمة وفي
متبقى قسمة لما نجسم اللي هوعدد على positive number
دي اللي هو مقسوم عليه this is traditionally called
the division algorithm أو خوارزمية القسمة وخلّينا
نشوف إيش خوارزمية القسمة أو نظرية الخوارزمية
القسمةبتقول بقى يعني صلوا على النبي عليه الصلاة
والسلام if a is an integer and d is a positive
integer يعني a أي انتجر سالم موجة بالإبداكية حتى
لو كان سفر مش فارجة هقلناه و ال d positive integer
أكبر من سفر لما نجسم ال a على ال d هيطلع ناتج قسمة
بدي أسميه Q والمتبقى اللي هو بدي أسميه Rبعد ذلك
يوجد
ناتج قسم واحد Q ومتبقى واحد R بحيث ان R أكبر وسوء
سفر وأصغر من D دائما عندما تقسم ال A على ال Dيعني
11 على خمسة و تقول 11 على خمسة بطلع اتنين و بضال
واحد الواحد هذا سبته ليش سبته لأنه أصلا هو أكبر أو
يساوي سفر و أصغر من المقسوم عليه اللي هي الخمسة
فدائما ال remainder بكون أكبر أو يساوي سفر و أصغر
من المقسوم عليه ال Dإذاً لما نقعد يقسم ال A على ال
D بطلع لناتج قسمة اسمه Q وفيه remainder اسمه HR
عشان هيك بنقول A بتساوي D في Q زايد R زي ما قولنا
ل 11 بساوي ال 5 في 2 ب10 زايد ال 1 ال 1 هو ال
remainder وال 2 هو ناتج القسمة هو الخمسة اللي
قسمنا عليها إذاً الآنالـ A بيتساوى DQ زي الـ R حيث
الـ A هو المقسوم والـ D المقسوم عليه والـ Q ناتج
القسمة والـ R هو المتبقي D is called the divisor
الان المقصوم عليه A is called the dividend اللي هو
المقصوم و Q is called the quotient ناتج القسمة و R
is called the remainder من هذا الحديث الان بدنا
نستقي مع بعض دالتينانعرفن كما يالي definitions of
functions واحدة اسمها dive واحدة اسمها mud بدنا
نصطلح مع بعض شو معناته ان احنا بنقول ايه dive دي
اللي بنقصد فيها انه لما جينا قسمنا ال a على ال d
طلع عندى ناتج قسمة ناتج القسمة هذا اللى بتسميه a
ضايف d بقصد فيه ناتج قسمة a على d هذا ناتج القسمة
طب اهم ال d ايش بقصد فيه هو المتبقي من ناتج قسمة a
على d اذا a ضايف d مقصود فيه لما اقسم a على d
بتطلع اللى هى ناتج القسمةلما أقسم الـ a على d
بيطلع عندي remainder فبقصد ال a مو ال d هو عبارة
عن مين المتبقي او ال remainder اتفجن علينا دول
الدالتين يللا خلينا نشوف أمثل عددية طيب احنا نشوف
أمثل عددية المثل العدد لل division algorithm هو ما
يعني what are the quotient and remainder when 101
is divided by 111بنشوف ايش اللي هو الناتج القسمة
ومتبقى القسمة لما نجسم 101 على 11 اكيد كلكم كان
101 على 11 في 99 و بظهر بينهم قداش بزيادة 2 فاكيد
اللي هو هيكون عند 101 بساوة 11اللي هو ضرب تسعة
زائد اتنين تسعة هذا هو ناتج القسمة والتنين هو
متبقي القسمة عشان هيك بنكتبهم بالطريقة اللي اتفجنا
عليها قبل بشوية اللي هو بيصير عندي اللي هو عندي
المتبقيالقسمة اللي هو 2 فبنكتب 101 مد 11 بما أن في
متبقى القسمة لما نقسم 101 ل11 بيطلع 2 وبنكتب 101
ضايف 11 معناته الدالة هذه بتعني أنه لما نقسم 101
ل11 بيكون ناتج القسمة 100 اللي هو 9 زي ما شفنا
اللي عاملينه احنا هنا في ال division
السؤال الثاني هو what are the quotient and
remainder نقص 11 is divided by 3 نقص 11 نقص 11 نقص
11 نقص 11 نقص
11 نقص 11 نقص 11 نقص 11 نقص 11 نقص 11 نقص 11 نقص
11 نقص 11 نقص 11 نقص 11 نقص 11 نقص 11في هذه الحالة
بيصير نقص 11 بيساوي تلاتة فى ناقص أربعة زايد واحد
لما نقسم الناقص ماحدش يقول ناقص تلاتة لأنه بيصير
تلاتة فى ناقص تلاتة بيساوي ناقص تسعة ناقص تسعة
بيصير ناقص احداش بيساوي ناقص تسعة ناقص اتنين و ال
remainder لازم التفاجن يكون ايه شماله اكبر من سفر
و اصغر من تلاتة لأن احنا لما نقدر نقسم اي عدد على
ال remainder بيطلع انه عدد صحيحلو زاد عن اللي هو
.. لو ال remainder طلع بالسالب لأ احنا مابنقش
بنوحد الكلام كله مع بعض كلنا نجسم زي بعض و طلعنا
remainder زي بعض و ناتج قسمتنا زي بعض عشان هيك
بنطلب ال remainder يكون بين السفر و بين التلتة زي
ما كنا نعمل زمان في قسمة الأعداد الصحيحة على بعض
الان هذا بيصير نقص 11 بيساوي تلتة في نقص 4 زائد من
1الان هذا اللي هو الواحد هو عبارة عن ال remainder
عشان هيك بنقول الواحد اللي هو بساوي ناقص أحداش مدت
تلاتة نقولنا دالة المد هذه تعني قسمة ناقص أحداش ع
تلاتة بطلع متبقى القسمة بساوى واحد يعني هذه تدل
على متبقى القسمةالان اللى هو ناقص 11 ضايف 3 تعني
اللى هو ناتج قسمة ناقص 11 على 3 اللى هو ايش طلع
عندى ناقص 4 و هيك بنوجد اللى هو ناتج القسمة و
بنوجد مين اللى هو متبقي القسمة الان ان دخلنا على
حاجة اسمها ال congrance relation او اللى هي علاقة
التطابقالان ايش اللى بنقصد فيها علاقة التطابق؟
خلينا نشوف ايش اللى هو تعريف علاقة التطابق دي، ايش
معناه الـcongruence؟ لو كان عند A وB عبارة عن
أعداد صحيحة integers and M is a positive integer
والـ M إيش ماله؟ عدد صحيح موجببنقول أن a is
congruent to b modulo m يعني a تطابق b modulo m
يعني a تطابق b اللي هو بالنسبة للمقياس m إذا حققت
مالي ال m تقسم ال b minus a أو تقسم ال a minus b
في هذه الحالة بنقول a تطابق ال b modulo m وبنرمز
لها بالرمز اللي عندي ais congruent to B modulo M
نعني بها أن M تقسم اللي هو ال A ناقص B تقسم ال A
ناقص B هذا معناته أن A تطابق ال B modulo M الان
هذه ع بعضها بنسميها is a congruence أو بنسميها
تطابقة و ال M هو ال modulus أو هو مقياس التطابق
بنسميهالان اللى اللى اللى اللى اللى اللى اللى اللى
اللى اللى اللى اللى اللى اللى اللى اللى اللى اللى
اللى اللى اللىيكون المتطابقتين إذا كان ال a و ال b
اللي هى نفس ال remainder لو قسمناها على ال m يعني
لو قسمنا ال b على ال m هنلاقي اللي هو ناتج القسمة
b على m R1 و ناتج قسمة a على m R2 في حالة ما يكون
المتطابقتين لازم ال R1 ايش يساوي R2 عشان هيك two
integers are congruent modulo mif and only if they
have the same remainder when divided by main by m
لو كانت ال a لاتطابق ال b بنرمز ال a لاتطابق ال b
modulo m وهذا ماذا بتحدث؟ بتحدث لما نلاقي ال m لا
تقسم ال a minus b أو لما نلاقي ال remainder لل b
لما نقسمها على m يختلف عن ال remainder لل a لما
نقسمها على mainعلى أمن طيب خلينا نشوف احنا مثال او
امثلة عددية نشوف المثال العددي بيقول determine
whether ال 17 is congruent to 5 ولا لأو بعدين
modulo 6 طبعا and whether ال 24 and ال 14 are
congruent modulo 6 الآن بده يشوف السبعتاش والخمسة
هل المتطابقتين modulo 6 قلنا أحد أمرين ابني جي
بنقول السبعتاش ناقص خمسة بطلع اتناش الستة بتقسم
اتناش اذا السبعتاش بتقسم الخمسة modulo 6الان طريقة
اخرى اللى هى انه بنجيب نجسم السبعتاش على الستة
المتبقى جديش خمسة هو نفس المتبقى لما الخمسة نجسمها
على الستة لإن المتبقى بيطلع خمسة ونتج القسم صفر
طبيعى اذا الان السبعتاش تطابق خمسة مدله ستةلأن أحد
سببين يا إما ستة بتقسم حصل طرحين يا إما هذا لما
نقسم على هذا و هذا لما نقسم على هذا بيعطي نفس
نتيجة نفس اللي هو ال remainder طيب الآن يجي نحكم
على مين الاربع عشرين و الاربعة عشر هال congrant
بدوله ستة ولا لأ أكيد كلكم قال اربعة عشرين نقص
اربعة عشر بتساوي عشرة الستة بتقسمش العشرةإذا
الأربعة عشرين لاتطابق الاربعة عشر مدلو ستة أو
مقياس ستة الان لو أحد قال لا ما هو أنا بتطلع لها
نظرة أخرى الأربعة عشرين لو جسمناها على الستة بتطلع
ال remainder صفر لأنه تقبل قسم عليها لكن الأربعة
عشر لما نجسمها على الستة بتطلع عندي remainder
اتنين إذا ال remainder هنا و ال remainder هنا
مختلفات إذا they are notCongruent أحد الأمرين اللي
بتشتغلوه هو صحيح ندى الأن نشوف أخدنا شغلتين الأن
أخدنا اللى هو ايه تطابق الـ P modulo Mاللي هو و
الـ a mod m بتساوي b بدنا نشوف العلاقة the
relation between او the relationship between mod m
and mod m notations يعني هذه اللي بالغامج هذه اللي
بنقصد فيها دالة a mod m اللي هي نصدنا فيها دالة
لما نعرفنا هي و ال dive الآن a تطابق b mod m اللي
هي علاقة بين اللي هي integers a و bقلنا ايش هذا
بتعني؟ بتعني ان a تطابق b modulo m اللي هي معناتها
ان m بتجسم ال a minus b او بمعنى اخر قلنا معناتها
ان المتبقى القسمة من a على m هو نفس متبقى القسمة
من b على mبينما هذه يا جماعة اللى بتعني a مد ام
انه لما نجسم ال a على m متبقى القسمة بساوة b ماشي
اذا لما نقول a مد ام بساوة b يعني متبقى قسمة a على
m بساوة b اما هنا a تطابق b مد ام انه متبقى القسمة
a على m هو نفسه متبقى القسمة b لما نقسمه على mالان
هذا الكلام حكيته انا it وطبق me the relation on
the six integers هذه علاقة على الست الفنتجرز بينما
هذه عبارة عن دالة اتفاقنا عليها اللي هي the
notation denotes the function او a function
العلاقة بين التنتين الآن هنشوف that the
relationship between these two is made clear in
this theorem هتكون واضحة من خلال هذه النظرية اللي
أمامنا شوفوا يا جماعة صلى الله عليه الصلاة والسلام
لو كان عندي a و b integers و m positive integers
احنا ال a تطابق b مدله m هي تكافئ تماما يعني if
and only if هذه على بعضها هذه تكافئ تماما ان نقول
a مد m بساوي b مد mلأن بي مض ام ايش بتعني ان متبقى
قسمة ال بي على ام يساوي متبقى قسمة ال ا على ام لان
هذه بتعني متبقى قسمة ال ا على ام وهذه بتعني متبقى
قسمة ال بي على ام هذه معناته مساواة يعني متبقى
قسمة هذه على هذه بساوي متبقى قسمة هذه على هذه هو
بالظبط هذااللي هو A تطابق B mod M يعني متطابق قسمة
A على M اللي هو نفسه متطابق قسمة B على M وكأنه هذا
التعبير هو هذا التعبير ولكن بصورة أخرى ماشي الحال؟
طيب الآن إذا هذا بكافة اللي هو هذه الكلمتين بخزن
هذولة اللي عندنا أو كفاتة خلينا نشوف مثالالان الـ
31 و 351 متطابقات ليش لأن 351 ناقص 31 تطلع 320
العشرة بتجسمها إذا فعلا متطابقتين بالنسبة للمقياس
عشرة الان طيب الان اني جي نشوف اللي هو ال .. ال ..
ال .. نظرة أخرى لهذه ان هذا و هدولة اللي هي نفس ال
remainder لما نجسمها للعشرة هذا هو الان31 لما
تجسمها على عشرة بيطلع متبقي واحد 351 لما تجسمها
على عشرة بيطلع متبقي واحد إذا هذا بيساوي هذا يعني
اللي هي التطابقات و بالمناسبة التطابقات اللي هو
موضوع ال concurrences هذه هي أصلا لأودادتنا أو
خلينا نقول اللي بتعلمنا كيف أو قدام هنعرف أنظمة
العد من خلالهانظام العد الثاني نظام العد الثلاثي
الرباعي الخماسي العشاري اللي بنتعامل فيه أو الستعش
أو التمانية اللي بدنا يه اللي هو النظام العد اللي
هو اللي بتبع من المقياس يعني مقياس عشرة بنصير مجول
عن نظام العد العشاري مقياس اتنين بنصير مجول عن
نظام العد الاتنين وهكذا وان شاء الله هنجيه قدام
الان بيكون هيك احنا خلصنا اللي هو اللي بدناياه في
هذا ال section وعندي ال homework التالي بدياه
تجيبوليه ببعتلكم عن واتس بظبط إيش اللي بدياه الآن
السؤال الأول بيقوللي 31 تطابق ماذا مدل سبعة هل
بالطابق الخامسة، بالطابق ال 211؟ يمكن الطابق
واحدة، تمتين، تلاتة، كل واحدة من هناك تشوف مين
بالطابق ال 31 مدل السبعة وتحط اللي تحتها خط
وتقوللي ليش بالطابقهاوالثاني لماذا بالطبق عشر؟
find اللي هو عشرة ضايف تلاتة عشرة ضايف تلاتة قدش
قيمته 101 ضايف تلاتة وعشرين برضه نفس الاشي و بعدين
اجدل عشرة موت تلاتة الاخر هدولة إيجاد زي ما شرحنا
قبل شوية الان question الثالث which of the
following divides the positive integer a؟ يعني
عندي في positive integer aمين من هدولة divides
which of the following divides the positive
integer ايه او خلينا نقول which of the following
او a divides which of the followingA divides
which of the followingيعني مش هنا اللي بدني اجيز
منه هل ال ا بتجسم هدول ولا لأ ا بتجسم مين منهم بدك
تحددها و هيك بكون خلصنا ال section الأول و إلى
لقاء آخر والسلام عليكم ورحمة الله وبركاته