خوارزمية اقليدس The Euclidean algorithm وكتابته القاسم المشترك الأكبر (a,b) كتركيب خطي
.png "خوارزمية اقليدس وكتابته القاسم المشترك الأكبر (a,b) كتركيب خطي")
تعريف : القاسم المشترك الأكبر (الأعظم) g.c.d
اذا كان a ,b عددين ليس كلاهما صفر ، نقول ان d قاسم مشترك اعظم للعددين a,b اذا كان ويكتب d=(a, b)
اولا : d قاسم مشترك لهما اي ان
d|a و d|b
ثانيا : لا يوجد للعددين قاسم مشترك اكبر من d اي ان
اذا وجد عدد اخر c يقسم كلا من العددين c|a , c|b فان c يجب ان يكون اقل من او يساوي d
ملاحظة : القاسم المشترك الأعظم معرف لجميع الحالات ما عدا ان يكون a=b=0
ملاحظة : القاسم المشترك الأعظم d=(a , b ) دائما اكبر من الواحد الصحيح
مثال : اوجد القاسم المشترك الأعظم (-39 , 26)
القواسم الموجبة للعدد 26 هي 1,2,13,26
القواسم الموجبة للعدد -39 هي 1,3,13,39
القواسم المشتركة هي 1,13
وبالتالي القاسم المشترك الأعظم هو 13 ، نكتب 13=(26,-39)
استخدام خوارزمية اقليدس في إيجاد القاسم المشترك الأعظم
ان الطريقة الأفضل في إيجاد القاسم المشترك الأكبر لعددين او اكثر هي طريقة خوارزمية اقليدس والتي تعتمد على نظرية هامة وهي ان القاسم المشترك الأكبر بين عددين (b,a) تساوي القاسم المشترك الأكبر بين العدد a ,باقي قسمة العدد b على a
نظرية : اذا كان العددين a,b ينتميان الى مجموعة الاعداد الصحيحة وكان d=(a,b) فان d=(a,r) حيث ان
r+aq=b (اي ان r هي باقي قسمة العدد b على a)
مثال : استخدم خوارزمية اقليدس لا يجاد القاسم المشترك الاكبر للعددين 1338و 501
نريد إيجاد (1338,501) او تكتب نريد إيجاد gcd(1338,501) باستخدام خوارزمية اقليدس
الخطوة الأولى : نكتب العدد 1338 كحاصل ضرب للعدد 501 مع عدد صحيح ونجمع الباقي بحيث يكون الباقي اقل من 501
$$1338=(2)501+336$$
الخطوة الثانية : نكتب العدد 501 كحاصل ضرب العدد 336 مع عدد صحيح ونجمع الباقي بحيث يكون الباقي اقل من 336
$$501=(1)336+165$$
الخطوة الثالثة : نكتب العدد 336 كحاصل ضرب العدد 165 بعدد صحيح ونجمع الباقي بحيث يكون الباقي اقل من 165
$$336=(2)165+6$$
الخطوة الرابعة : نكتب العدد 165 كحاصل ضرب للعدد 6 بعدد صحيح ونجمع الباقي بحيث يكون الباقي اقل من 6
$$165=(27)6+3$$
الخطوة الخامسة : نكتب العدد 6 كحاصل ضرب العدد 3 بعدد صحيح ونجمع الباقي بحيث يكون الباقي اقل من 3
$$6=(2)3+0$$
من الخطوة الخامسة نجد ان الباقي يساوي الصفر ، وبذلك فان القاسم المشترك الأكبر للعددين (1338,501) هو 3
اي ان 3=(1338,501)g.c.d
تكمن أهمية طريقة اقليدس في إيجاد القاسم المشترك الأكبر لأنه بإمكاننا استخدام خطوات الطريقة (تراجعيا) في كتابة القاسم المشترك الأعظم d في صورة تركيب خطي بدلالة العددين a,b
مثال : اوجد x,y بحيث 501y + 1338x= (1338,501)
او اكتب القاسم المشترك في صرة تركيب خطي بدلالة الاعداد 1338,501
نستخدم الخطوات السابقة التي قمنا بإيجاد القاسم المشترك الأعظم من خلالها ونبدأ بالخطوة قبل الأخيرة (الخطوة الرابعة ) ، من الخطوة الرابعة نجد ان
.png&description=خوارزمية اقليدس The Euclidean algorithm وكتابته القاسم المشترك الأكبر (a,b) كتركيب خطي){kind=link}
تعليقات
إرسال تعليق