ب‌ م‌ م (الگوریتم اقلیدسی)

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 03 شهریور 1400
دسته‌بندی: نظریه اعداد
امتیاز:
بازدید: 34 مرتبه

تاکنون قضایایی را در مورد بزرگ‌ترین مقسوم علیه مشترک دو عدد بیان کرده‌ایم لیکن  تا به‌حال یک راه حل برای به‌دست آوردن ب‌م‌م دو عدد ارائه نداده‌ایم، اینک می‌خواهیم الگوریتمی برای یافتن بزرگ‌ترین شمارنده مشترک دو عدد به‌دست آوریم.

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

قضیه

اگر a=bq+r باشد، آن‌گاه a,b=b,r.

اثبات

قضیه بیان می‌دارد که اگر a را بر b تقسیم کنیم و q خارج قسمت و r باقیمانده تقسیم باشد، در این‌صورت بزرگ‌ترین مقسوم علیه مشترک بین مقسوم و مقسوم علیه برابر است با بزرگ‌ترین مقسوم علیه مشترک بین مقسوم علیه و باقیمانده. 

برای اثبات فرض می‌کنیم a,b=d1b,r=d2 باشد و ثابت می‌کنیم d1=d2:

a=bq+rr=abq

1     :    a,b=d1d1ad1bd1bq  d1abqd1rd1|rd1|bd1b,rd1d2d1d2


2     :    b,r=d2d2bd2bqd2r  d2bq+rd2ad2ad2bd2a,bd2d1d2d1    


از 1 و 2 نتیجه می‌شود:

d1=d2

نکته

صورت دیگر الگوریتم اقلیدسی به‌شکل زیر است:

فرض کنید a و b دو عدد طبیعی باشند، برای یافتن a,b تقسیمات زیر را انجام می‌دهیم:

a=bq+r1    ;    0<r1<bb=r1q2+r2    ;    0<r2<r1r1=r2q3+r3    ;    0<r3<r2                    rk2=rk1qk+rk    ;    0<rk<rk1rk1=rkqk+1+0

در این‌صورت rk آخرین باقیمانده غیر صفر همان ب‌م‌م a و b است.   

الگوریتم اقلیدسی - پیمان گردلو

تمرین

بزرگ‌ترين شمارنده مشترک (ب م م ) جفت اعداد زير را بيابيد:

8,6

8=6×1+26=2×3+0


آخرين باقيمانده غير صفر، (ب م م) می‌باشد:

8,6=2

629,357

629=357×1+272357=272×1+85272=85×3+1785=17×5+0


آخرين باقيمانده غير صفر، (ب م م) می‌باشد:

629,357=17


توجه کنید:

629,357=357,272=272,85=85,17=17

1999,1379

1999=1379×1+6201379=620×2+139620=139×4+64139=64×2+1164=11×5+911=9×1+29=2×4+12=1×2+0  


آخرين باقيمانده غير صفر، (ب م م) می‌باشد:

1999,1379=1

1404,1014

1404=1014×1+3901014=390×2+234390=234×1+156234=156×1+78156=78×2+0


آخرين باقيمانده غير صفر، (ب م م) می‌باشد:

1404,1014=78


توجه کنید:

1404,1014=1014,390=390,234=.....=156,78=78

تمرین

بزرگ‌ترين شمارنده مشترک دو عدد، 14 است و در موقع تعيين (ب م م) به‌وسيله قاعده تقسيمات متوالی، سلسله خارج قسمت‌ها، عبارت است از 4,2,8,3 مطلوب است تعيين آن دو عدد. 

فرض كنيد a,b دو عدد مطلوب باشند و a>b بنابراين:


الگوریتم اقلیدسی - پیمان گردلو


با توجه مطلب فوق، داریم:

a=3b+r1b=8r1+r2r1=2r2+r3r2=4r3


می‌دانيم آخرين باقيمانده غير صفر همان (ب م م) دو عدد است، پس r3=14 است و خواهيم داشت:

r3=14r2=4r3r2=414=56r1=2r2+r3r1=256+14=126b=8r1+r2  b=8126+56=1064a=3b+r1  a=31064+126=3318

هرگاه بزرگ‌ترين شمارنده دو عدد طبيعی a, b برابر 5 باشد و در تعيين اين بزرگ‌ترين شمارنده مشترک به كمک تقسيمات متوالی، سلسله خارج قسمت به‌ترتيب 2,3,4 باشد، دو عدد a, b را بیابید.  

a,b=5a=4b+rb=3r+r1r=2r1


می‌دانيم آخرين باقيمانده غير صفر همان (ب م م)  دو عدد است پس r1=5 است و خواهيم داشت: 

r1=a,b=5r=r=2r1=25=10b=3r+r1=310+5=35a=4b+r=435+10=150

برای ارسال نظر وارد سایت شوید