شبكة الرياضيات رمز

Extended Euclidean Algorithm

 

خوارزمية إقليدس الموسعة (أو الخوارزمية الإقليدية الموسعة) هي عملية حسابية نستطيع من خلالها إيجاد القاسم المشترك الأكبرd للعددين a,b  وإيجاد حل للمعادلة

 

ax+by=d    (I)

 

هذه الخوارزمية تمكننا أيضا من إيجاد الحل العام للمعادلة

 

ax+by=0   (II)

 

وإذا أضفناه إلى حل خاص من حلول المعادلة (I) نحصل على كل حلولها.

 

الخوارزمية الإقليدية الموسعة لها أكثر من أسلوب في العرض.  البعض يعبر عنها باستخدام الجداول والبعض يستخدم أسلوب المتجهات^[م] أو الثلاثيات المرتبة وهذا ما نقوم به الآن.

 

 

ليكن لدينا العددين الموجبين a,b. خذ الثلاثيين

u=(a,1,0)

v=(b,0,1)

 

أوجد العدد الصحيح الذي يمثل الجزء الصحيح من قسمة a على b ثم كون الثلاثي w بالصورة

w=u-vh

 

كرر نفس العمل ولكن على الثلاثيين المرتبين v,w لينتج ثلاثي جديد z ثم نفس الخطوات على w,z وهكذا حتى تصل في النهاية إلى الثلاثي الذي فيه المركبة الأولى متلاشية عندها تكون مركبات الثلاثي الذي قبله هي

 

(d,x,y)

مثال 1:

 

إذا كان (a,b)=(4542,1184) فأوجد حل المعادلة ax+by=d حيث d القاسم المشترك الأكبر لـ a,b.

الحل: نبدأ بالثلاثيين u=(a,1,0),  v=(b,0,1).  لدينا هنا h=3

 

u=(4542,1,0),  v=(1184,0,1),  w=u-vh=(990,1,-3)

 

كرر العمل على الثلاثي الجديد والذي قبله حيث فيهما h=1

 

(1184,0,1),  (990,1,-3), (194,-1,4)

 

كرر العمل على الثلاثي الجديد والذي قبله حيث فيهما h=5

 

(990,1,-3), (194,-1,4), (20,6,-23)

 

كرر العمل على الثلاثي الجديد والذي قبله حيث فيهما h=9

 

(194,-1,4), (20,6,-23),  (14,-55, 211)

 

كرر العمل على الثلاثي الجديد والذي قبله حيث فيهما h=1

 

 (20,6,-23),  (14,-55, 211),  (6,61,-234)

 

كرر العمل على الثلاثي الجديد والذي قبله حيث فيهما h=2

 

(14,-55, 211),  (6,61,-234),  (2,-177,679)

 

كرر العمل على الثلاثي الجديد والذي قبله حيث فيهما h=3

 

(6,61,-234),  (2,-177,679),  (0,592,-2271)

 

الثلاثي الأخير فيه المركبة الأولى تساوي صفر. هنا نتوقف ويكون الذي قبله هو الثلاثي (d,x,y) أي أن القاسم المشترك الأكبر هو 2 وأن

 

(4542)(-177)+(1184)(679)=2

 

وبهذا نكون قدمنا حلا للمعادلة 4542x+1184y=2.

 

الثلاثي الأخير يتضمن الحل (592,-2271) للمعادلة 4542x+1184y=0 , وهو أصغر حل بأعداد موجبة لهذه المعادلة. من السهل التأكد أن (k*592, -k*2271) هو حل لهذه المعادلة حيث k عدد صحيح وذلك لأن

 

ax+by=0 .--->  a(kx)+b(ky)=0

 

بإضافة هذا الحل العام (k*592, -k*2271) للحل  الخاص  (-177,679)نحصل على الحل العام

 

X=-177+k*592

Y=679-k*2271

 

للمعادلة4542x + 1184y = d  حيث d القاسم المشترك الأكبر للعددين 4542, 1184.

 

 

مسائل

* لدى تاجر نوعين من  سلعة غذائية واحدة , النوع الأول يبيع منه الكيلو بسعر 29 دينار ويبيع الكيلو من النوع الثاني بسعر 18 دينار.  إذا علمت أن سعر مجموع ما باعه يساوي 289 دينار فكم كيلو باع من كل نوع؟

إرشاد: (29,18)=1 . أبدا من المعادلة  29x+18y=1  وأوجد x,y ثم اضرب المعادلة في 289 لتحويلها لمعادلة المسألة وحدد من الحل العام الذي تقدمه نظرية حل معادلة ديفونتية خطية ذات مجهولين قيم x,y الموجبة. الحل (5,8).