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

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

بزرگترین مقسوم علیه مشترک دو عدد 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^{\prime }$. پس

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

منابع

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