الخوارزمية الإقليدية

Euclidean Algorithm

الخوارزمية الإقليدية أو خوارزمية إقليدس Euclid's Algorithm حيث أول من قدمها هو إقليدس في الكتاب السابع من عمله المسمى "العناصر" كطريقة حسابية لإيجاد القاسم المشترك الأكبر لعددين a,b والذي نستخدم له الرمز (a,b). الخوارزمية تطبق على الأعداد a,b بحيث $a > b \ge 0$ وهذا كافي لأنه لأي صحيحين x,y فإن

(x,y)=(|x|,|y|)

تعتمد هذه الطريقة على خوارزمية القسمة التي تؤكد على أنه لأي عددين صحيحين a,b يوجد صحيحين q,r بحيث

a=qb+r , 0<r<b

وهي عملية قسمة العدد a على العدد b. العدد q خارج القسمة و العدد b هو الباقي.

خوارزمية إقليدس عبارة عن تطبيق^[م] متعاقب لخوارزمية القسمة حيث نبدأ بقسمة العدد الأكبر a على b ثم نطبق خوارزمية القسمة تكراريا بقسمة القاسم على الباقي وهكذا نستمر حتى نصل بعد عدد من التطبيقات إلى الباقي صفر. عندئذ فإن القاسم المشترك الأكبر للعددين a,b هو آخر باقي لا يساوي صفر.

فمثلا إذا كان لدينا العددين $a > b \ge 0$ . من خوارزمية القسمة يوجد $q_1 ,\;r_1$ بحيث

$a = q_1 b + r_1 ,\quad 0 \le r_2 < b$

خذ المقسوم عليه والباقي $b,\;r_1$ وطبق خوارزمية القسمة عليهما, إذا

$b = q_2 r_1 + r_2 ,\quad 0 \le r_2 < r_1$

أيضا

$r_1 = q_3 r_2 + r_3 ,\quad 0 \le r_3 < r_2$

وهكذا حتى الوصول للباقي صفر وهذا أمر حتمي لأن في كل عملية يتناقص الباقي عن الباقي الذي قبله, فإذا كانت آخر عمليتي تطبيق لخوارزمية القسمة هي

$r_{n - 2} = q_n r_{n - 1} + r_n ,\quad 0 \le r_n < r_{n - 1}$

$r_{n - 1} = q_{n + 1} r_n + 0$

فإن $(a,b) = r_n$ .

ولكن ما هو الأساس^[م] النظري للطريقة؟ بمعنى آخر كيف علمنا أن الباقي $r_n$ هو القاسم المشترك الأكبر؟. الجواب يعتمد على ملاحظة أنه إذا كانت a=qb+r خوارزمية القسمة للعددين a,b فإن

(a,b)=(a,r)

تأكد من ذلك, إذا من خوارزمية إقليدس نستنتج أن

$(a,b) = (b,r_1 ) = \cdots = (r_{k - 1} ,r_k ) = \cdots = (r_n ,0) = r_n$

مثال 1: أوجد القاسم المشترك الأكبر للعددين a=321805575, b=198645.

الحل:

321805575=1620*198645+675

198645=294*675+195

675=3*195+90

195=2*90+15

90=18*5+0

إذا (321805575, 198645)=15.

ملاحظة: من خلال قواعد قابلية القسمة واضح أن العددين a,b في المسألة يقبلان القسمة على الأوليان 3,5 ولذلك يقبلان القسمة على حاصل ضربهما15 , ولكن هذا لا يكفي لضمان أن 15 هو أكبر قاسم مشترك.

خوازمية إقليدس ومتطابقة بيزوه

تستخدم خوازمية إقليدس ( ولكن بطريقة عكسية) لإيجاد x,y في متطابقة بيزوه حيث نبدأ من الخطوة ما قبل الأخيرة

$r_{n - 2} = q_n r_{n - 1} + r_n ,\quad 0 \le r_n < r_{n - 1}$

ونكتب المضاعف المشترك الأكبر $d = r_n$ بدلالة القيم الأخرى , أي

$r_n = r_{n - 2} - q_n r_{n - 1}$

ثم نعوض عن الباقي $r_{n - 1}$ من الخطوة السابقة وهكذا حتى نصل في النهاية إلى متطابقة بيزوه

ax+by=d

مثال 2 : خوارزمية اقليدس على العددين a,b في المثال السابق كانت على النحو التالي

321805575=1620*198645+675

198645=294*675+195

675=3*195+90

195=2*90+15

90=18*5+0

من الخطوة قبل الأخيرة نبدأ لتحديد x,y الخاصة بمتطابقة بيزوه

15=195-2*90

=195-2(675-3*195)

=7*195-2*675

=7(198645-294*675)-2*675

=7*198645-2060*675

=7*198645-2060(321805575-1620*198645)

=3337207*198645-2060*321805575

إذا

3337207*198645-2060*321805575=15

وبالتالي x=-2060, y=3337207.

الطريقة في هذا المثال متعبة وغير منسقة بسبب التعويض (الإحلال) التراجعي المستمر. هناك طريقة تسمى طريقة إقليدس الموسعة تحسب x,y وتحسب أيضا d بطريقة مباشرة وقد خصص لها موضوع آخر.

نبذة عن كاتب الموضوع

$User picture$