سننتناول في هذا الدرس المواضيع التالية :

• خوارزمية القسمة ( Division Algorithm )

• خوارزمية إقليدس ( Euclidean Algorithm )

• القاسم المشترك الأكبر ( Greatest Common Factor )

• المضاعف المشترك الأصغر ( Least Common Multiple )

خوارزمية القسمة ( Division Algorithm )

نظرية 2.1 - خوارزمية القسمة (Division Algorithm)

ليكن أ و ب عددين صحيحين ( أ > صفر ) ، يمكننا أيجاد عددين صحيحين

وحيدين ( فريدين - unique ) ك و ر بحيث :

ب = أ ك + ر ، 0 ≤ ر < أ

إذا كانت ب لا تقسم على أ : 0 < ر < أ

البرهان

خذ المتتالية الحسابية(ممتدة من الجهتين) :

.....، ب - 3أ ، ب - 2أ ، ب - أ ، ب ، ب + أ ، ب + 2أ ، ب + 3أ ، .......

إثبات وجود ر

قم باختيار الحد الذي هو أقل عدد موجب في المتتالية و لنطلق عليه ر

إذن ر موجودة و هي موجبة و بالتالي تحقق الشرط الوارد في

النظرية ( 0 < ر < أ )

إثبات وجود ك

بما أن ر في المتتالية فإنها تأخذ الشكل : ب - ك أ و عليه ك موجودة و

معرّفة بالنسبة لـ ر

إثبات فرادة (uniqueness ) ك و ر

لنثبت أن ك و ر وحيدين ، نفترض وجود عددين صحيحين آخرين ك1 و ر1

يحققان نفس الشروط : 0 < ر1 < أ

نستطيع الجزم بأن ر1 = ر لأنه إذا لم يكونا متساويان ، يمكن أن نفرض

أن ر < ر1 بحيث 0 < ر1 - ر < أ

ب= أ ك + ر ، ر = ب - أ ك
ب = أ ك1 + ر 1 ، ر1 = ب - أ ك1

ر1 - ر = أ ( ك1 - ك)
و هذا يعني أن ر1 - ر تقسم على أ : ر1 - ر | أ

و لكن أ > ر1 - ر و هذا يتعارض مع النظرية 1.1 - 5

من الدرس الأول (تذكير إذا كان العددين أ و ب صحيحين موجبين و كان ب | أ ،

يكون أ ≤ ب ، بمعنى آخر ب هو الأكبر بين قواسمه )

و عليه ر1 = ر و كذلك ك1 = ك

ملحوظة

قلنا في النظرية أن أ > 0 و هذه فرضية غير ضرورية و يمكن ان تكون النظرية

كالتالي:

ليكن أ و ب عددين صحيحين ( أ ≠ صفر ) ، يمكننا أيجاد عددين صحيحين

وحيدين ( فريدين - unique ) ك و ر بحيث :

أ = ب ك + ر ، 0 ≤ ر < أ

أمثلة

أ = 5 ، ب = 17

17 = 5 × 3 + 2

أ = 428 ، ب = 963

963 = 428 × 2 + 107

كيفية الحصول على تلك النتيجة بواسطة الآلة الحاسبة

نقسم 963 على 428 فنحصل على 2.25 ، من هنا ك = 2

للحصول على ر : 428 × 0.25 = 107

ولكن ليست الحالة بسيطة دائما كذلك

أ = 428 ، ب = 964

بواسطة الآلة الحاسبة : 946 ÷ 428 = ..... 2.2523364

تظل ك = 2 ، بالنسبة لـ ر

428 × 0.2523364 = 107.99997 , أي أن ر = 108

آلة حاسبة أخرى قد تعطي عددا مختلفا من المنازل بعد الفاصلة و لكن

الطريقة واحدة.

تعريف 2.1 - القاسم المشترك الأكبر ( GCD - Greatest Common Divisor )
يكون العدد الصحيح د ≠ صفر قاسما العدد أ إذا كان أ | د

