الگوریتم اقلیدس

برای این که ثابت کنیم چرا با الگوریتم فوق ب.م. م به دست می‌آید به لم زیر توجه کنید:

اثبات: فرض می‌کنیم ${\displaystyle (a,b)=d}$

شبه کد الگوریتم اقلیدسی:
procedure gcd(a,b:positive integers)
x:=a
y:=b
while y≠0
r:=x mod y
x:=y
y:=r
return x{gcd(a,b)is x}

الگوریتم اقلیدسی از تقسیم‌هایی از مرتبهٔ O(log b) برای پیدا کردن بزرگترین مقسوم علیه‌های مشترک اعداد صحیح a و b استفاده می‌کند که در آن a≥b است.
وقتی الگوریتم اقلیدسی در پیدا کردن a≥b، gcd(a,b) به کار گرفته می‌شود دنبالهٔ تساوی‌های زیر (که در آن a=R0 و b=R1) به دست می‌آید.
R0=R1q1+R2 0≤R2<R1
R1=R2q2+R3 0≤R3<R2
.
.
.
Rn-2=Rn-1qn-1+Rn 0≤Rn>Rn-1
Rn-1=Rnqn
در بدست آوردن n ، Rn=gcd(a,b) تقسیم به کار رفته‌است.دقت کنید که خارج قسمت‌های q1,q2,q3,...qn-1 حداقل 1 هستند.به علاوه qn≥2 چون Rn<Rn-1 در نتیجه
Rn≥1=F2
Rn-1≥2Rn≥2F2=F3
Rn-2≥Rn-1+Rn≥F3+F2=F4
.
.
.
R2≥R3+R4≥Fn-1+Fn-2=Fn
b=R1≥R2+R3≥Fn+Fn-1=Fn+1
بنابراین در استفاده از الگوریتم اقلیدسی برای پیدا کردن gcd(a,b) با n ، a≥b تقسیم به کار میرود،آنگاه b≥Fn+1.

• آموزش ریاضیات گسسته دوره پیش دانشگاهی نظام جدید، نوشتهٔ سید حسین سیدموسوی، انتشارات مبتکران