خوارزمية أقليدس
في الرياضيات، خوارزمية أقليدس هي طريقة فعالة تمكن من إيجاد القاسم المشترك الأكبر لعددين وهو أكبر عدد يقسم في نفس الوقت العددين معا بدون أي باق من القسمة. يُرمز له بالفرنسية ب PGCD وبالإنجليزية GCD. 
سميت هذه الخوارزمية هكذا نسبة إلى عالم الرياضيات الإغريقي أقليدس الذي وصف الخوارزمية لأول مرة في كتابه المعروف باسم الأصول (حوال عام 300 ق.م). ومثال على الخوارزمية، تتم خطوة بخطوة لإجراء عملية حسابية وفقًا لقواعد محددة جيدًا، وهي أحد أقدم الخوارزميات المستخدمة في الاستخدام الشائعة. يمكن استخدامها لتقليل الكسور إلى أبسط أشكالها (او كسر غير قابل للاختزال)، وهو جزء من العديد من الحسابات النظرية والتشفيرية (او التعمية).
تعتمد الخوارزمية الإقليدية على مبدأ أن القاسم المشترك الأكبر من رقمين لا يتغير إذا تم استبدال العدد الأكبر مع العدد الأصغر. على سبيل المثال، ال GDC من 252 و 105 (مثلما 252 = 21×12 و 105 = 21×5)، ونفس الرقم 21 هو ايضاً ال GDC من 105 و 252 - 105 = 147. بما أن هذا الاستبدال يقلل من الحجم الأكبر من الرقمين، تكرار هذه العملية يعطي أزواجًا صغيرة من الأرقام بشكل متتالي حتى يصبح الرقمان متساويين. عندما يحدث ذلك ، فهي GCD من الرقمين الأصليين. من خلال عكس الخطوات (خوارزمية إقليدس الممددة)، يمكن التعبير عن GCD كـ تركيبة خطية من الأرقام الأصلية لكل منهما مضروبة في عدد صحيح موجب أو سالب، على سبيل المثال، 21 = 5 × 105 + (−2) × 252. الحقيقة أنَ GCD يمكن التعبير عنها على الدوام بمتطابقة بوزو.
القاسم المشترك الأكبر ل 48 و 60 هو 12.
القاسم المشترك الأكبر للعددين 252 و 198:
252 = 198 * 1 + 54 ‘ أربع وخمسون هو باقي قسمة 252 على 198
فنجد القاسم المشترك للعددين 198 و 54
198 = 54 * 3 + 36 ‘ ست وثلاثون هو باقي القسمة.
نكرر العملية هذه المرة مع : 54 و 36
54 = 36 * 1 + 18
مرة أخرى :
36 = 18 * 2 + 0
هنا وصلنا للصفر فيكون العدد الثاني 18 هو القاسم المشترك الأكبر.
القاسم المشترك الأكبر لعددين طبيعيين A، B يساوي القاسم المشترك الأكبر للعدد الثاني B وباقي قسمة A على B، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر.
حيث r هو باقي قسمة A على B.
N هو القاسم المشترك الأكبر.
خوارزمية أقليدس هي واحدة من أقدم الخوارزميات الجارية الاستعمال. ظهرت في كتاب الأصول لإقليدس (في حوالي عام 300 قبل الميلاد).
تنص متطابقة بوزو على أن القاسم المشترك الأكبر g لعددين a و b يمكن أن يمثل مجموعا خطيا للعددين a و b؛ أي أنه يوجد عددان، s و t حيث يتوفر ما يلي:
formula_1
یمكن تمثیل القاسم المشترك الأكبر للعددین عن طریق دمج خطي مع عددین آخرین ،
كیف یمكن أیجاد قیمتي n و m وذلك عن طریق خوارزمیة اقلیدس الممتدة وهناك ثلاثة طرق لمعرفة هذه القیم (الطرق هي مشابه لبعض، لكن یمكن القول أنها مختصره من الأخریات).
الطريقة الأولى: وهي يمكن ان نطلق عليها التراجع وفي هذه الطريقة نقوم بالحل عن طريق خوارزمية اقليدس وبعدها تقول بالتراجع الخلفي لايجاد قيمتي m،n كما في المثال التالي:
مثال: قم بتمثيل العددين 26 و 21 بطريقة اقليدس الممتدة :
فنبدأ بالحل كما هو الحال في طريقة اقليدس :
26 = 1* 21 + 5 و 21 = 4 * 5 + 1 و 5 = 5 * 1 + 0
وتتوقف عند الصفر. الآن المعادلة التي قبل المعادلة التي باقيها صفر أي المعادلة الثانية نقوم بكتابتها بالشكل التالي :
أیضا المعادلة الأولى بنفس الشكل :
في المعادلتين السابقتين
ومن غیر أجراء عملیة حسابیة، فقط نفك القوس لینتج :
1 = 21 -4*26 +4*21
1=21(1+4)-4*26 حيث 21 عامل مشترك
لیكون لدینا الناتج النهائي : 4*21 +21
1 = 5*21 + (-4)*26
نتاكد من النتيجة 5*21+ -4*26 والناتج يساوي واحد إذاً المعادلة صحيحة
اذاً قيمة m هي 5 وقيمة n هي -4.
يمكن لخوارزمية أقليدس أيضا أن تستعمل من أجل حلحلة العديد من المعادلات الديوفانتية الخطية. تظهر واحدة من هده المعادلات في مبرهنة الباقي الصيني.
مبرهنة الباقي الصيني
انظر شجرة ستيرن-بروكوت.
دُرست فعالية خوارزمية أقليدس بشكل كثيف. تتمثل هذه الفعالية في عدد الخطوات اللازمة من أجل إيجاد القاسم المشترك الأكبر المراد حسابه. أول تحليل لفعالية الخوارزمية يرجع إلى العالم غيينو، (كان ذلك عام 1811)، حيث أثبت أنه أثناء حساب القاسم المشترك الأكبر للعددين u و v، عدد الخطوات اللازمة، لا يمكن أن يتجاوز v. وزاد فيما بعد هذا البرهانَ دقة عندما برهن أن هذا العدد لا يمكن أن يتجاوز v/2 +2.
انظر إلى بيير جوزيف إتيان فينك وإلى إيميل ليجي وإلى غابرييل لامي.