مثال : 6 قاسم من قواسم العدد 12 لأن 12 | 6

مجموعة القواسم للعدد أ هي المجموعة التي تحتوي على جميع قواسم العدد

أ ، بمعنى آخر جميع الاعداد الصحيحة د ( الغير مساوية للصفر) و التي تحقق

أ | د . نرمز لهذه المجموعة بالرمز ق _أ ( D_a )

مثال : ق₈ = { ± 1 ، ± 2 ، ± 4 ، ± 8 }

{± 1 , ± 2 , ± 3 , ± 4 , ± 6 , ± 12 } = D₁₂

يكون العدد الصحيح أ قاسما مشتركا ( Common Divisor ) لـ ب و جـ

إذا كان ب | أ و جـ | أ

مثال : 3 قاسم مشترك ( Common Divisor ) لـ 12 و 21 لأن

12 | 3 ، 21 | 3

بما أنه هناك عدد محدد من القواسم لأي عدد صحيح ≠ صفر ، هناك عدد محدد

من القواسم المشتركة لـ ب و جـ ما عدا الحالة التي يكون فيها

ب = جـ = صفر

إذا كان أحد ب أو جـ على الأقل غير مساو للصفر ، الأكبر بين قواسمهما

المشتركة نطلق عليه القاسم المشترك الأكبر ( GCD - Greatest Common Divisor ) لـ ب و جـ و نرمز له بالشكل التالي :

( ب ، جـ )

بالمثل ، القاسم المشترك الأكبر للأعداد أ ، ب ، جـ ، ......، ي

نرمز له : ( أ ، ب ، جـ ، .......، ي )

نتيجة

القاسم المشترك الأكبر ( GCD - Greatest Common Divisor ) معرّف لـ ب و جـ ما عدا الحالة ب = جـ = صفر

لاحظ أن ( ب ، جـ ) ≥ 1

خصائص

1) ب | (ب ، جـ ) و جـ | (ب ، جـ)

2) إذا كان ب | د و جـ | د فإن (ب ،جـ ) | د

3) ( ب ، جـ ) = ( جـ ، ب )

4) ( - ب ، جـ ) = ( ب ، جـ )

5) ( صفر ، ب ) = ب

6) إذا كان ب | جـ فإن ( ب ، جـ ) = جـ

مثال : 12 | 3 ، ( 12 ، 3 ) = 3

7) ( ب ، جـ ) = ( ب - جـ ، جـ )

8) (ب ، جـ) = ( ب + ك جـ ، جـ ) ، ك عدد صحيح

مثال ( 6 ، 18 ) = 6 = ( 6 + 2 × 18 ، 18 ) = ( 42 ، 18 ) = 6 ( ك = 2 )

9) إذا كانت ب = أ ك + ر فإن (ب ، أ) = (أ ، ر )

10) ( ب ، جـ ) = ( ب ، ب + جـ )

أمثلة و براهين

1) برهن الخاصية رقم 8 أعلاه : (ب ، جـ) = ( ب + ك جـ ، جـ )

إذا أثبتنا أن (ب ، جـ) |( ب + ك جـ ، جـ ) و ( ب + ك جـ ، جـ ) | (ب ، جـ)

يكونان متساويان.

باستخدام التعريف :جـ |(ب + ك جـ ، جـ ) [ منها ك جـ | (ب + ك جـ ، جـ ) ]

و ب + ك جـ |(ب + ك جـ ، جـ )

إذن ب + ك جـ - ك جـ | (ب + ك جـ ، جـ )

أي ب | (ب + ك جـ ، جـ )

و منها (ب ، جـ) |( ب + ك جـ ، جـ )

بطريقة مشابهة ( ب + ك جـ ، جـ ) | (ب ، جـ)

و عليه (ب ، جـ) = ( ب + ك جـ ، جـ )

2) أثبت أن (ن ، ن + 1 ) = 1

ليكن د = ( ن ، ن + 1 )

ن | د ، ن + 1 | د و منها ن + 1 - ن | د

