الگوریتم اقلیدس: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
برچسب تمیزکاری، برچسب: استفادهٔ زیاد از تگ یا الگوی سرخط |
←اثبات الگوریتم اقلیدس: اصلاح نویسه، اصلاح سجاوندی برچسب‌ها: استفادهٔ زیاد از تگ یا الگوی سرخط افزودن فضای خالی زیاد |
||
خط ۹:
== اثبات الگوریتم اقلیدس ==
برای این که ثابت کنیم چرا با الگوریتم فوق ب.م. م به دست می‌آید به لم زیر توجه کنید:{{سخ}}
{{
'''لم:''' اگر <math>a = bq + r</math> آنگاه <math>(a , b) = (b , r)</math>
{{پایان وسط‌چین}}
'''اثبات:'''
[[پرونده:Proof - Euclidean Algorithm.png|600px|وسط]]
خط ۲۴:
{{سرخط}}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.
== منابع ==
| |||