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

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

بزرگترین مقسوم علیه مشترک دو عدد a و b را بصورت $gcd(a,b)$ نشان می دهند. برای محاسبه $gcd(a,b)$ عدد بزرگتر را بر عدد کوچکتر تقسیم می کنیم, اگر باقی مانده صفر بود پس عدد کوچکتر همان ب.م.م دو عدد است وگرنه عدد کوچکتر را بر باقی مانده تقسیم قبلی تقسیم می کنیم و این فرایند را تا جایی پیش می بریم تا به باقی مانده صفر برسیم.
مثال: برای محاسبهٔ $gcd(18,12)$ عدد بزرگتر یعنی 18 را بر 12 تقسیم می‌کنیم و سپس 12 را بر باقی ماندهٔ تقسیم قبل (باقی مانده ۱۸ تقسیم بر ۱۲ مساوی با 6 است) تقسیم می کنیم، ۱۲ تقسیم بر ۶ باقی مانده صفر دارد بنابراین $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≠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.

منابع

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