نظرية الأعداد 1

المدير العام

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

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

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

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

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

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

{± 1 , ± 2 , ± 3 , ± 4 , ± 6 , ± 12 } = D12

يكون العدد الصحيح أ قاسما مشتركا ( 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) ( ب ، جـ ) = ( ب - جـ ، جـ )

Cool

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

مثال ( 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
__________________