بزرگترین مقسوم علیه مشترک

[nafise sadeghi]

مقسوم علیه های مشترک میان دو عددa وb، اعدادی هستند که بتوانند هم a و هم b را بشمارند.
به عبارت ریاضی: c مقسوم علیه مشترک دو عدد a و b است هرگاه c|a و c|b .
مثلا مقسوم علیه های دو عدد 15 و30 را داریم:


مقسوم علیه‌های 15 = {1,3,5,15}
مقسوم علیه‌های 35 = {1,5,7,35}
مقسوم علیه های مشترک میان این دو عدد عبارتند از:
مقسوم علیه های مشترک 15 و 35 = {1,5}
تعریف

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

به عبارت ریاضی: d بزرگترین مقسوم علیه a و b است هرگاه d|a و d|b و اگر c|a و c|b وآنگاه d>c .

بزرگترین مقسوم علیه مشترک در مثال بالا ، 5 است. که آن را به این صورت نمایش می دهند:


(15,35)=5

بزرگترین مقسوم علیه میان دو عدد را به اختصار به صورت ب.م.م می نویسند.
اگر ب.م.م دو عدد یک باشند ، آنگاه این دو عدد نسبت به هم اولند.مثلا دو عدد 13 و 8 هیچ مقسوم علیه مشترکی جز یک ندارند.

قضایای مربوط:

قضیه 1. این قضیه به قضیه بزو نیز معروف است. مطابق این قضیه مجموعه زیر مجموعه ای از مقسوم علیه های مشترک میان دو عدد a وb هستند:
{S={m,n ε Z| am+bn>0
به این ترتیب می توان ثابت کرد که مینیمم این مجموعه همان بزرگترین مقسوم علیهaوb است.
برهان:در {S={m,n ε Z| am+bn>0 داریم http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/ef65f949dddf5647905956f4e1051511.png و همچنین S ناتهی است چون: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/c525a9b12659336aba5cc49ebda67a1f.png
به این ترتیب اگر a>0 باشد:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/7351c41110bca218146cd51b2d48d41a.png
و اگر a<0 باشد:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/55a03b1a703d2a1c21b529c5bac44fe7.png
و این نتیجه می دهد S ناتهی است.
لذا بنا بر اصل خوشترتیبی S دارای عضو مینیمم است چون d. یعنی: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d001fa1f52e5cd4632ca33d8d0a822f4.png
پس داریم:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/76ea99218e63c9c9c618e928530e867d.png
حال نشان می دهیم d برابر بزرگترین مقسوم علیه مشترک aوb است یعنی:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/9b81ae74c43f59f7723423d6355a784b.png
برای این کار باید نشان دهیم:
1) http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/adf96a1b3da5940b45d1789f89a732f6.png
برهان: a را بر d تقسیم می کنیم: برطبق قضیه الگوریتم تقسیم: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/52f9c6981eb1daa7011a0035c8c25e41.png
حال نشان می دهیم که r=0 و از آنجا نتیجه میگیریم که d|a. به برهان خلف اگر r مخالف صفر باشد پس r>0 به این ترتیب: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/ceae6f9231e04541121f681eeaae1958.png
و از طرفی r<d که این با مینیمم بودن d در تناقض است پس فرض خلف باطل و r=0 پس d|a. به طریق مشابه d|b.
2) باید در مرحله دوم نشان دهیم:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/2afed6bb3075155b2dedb3c9eb31fe3a.png
برهان: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/a29173ad1fe4191428d638acd5f6efee.png
پس به این ترتیب ثابت شد: مینیمم مجموعه S یعنی d همان بزرگترین مقسوم علیه مشترک aوb است.

قضیه 2. d بزرگترین مقسوم علیه مشترک دو عدد a و b است اگر و تنها اگر :
الف) d|a و d|b و ب) اگر c|a و c|b آنگاه c|d.

قضیه 3.اگر a|bc و a,b نسبت به هم اول باشند، آنگاه a|c . این قضیه به لِم اقلیدس نیز معروف است.
قضیه 4. اگر P|ab (عدد P یک عدد اول (http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%D8%B9%D8%AF%D8%AF+%D8%A7%D9%88%D9% 84) است)، آنگاه P|a یا P|b .
قضیه 5. اگر c کوچکترین مضرب مشترک و d بزرگترین مقسوم علیه مشترک دو عدد a وb باشد آنگاه داریم:
d*c=ab

[nafise sadeghi]

لم های مربوط:

لم 1. بر اساس اصول بنیادی حساب، هر عدد مرکب را می توان به صورت حاصلضرب اعداد اول تجزیه کرد. ب.م.م میان دو عدد برابر با حاصلضرب اعداد اول مشترک میان آن دو عدد به توان عدد کمتر.
لم 2. ب.م.م دو عدد، هر مقسوم علیه مشترک میان دو عدد را می شمارد:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/652497ed7e7e0323aa2b71d8d45cd409.png
لم 3. اگر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/438ab654313466f6e492a0d5ba6a0ab5.png آنگاه : عدد k موجود است به قسمی که http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/e05b20fa039335b7cf9e7ecedeb33841.png
لم 4. اگر
a|c & b|c , (a,b)=1 ===> ab|c


لم 5. اگر http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/f0f167fa2858ba37081a6d30fff771ed.pngآنگاه
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/78885352e077adc5946c34dd2ad89ba3.png

مثال :


مثال1. اگر n عددی فرد باشد ثابت کنید که 24حاصلضرب سه عدد متوالی قبل و بعد از n را می شمرد:
24|(n-1)n(n+1)
جواب:
عدد سه، حاصلضرب سه عدد متوالی را می شمرد( اثبات آن به عهده خواننده است. راهنمایی : هر عددی را می توان به صورت :
A=3q+r 0≤r<3)
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/22f59dff7b7fe2b2e601a7ea484dce38.png
باید ثابت کنیم که حاصلضرب دو عدد زوج متوالی بر 8 تقسیمپذیر است:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/a91ca95f75bd3dc913ab854211159352.png :

آنگاه: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/d044e23bc6baed708ea46063758b92b7.png
حاصلضرب دو عدد متوالی همواره بر 2 بخش پزیر است.پس:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/3db88f96a1743eab36f2a352b1828188.png


آنگاه:http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/326a297a806eb23678f8bca8c34e8814.png

آنگاه: http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/85d7287367a81f43b1d32a4a3c5af64e.png

http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/bb73c74a2556b09eeac6a622a8c906f3.png آنگاه:


طبق لم 4 داریم:
http://daneshnameh.roshd.ir/mavara/img/daneshnameh/math/8cf9c401f3a34176e4946409af46cf55.png