نظرية الأعداد - الدرس الاسبوعي(2)

02-03-2007, 06:29 PM

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

خوارزمية القسمة ( 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


العضو المميز	الموضوع المميز	المشرف المميز
المنتدى متاح للتصفح فقط ولا يقبل المشاركات الجديدة	ماشاء الله تبارك الله ماشاء الله لاقوة الا بالله	المنتدى متاح للتصفح فقط ولا يقبل المشاركات الجديدة