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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

الگوریتم اقلیدس، روشی موسوم به روش نردبانی یا تقسیمات متوالی برای یافتن بزرگترین مقسوم علیه مشترک دو عدد است که در ادامه، با مثالی آن را شرح می‌دهیم.
مثال: برای محاسبهٔ عدد بزرگتر یعنی 846 را بر 204 تقسیم می‌کنیم و سپس 204 را بر باقی ماندهٔ تقسیم قبل تقسیم می‌کنیم و این عمل را تا جایی که باقی مانده صفر شود ادامه می‌دهیم، آخرین باقی‌مانده غیرصفر، بزرگترین مقسوم علیه مشترک دو عدد مزبور است.

بنابرین .

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

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

لم: اگر آن‌گاه

اثبات: فرض می‌کنیم و . پس

شبه کد الگوریتم اقلیدسی:
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.

منابع[ویرایش]