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

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

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

Euclidean Algorithm

بنابرین .

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

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

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

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

Proof - Euclidean Algorithm.png

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

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

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