أي أن 1 | د و منها د = ± 1 أي أن ( ن ، ن + 1 ) = 1

 

 

نظرية 2.2

إذا كان د = ( ب ، جـ ) فإنه يوجد أعداد صحيحة س و ص بحيث

د = ب س + جـ ص

البرهان : سيوضع عند الطلب أو بعد حل التمارين

مثال : د = ( 3 ، 7 ) = 1

1 = 3 × 19 + 7 × - 8 ( 57 - 56 = 1 )

تحذير

العكس غير صحيح : إذا كان د = ب س + جـ ص فذلك لا يعني أن د هو

القاسم المشترك الأكبر ( ب ، جـ )

مثال : 2 = 3 × - 1 + 5 × 1

و لكن ( 3 ، 5 ) = 1 و ليس 2

نتيجة

القاسم المشترك الاكبر هو أصغر قيمة موجبة لـ ب س + جـ ص ، س و ص

أعداد صحيحة

نظرية 2.3

( م ب ، م جـ ) = م ( ب ، جـ )

البرهان

باستخدام النتيجة أعلاه

( م ب ، م جـ ) = أصغر قيمة موجبة لـ م ب س + م جـ ص

= أصغر قيمة موجبة لـ م( ب س + جـ ص )

= م ( ب ، جـ )

نظرية 2.4

إذا كان ب | ك و جـ | ك ( ك > صفر ) فإن

( ب / ك ، جـ / ك ) = (1 / ك) ( ب ، جـ )

البرهان

مباشرة من النظرية 2.3 بوضع م = 1 / ك

نظرية 2.5

إذا كان ( ب ، م ) = ( جـ ، م ) = 1 فإن ( ب جـ ، م ) = 1

البرهان

باستخدام النظرية 2.2 ، يوجد أعداد صحيحة س و ص بحيث

1 = ب س + م ص و بالمثل أيضا يوجد س1 و ص1 بحيث

1 = جـ س1 + م ص1 و منهما

( ب س )(جـ س1 ) = ( 1 - م ص )(1 - م ص1 )

ب جـ س س1 = 1 - م ( ص + ص1 - م ص ص1 )

ب جـ س س1 = 1 - م ك

ب جـ س س1 + م ك = 1

من النظرية 1.1 أي قاسم مشترك بين ب جـ و م هو قاسم للـ 1

و عليه ( ب جـ ، م ) = 1

خوارزمية إقليدس ( Euclidean Algorithm )

ب و أ عددان صحيحان ( أ > صفر ) بإجراء خوارزمية القسمة بشكل متكرر ،

نحصل على سلسلة من المعادلات

ب = أ ك1 + ر 1 ، 0 < ر1 < أ ( نقسم ك1 على ر1 ) :

ك1 = ر1 ك2 + ر2 ، 0 < ر2 < ر1 و هكذا

مثال

نقسم 99 ÷ 4

99 = 24 × 4 + 3 ( الباقي = 3 ) ، الآن نقسم 4 ÷ 3

4 = 1 × 3 + 1 ( الباقي = 1 ) ، الآن نقسم 3 ÷ 1

3 = 1 × 3 + 0 ( الباقي = 0 )

القاسم المشترك الاكبر هو آخر باقي غير مساو للصفر أي الواحد في هذه

الحالة : د = 1

نتيجة

يمكننا إيجاد حل للمعادلة ( ليس كل الحلول ) 99 س + 4 ص = 1

نعبّر عن القاسم المشترك الاكبر بالنسبة للعددين ، نفعل ذلك

بالتعويض بشكل تراجعي في عمليات القسمة اعلاه :

من الثانية : 1 = 4 - 3 × 1 ------------------(*)

من الأولى : 3 = 99 - 4 × 24

نعوض قيمة الـ 3 في (*) :

1 = 4 - ( 99 - 4 × 24 )

1 = 4 - 99 + 4 × 24

1 = 4(25) + 99 (-1)

س = - 1 ، ص = 25

تعريف 2.2 - المضاعف المشترك الأصغر

