سننتناول في هذا الدرس المواضيع التالية :
- خوارزمية القسمة ( 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) ( ب ، جـ ) = ( ب - جـ ، جـ )
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