فرض کنیم a,b دو عدد صحیح باشند که حداقل یکی از آن ها ناصفر باشد. عدد صحیح d را مقسوم علیه مشترک دو عدد a, b گویند هرگاه a و b هر دو بر d بخشپذیر باشند.
در میان عوامل مشترک دو عدد a,b، بزرگترین آن ها را بزرگترین مقسوم علیه مشترک (Greatest common factor) یا به اختصار ب.م.م (GCF) گوییم و با نماد (a,b) یا GCF(a,b) نمایش می دهیم.
همواره a,b)≥1) حالت تساوی زمانی اتفاق می افتد که دو عدد a,b هیچ عامل مشترکی نداشته باشند.
(a,b) بر هر عامل مشترک a, b بخشپذیر است.
اگر k عددی مثبت باشد آنگاه (ka,kb)=k(a,b).
اگر a,bc)=1) آنگاه a,b)=1) و a,c)=1)
برعکس عبارت بالا هم برقرار است. یعنی اگر a,b و همینطور a,c عامل مشترکی نداشته باشند آنگاه a و bc هم عامل مشترکی ندارند.
همواره داریم: (a,b,c)=((a,b),c)
دو عدد پشت سر هم عامل مشترکی ندارند: (n,n+1)=1
دو عدد فرد پشت سر هم عامل مشترکی ندارند یعنی اگر n فرد باشد آنگاه (n,n+2)=1
دو عدد زوج پشت سر هم فقط عامل مشترک 2 دارند یعنی اگر n طوج باشد آنگاه (n,n+2)=2
اگر b عاملی از a باشد آنگاه (a,b)=b پس همیشه (n,n)=n و (1,n)=1.
اگر a,b اعداد اول متمایزی باشند آنگاه (a,b)=1. توجه کنید که عکس این گزاره درست نیست. مثلا 10 و 21 اول نیستند اما عامل مشترک هم ندارند.
یکی از راه های بدست آوردن ب.م.م دو عدد اینست که تمام مقسوم علیه های دو عدد را نوشته و بزرگترین مقسوم علیه مشترک آنها را بیابیم. اما این روش برای اعداد بزرگتر بسیار وقت گیر است.
روش بهتر آنست که هر دو عدد را به صورت حاصلضرب عوامل اول تجزیه کنیم. ب.م.م برابر است با حاصلضرب عوامل اول مشترک که دارای توان کمتر هستند.
مثلا برا ی دو عدد 180 و 840 داریم:
180=22×32×5, 840=23×3×5×7
عوامل اول مشترک عبارتند از 2و 3و 5.چون باید توان کمتر را انتخاب کنیم پس 22و 3و 5 را در هم ضرب میکنیم. در نتیجه:
(180,840)=22×3×5=60
مثال هایی از GRE:
The length and width of a rectangular yard are respectively 18 and 12 meters. What is the area of the greatest square-shape tiles that we can fill the yard by?(the side of the tiles is less than 1 meter)
می خواهیم یک حیاط به ابعاد 18 در 12 متر را کاشی کنیم. برای این منظور مساحت حیاط باید بر مساحت کاشی های مربعی بخشپذیر باشد یا به عبارت دیگر ابعاد حیاط باید بر ابعاد کاشی ها بخشپذیر باشد. اما چون میخواهیم بزرگترین کاشی مربعی را برای این کار بیابیم کافیست بزرگترین مقسوم علیه مشترک 18 و 12 را بیابیم. چون ضلع کاشی های مربعی شکل کمتر از یک متر است پس ابعاد را تبدیل به سانتیمتر می کنیم. پس ابعاد حیاط 180 و 120 سانتیمتر است.
120=23×3×5, 180=22×32×5→ (120,180)=22×3×5=60
بنابراین ابعاد کاشی باید 60 در 60 باشد.
If (a,b)=b and (b,c)=c and (c,d)=d, Then what is (abcd,(b,d))?
چون (b,c)=c بنابراین c عاملی از b است و به همین ترتیب d نیز عاملی از c است. پس d عاملی از b نیز هست، در نتیجه (b,d)=d از اینرو
(abcd,(b,d))=(abcd, d)=d
جواب آخر از اینجا نتیجه می شود که d عاملی از abcd است.
the greatest common factor of 12x and 35y is 5y.
x and y are positive integers.
Quantity A Quantity B
the remainder when 12x is divided by 10 the greatest common factor of x and y
12x, 35y)=5y) بنابراین 12x باید بر 5y بخشپذیر باشد پس x باید عامل 5 داشته باشد در نتیجه 12x بر 10 بخشپذیر است.
پس مقدار Quantity A برابر با 0 است. از طرفی ب.م.م دو عدد همواره حداقل 1 است پس Quantity B حداقل 1 است.
در نتیجه جواب گزینه B است.