يكون العدد الصحيح د ≠ صفر مضاعفا العدد أ إذا كان د | أ

مثال : 36 مضاعفا للعدد 12 لأن 36 | 12

مجموعة مضاعفات العدد أ هي المجموعة التي تحتوي على جميع مضاعفات

العدد أ ، بمعنى آخر جميع الاعداد الصحيحة د ( الغير مساوية للصفر) و التي

تحقق د | أ . نرمز لهذه المجموعة بالرمز م _أ ( M_a )

مثال : م₈ = {0 ، ± 8 ، ± 16 ، ± 32، ....... }

{ 0, ± 5 , ± 10 , ± 15 , ±20 , ± 25 , ....... } = M₅

يكون العدد الصحيح أ مضاعفا مشتركا ( Common Multiple ) لـ ب و جـ

إذا كان أ | ب و أ | جـ

مثال : 15 مضاعف مشترك ( Common Multiple ) لـ 3 و 5

أقل مضاعف مشترك موجب ، نطلق عليه المضاعف المشترك الأصغر ( Least Common Multiple )

[ ب ، جـ ]

بالمثل ، المضاعف المشترك الأكبر للأعداد أ ، ب ، جـ ، ......، ي

نرمز له :[ أ ، ب ، جـ ، .......، ي]

نظرية 2.5

1) [م ب ، م جـ ] = م [ب ، جـ ] حيث م > صفر

2) [ب ، جـ ] × ( ب ، جـ ) = | ب × جـ |

البرهان : عند الطلب أو بعد حل التمارين

 

 

1 ) قرر أي من العبارات التالية صحيحة و أي منها خطأ ، في حالة الصحة اعط تبريرا مقتضبا و في حالة الخطأ اعط مثالا :

أ) إذا كان جـ = أ س + ب ص فإن جـ = ( أ ، ب )

ب) القاسم المشترك لـ أ و ب يكون قاسما لـ ( أ ، ب )

جـ) إذا كان أ ب | جـ فإن أ | جـ و ب | جـ

د) ( أ ب ، جـ ) = ( أ ، جـ ) × ( ب ، جـ ) إذا كان أ و ب أعداد أولية

2) باستخدام خوارزمية إقليدس ، أوجد القاسم المشترك الأكبر

أ) 7469 ، 2464

ب) 1109 ، 4999

3) باستخدام خوارزمية إقليدس ، أوجد القاسم المشترك الأكبر

( 42823 ، 6409 )

أوجد س و ص بحيث

6409 س + 42823 ص = 17

4) إذا كان ( أ ، 4 ) = 2 و ( ب ، 4 ) = 2 برهن أن ( أ + ب ، 4 ) = 4

5) برهن إذا كان أ ، ب > صفر بحيث ( أ ، ب ) = [ أ ، ب ] فإن أ = ب

6) أثبت أنه لا يوجد أعداد صحيحة س و ص بحيث

س + ص = 100 و ( س ، ص ) = 3

7) أثبت أنه يوجد أعداد صحيحة س و ص بحيث

س + ص = 100 و ( س ، ص ) = 5

8) ليكن م و ن أعداد صحيحة موجبة ، أثبت أنه يوجد أعداد صحيحة س و ص

بحيث س + ص = م ، ( س ، ص ) = ن إذا و فقط إذا م | ن

9) أوجد أ و ب أعداد صحيحة موجبة التي تحقق

( أ ، ب ) = 10 ، [ أ ، ب ] = 100

أوجد جميع الحلول

10) برهن أن ( أ ، أ + ب ) = ( أ ، ب )

11) إذا كان أ و ب أعداد صحيحة موجبة ، برهن أن ( أ ، ب ) = 1

إذا و فقط إذا ( أ² ، ب² ) = 1

12 ) برهن أن ( ن - 1 ، 2ن - 1 ) = 1 و كذلك ( 2ن - 1 ، 3ن - 1 ) = 1

13)* إذا كان م و ن أعداد صحيحة موجبة ، برهن أن

