تعريف : خوارمية أقليدس هي تقنية تمكننا من تحديد القاسم المشترك الأكبر بين عددين صحيحين طبيعيين.
الطريقة :
نعتبر a و b عددين صحيحين طبيعيين بحيث a<b.
نقوم بقسمة b على a وليكن الباقي هو r1 ثم نقوم بقسمة a على r1وليكن الباقي هو r2 ثم نقوم بقسمة r1 على r2 ولنعتبر أن الباقي هو r3 ثم نقسم r2 على r3 ونكرر العملية حتى يكون الباقي هو 0.
القاسم المشترك الأكبر ل a و b هو آخر باقي غير منعدم.
مثال1 : لنحدد القاسم المشترك الاكبر ل 46 و 18:
إذن PGCD(46,18)=2
مثال2 : لنحدد القاسم المشترك الاكبر ل 259 و 140:
إذن PGCD(140,259)=7
الشرح بالفيديو
