ب.م.م و ک.م.م و الگوریتم اقلیدس
اهداف یادگیری
- بزرگ‌ترین مقسوم‌علیه مشترک و کوچک‌ترین مضرب مشترک را تعریف کنید.
- آن‌ها را از تجزیه به عامل‌های اول محاسبه کنید.
- با الگوریتم اقلیدس و بدون تجزیه، ب.م.م را بیابید.
- با ب.م.م کسرها را ساده کنید.
مقسوم‌علیه‌ها و مضرب‌های مشترک
بزرگ‌ترین مقسوم‌علیه مشترک (ب.م.م) دو عدد صحیح \(a,b\) که هر دو صفر نباشند، با \(\gcd(a,b)\) نشان داده می‌شود و بزرگ‌ترین عدد صحیح مثبتی است که هر دو را می‌شمارد. دو عدد صحیح نسبت به هم اول هستند اگر \(\gcd(a,b)=1\).
کوچک‌ترین مضرب مشترک (ک.م.م) دو عدد صحیح ناصفر، با \(\operatorname{lcm}(a,b)\) نشان داده می‌شود و کوچک‌ترین عدد صحیح مثبتی است که بر هر دو بخش‌پذیر باشد.
مقسوم‌علیه‌های ۱۲: \(1,2,3,4,6,12\). مقسوم‌علیه‌های ۱۸: \(1,2,3,6,9,18\). مقسوم‌علیه‌های مشترک \(1,2,3,6\) است، پس \(\gcd(12,18)=6\).
مضرب‌های ۴: ۴، ۸، ۱۲، … و مضرب‌های ۶: ۶، ۱۲، …، پس \(\operatorname{lcm}(4,6)=12\).
استفاده از تجزیه به عامل‌های اول
هر دو عدد را به عامل‌های اول تجزیه کنید. در ب.م.م از هر عدد اول، توان کوچک‌تر و در ک.م.م توان بزرگ‌تر را برمی‌داریم.
\(\gcd(360,84)\) و \(\operatorname{lcm}(360,84)\) را بیابید.
\[360=2^3\cdot 3^2\cdot 5,\qquad 84=2^2\cdot 3\cdot 7\]
\[\gcd=2^2\cdot 3=12,\qquad \operatorname{lcm}=2^3\cdot 3^2\cdot 5\cdot 7=2520\]
برای اعداد صحیح مثبت \(a,b\): \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab\).
نمایش اثبات
برای هر عدد اول، اگر توان آن در \(a\) و \(b\) برابر \(x\) و \(y\) باشد، ب.م.م توان \(\min(x,y)\) و ک.م.م توان \(\max(x,y)\) را دارد. چون \(\min(x,y)+\max(x,y)=x+y\)، حاصل‌ضرب ب.م.م و ک.م.م در توان هر عدد اول با \(ab\) برابر است. ∎
\(12\cdot 2520=30240=360\cdot 84\)
الگوریتم اقلیدس
برای اعداد صحیح \(a\) و \(b>0\) اعداد صحیح یکتای \(q\) و \(r\) وجود دارند که \(a=qb+r\) و \(0\le r<b\).
اگر \(a=qb+r\)، آنگاه \(\gcd(a,b)=\gcd(b,r)\).
نمایش اثبات
هر مقسوم‌علیه مشترک \(a\) و \(b\)، عدد \(r=a-qb\) را هم می‌شمارد و پس مقسوم‌علیه مشترک \(b\) و \(r\) است. برعکس، هر مقسوم‌علیه مشترک \(b\) و \(r\)، عدد \(a=qb+r\) را می‌شمارد. دو جفت مقسوم‌علیه‌های مشترک یکسان و در نتیجه بزرگ‌ترین مقسوم‌علیه مشترک یکسان دارند. ∎
تقسیم را تکرار کنید و هر بار \((a,b)\) را با \((b,r)\) جایگزین کنید تا باقی‌مانده ۰ شود. آخرین باقی‌مانده ناصفر، ب.م.م است. با لغزنده‌ها امتحان کنید:
\(\gcd(252,105)\) را بیابید.
\[252=2\cdot 105+42,\qquad 105=2\cdot 42+21,\qquad 42=2\cdot 21+0\]
آخرین باقی‌مانده ناصفر ۲۱ است، پس \(\gcd(252,105)=21\).
باقی‌مانده‌ها به‌سرعت کوچک می‌شوند: حتی برای اعداد ۱۰۰ رقمی این الگوریتم فقط چند صد گام لازم دارد. این الگوریتم در کتاب اصول اقلیدس، نوشته‌شده در حدود ۳۰۰ سال پیش از میلاد، آمده است.
ساده کردن کسرها
کسر \(\frac{252}{105}\) را ساده کنید.
چون \(\gcd(252,105)=21\)، صورت و مخرج را بر ۲۱ تقسیم می‌کنیم: \(\frac{252}{105}=\frac{12}{5}\).
کسر \(\frac ab\) دقیقاً وقتی ساده‌شده است که \(\gcd(a,b)=1\). این همان ایدهٔ پشت کسر ساده‌شده در درس اعداد گویا است.
تمرین‌ها
با تجزیه به عامل‌های اول، \(\gcd(84,126)\) و \(\operatorname{lcm}(84,126)\) را بیابید.
نمایش پاسخ
\(84=2^2\cdot 3\cdot 7\) و \(126=2\cdot 3^2\cdot 7\). پس \(\gcd=2\cdot 3\cdot 7=42\) و \(\operatorname{lcm}=2^2\cdot 3^2\cdot 7=252\).
با الگوریتم اقلیدس \(\gcd(1071,462)\) را بیابید.
نمایش پاسخ
\(1071=2\cdot 462+147\)، \(462=3\cdot 147+21\)، \(147=7\cdot 21+0\). پس \(\gcd(1071,462)=21\).
دو زنگ به‌ترتیب هر ۱۲ و هر ۱۸ دقیقه به صدا درمی‌آیند و ظهر با هم زنگ می‌زنند. بار بعد کی با هم زنگ می‌زنند؟
نمایش پاسخ
نخستین زمان مشترک بعدی، ک.م.م است: \(\operatorname{lcm}(12,18)=36\)، یعنی ۳۶ دقیقه بعد.
ثابت کنید دو عدد صحیح متوالی \(n\) و \(n+1\) نسبت به هم اول‌اند.
نمایش پاسخ
هر مقسوم‌علیه مشترک \(n\) و \(n+1\)، تفاضل آن‌ها یعنی \((n+1)-n=1\) را می‌شمارد، پس ب.م.م برابر ۱ است.
کسر \(\frac{168}{294}\) را ساده کنید.
نمایش پاسخ
\(294=1\cdot 168+126\)، \(168=1\cdot 126+42\)، \(126=3\cdot 42+0\)، پس \(\gcd=42\) و \(\frac{168}{294}=\frac{4}{7}\).
دو عدد صحیح مثبت بیابید که ب.م.م آن‌ها ۶ و ک.م.م آن‌ها ۳۶ باشد.
نمایش پاسخ
حاصل‌ضرب آن‌ها \(6\cdot 36=216\) است. ۱۲ و ۱۸ را امتحان کنید: \(\gcd(12,18)=6\)، \(\operatorname{lcm}(12,18)=36\) و \(12\cdot 18=216\). (جفت ۶ و ۳۶ هم جواب است.)
جمع‌بندی
- ب.م.م بزرگ‌ترین مقسوم‌علیه مشترک و ک.م.م کوچک‌ترین مضرب مشترک است؛ هر دو از تجزیه به عامل‌های اول به دست می‌آیند.
- حاصل‌ضرب \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)\) برابر \(ab\) است.
- الگوریتم اقلیدس با تقسیم‌های متوالی و بدون تجزیه، ب.م.م را پیدا می‌کند.
- تقسیم صورت و مخرج بر ب.م.م، کسر را ساده می‌کند.