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

الگوریتم اقلیدس روشی موسوم به روش نردبانی یا تقسیمات متوالی برای یافتن بزرگترین مقسوم علیه مشترک (ب.م.م) دو عدد است.

بزرگترین مقسوم علیه مشترک دو عدد a و b را به‌صورت $gcd(a,b)$ نشان می‌دهند. برای محاسبه $gcd(a,b)$ عدد بزرگتر را بر عدد کوچکتر تقسیم می کنیم؛ اگر باقی‌مانده صفر بود، پس عدد کوچکتر همان ب.م.م دو عدد است؛ وگرنه عدد کوچکتر را بر باقی‌مانده تقسیم قبلی تقسیم می‌کنیم و این فرایند را تا جایی پیش می‌بریم تا به باقی مانده صفر برسیم.

مثال: برای محاسبهٔ $gcd(18,12)$ عدد بزرگتر یعنی ۱۸ را بر ۱۲ تقسیم می‌کنیم و سپس ۱۲ را بر باقی ماندهٔ تقسیم قبل (باقی‌مانده ۱۸ تقسیم بر ۱۲ مساوی با ۶ است) تقسیم می‌کنیم. ۱۲ تقسیم بر ۶ باقی‌مانده صفر دارد؛ بنابراین $gcd(18,12)=6$.

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

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

لم: اگر $a=bq+r$ آن‌گاه $(a,b)=(b,r)$

اثبات: فرض می‌کنیم $(a,b)=d$ و $(b,r)=d'$. پس

شبه کد الگوریتم اقلیدسی:
procedure gcd(a,b:positive integers)
x:=a
y:=b
while y≠۰
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 حداقل ۱ هستند. به علاوه qn≥۲ چون Rn<Rn-1 در نتیجه
Rn≥۱=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.

منابع

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