Algorithme d’Euclide خوارزمية إقليدس لتحديد القاسم المشترك الأكبر

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

الشرح بالفيديو

 

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.