( 2^م - 1 ، 2 ^ن - 1 ) = 1 إذا و فقط إذا ( م ، ن ) = 1

14) برهن أن ( 2ن² + 6ن - 4 ، 2ن² + 4ن - 3 ) = 1
( استخدم القسمة و خوارزمية إقليدس )

15)* إذا كان ( أ² ، ب جـ ) = م ، م عدد اولي أثبت أنه

إما ( أ ، ب ) = 1 أو ( أ ، جـ ) = 1

 

 

الكلام ده كبير


في الواقع لم اقراه كله

لكنه يحتاج منا الى قراءة متانية

بارك الله بك اخى الكريم

 

 

سلام عليكم ورحمة الله وبركاته

يعطيك العافية
1)

أ) غير صحيح

كما ذكرت في شرحك
مثال : 2 = 3 × - 1 + 5 × 1

و لكن ( 3 ، 5 ) = 1 و ليس 2
مثال اخر
5=4×3-7×1
ولكن و لكن (4 ، 7 ) = 1 و ليس 5

ب)
صح
لكن ماعرفت اثبتها


جـ)
خطأ
مثال 4×5 | 4 ولكن 4 لايقسم 5

د)
خطأ

( 3×3 ، 12) لاتساوي (3، 12) × ( 3 ، 12)


مستعجل بعدين اكمل الحلول^_^

 

 

1) قرر أي من العبارات التالية صحيحة و أي منها خطأ ،
في حالة الصحة اعط تبريرا مقتضبا و في حالة الخطأ اعط مثالا :

اقتباس :

أ) إذا كان جـ = أ س + ب ص فإن جـ = ( أ ، ب )

عبارة خاطئة
مثال معاكس: لدينا: 14=8×1+6×1 لكن 14≠ (6،8)

اقتباس :

ب) القاسم المشترك لـ أ و ب يكون قاسما لـ ( أ ، ب )

عبارة صحيحة
دوماً توجد أعداد صحيحة س,ص بحيث:( أ ، ب )=أ س+ب ص
إذا كان ء قاسم مشترك لـ أ,ب عند ئذٍ:
أ | ء ومنه: أ س | ء
ب| ء ومنه: ب ص | ء
إذاً ( أ ، ب ) =أس +ب ص | ء

اقتباس :

جـ) إذا كان أ ب | جـ فإن أ | جـ و ب | جـ

عبارة خاطئة
مثال معاكس:3×5|3 لكن 3 لاتقسم 5

اقتباس :

د) ( أ ب ، جـ ) = ( أ ، جـ ) × ( ب ، جـ ) إذا كان أ و ب أعداد أولية

عبارة خاطئة
مثال معاكس:(2×6,2)≠(6،2)×(6,2)

 

 

2) باستخدام خوارزمية إقليدس ، أوجد القاسم المشترك الأكبر

اقتباس :

أ) 7469 ، 2464

7469=3×2464+77
2464=32×77+0
إذاً (2464,7469)=77

اقتباس :

ب) 1109 ، 4999

4999=4×1109+563
1109=1×563+546
563=1×546+17
546=32×17+2
17=8×2+1
2=2×1+0
إذاً (4999,1109)=1

 

 

3) باستخدام خوارزمية إقليدس ، أوجد القاسم المشترك الأكبر ( 42823 ، 6409 )
42823=6×6409+4369
6409=1×4369+2040
4369=2×2040+289
2040=7×289+17.................(*)
289=17×17+0
إذاً (6409،42823)=17

اقتباس :

أوجد س و ص بحيث 6409 س + 42823 ص = 17

من(*)
17=2040-7×289
17=2040-7×(4369-2×2040)
17=15×2040-7×4369
17=15×(6409-1×4369)-7×4369
17=15×6409-22×4369
17=15×6409-22×(42823-6×6409)
17=6409×147+42823×-22
س=147 ,ص=-22

 

 

عسل مصفى ، حسام محمد

 

 

بارك الله بمجهودك الكبير أخي uaemath

مقدّرين وممنونين