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

**الخطوة الأولى: فهم خوارزمية إقليدس** تعتمد خوارزمية إقليدس على مبدأ أن القاسم المشترك الأكبر (GCD) لعددين صحيحين a و b لا يتغير إذا استبدلنا العدد الأكبر بالباقي من قسمة العدد الأكبر على العدد الأصغر. رياضياً: gcd(a, b) = gcd(b, a mod b). هذه الخاصية تسمح بتكرار عملية القسمة حتى يصبح الباقي صفراً، عندها يكون القاسم المشترك هو القاسم الأخير غير الصفري. على سبيل المثال، لحساب gcd(56, 15): 56 ÷ 15 = 3 والباقي 11، ثم 15 ÷ 11 = 1 والباقي 4، ثم 11 ÷ 4 = 2 والباقي 3، ثم 4 ÷ 3 = 1 والباقي 1، ثم 3 ÷ 1 = 3 والباقي 0. إذن gcd هو 1. هذه الخطوة ضرورية لفهم الأساس النظري للخوارزمية.

**الخطوة الثانية: إدخال القيمتين a و b** يجب على المستخدم إدخال عددين صحيحين (يمكن أن يكونا موجبين أو سالبين). ستقوم الآلة الحاسبة بتنفيذ الخوارزمية باستخدام القيم المطلقة للأعداد لتسهيل الحساب، لكن النتائج النهائية (المعاملات) ستُصحح حسب الإشارات الأصلية. تأكد من أن كلا المدخلين ليسا صفراً في نفس الوقت. إذا كان أحدهما صفراً، يكون gcd هو العدد الآخر، وتكون معاملات Bezou بسيطة (1,0) أو (0,1).

**الخطوة الثالثة: تطبيق الخوارزمية الموسعة** بعد الحصول على gcd باستخدام الخوارزمية العادية، نستخدم خوارزمية إقليدس الموسعة (Extended Euclidean Algorithm) لإيجاد معاملات x و y بحيث a·x + b·y = gcd(a,b). يتم ذلك بتتبع خطوات القسمة بشكل عكسي. نكتب كل باقٍ بدلالة الأعداد السابقة، ثم نعوض تدريجياً لنصل إلى معادلة خطية. على سبيل المثال: gcd(56,15)=1. الخطوات: 56 = 3·15 + 11 → 11 = 56 - 3·15; 15 = 1·11 + 4 → 4 = 15 - 1·11; 11 = 2·4 + 3 → 3 = 11 - 2·4; 4 = 1·3 + 1 → 1 = 4 - 1·3; 3 = 3·1 + 0. بالتعويض العكسي: 1 = 4 - 1·3 = 4 - 1·(11 - 2·4) = 3·4 - 1·11 = 3·(15 - 1·11) - 1·11 = 3·15 - 4·11 = 3·15 - 4·(56 - 3·15) = 15·15 - 4·56. إذن x = -4, y = 15.