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

خوارزمية أقليدس .. ليكن a , b أعداد صحيحة
فيوجد عدين صحيحين m و r بحيث أن :-

a = mb + r

فإن GCD(a,b) = GCD(b,r)    ..l‏

الإثبات المختصر :

نفرض وجود عددين a و b طبيعين بحيث

a = mb + r

حيث m عدد طبيعى و r هو باقى القسمة .

ليكن GCD(a,b) = d

اذاً d قاسم لـ a  و d قاسم لـ b ايضاً

تؤدى الى ان : d قاسم لـ a - mb

اوى بصفة أخرى d قاسم لـ r

اذاً  GCD(a,r) = d

ولكن GCD(a,b) = d

اذاً  GCD(b,r) = d

وهذا يؤدى الى ان : GCD(a,b) = GCD(b,r)   ..l‏