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

Question

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

قبلا از طریق برهان اثبات کردمش فک کنم ، ولی الان یادم نمیاد چطور بود و یادداشتش رو هم گم کردم

Answer 1

ب.م‌.م دو عدد $a$ و $b$ را با $(a,b)$ نشان می‌دهیم.

قضیه بزو : $$\exists\ x,y \in \Bbb Z :\ (a,b)=ax+by$$

خب، $d$ را یک مقسوم علیه مشترک دلخواه $a$ و $b$ در نظر میگیریم:

$a=da_1 ~~~~~~~~ b=db_1$

$\implies (a,b)=(da_1)x+(db_1)y=d(a_1x+b_1y)\implies d |(a,b)~~~\blacksquare$

Answer 2

با روش‌های گوناگون می‌توانید این گزاره را ثابت کنید، برای نمونه با استفاه از لم بزو که کاربر دیگری در پاسخش استفاده کرده‌است یا گزارهٔ زیر.

$$d_1,d_2\mid a,b\Longrightarrow (a,b)\text{ک.م.م}\mid a,b$$

این یعنی اینکه هر دو شمارندهٔ مشترک دو عدد را بردارید، کوچکترین مضرب مشترک آن دو، یک شمارندهٔ مشترک دو عدد اولیه خواهد بود. اکنون $d$ را بزرگترین شمارندهٔ مشترک $a$ و $b$ بردارید و $e$ را یک شمارندهٔ مشترک دیگر برای $a$ و $b$، چون $d$ بزرگترین شمارندهٔ مشترک است پس $e\lneqq d$. اگر $e\mid d$ آنگاه ک.م.مِ $d$ و $e$ برابر با $d$ می‌شود و تناقضی نیست ولی اگر $e\nmid d$ آنگاه ک.م.مِ این دو یک عددِ اکیدا بزرگتر از $d$ می‌شود و چون باید شمارندهٔ مشترک برای $a$ و $b$ بماند، با بزرگترین شمارندهٔ مشترک بودن $d$ تناقض ایجاد می‌کند. پس فرض خلف باطل و از آنجا حتما باید $e\mid d$.

اما آیا گزارهٔ استفاده‌شده در بالا یا لم بزو در اثباتشان از حکم آمده در این پرسش استفاده می‌کنند یا خیر؟ اگر بلی، آنگاه این اثبات‌ها در حال ایجاد حلقه هستند. برای اینکه مطمئن شویم که از حکم استفاده نمی‌کنیم از یک مطلب دیگر استفاده می‌کنیم. قضیهٔ اساسی حساب (نظریهٔ اعداد) را به یاد آورید که هر عدد طبیعی دارای یک تجزیهٔ یکتا به شمارنده‌های اولش است. برای نمونه $12=2^2\times 3$ یا $18=2\times 3^2$. زمانی که تجزیهٔ دو عدد را داریم، خیلی ساده می‌دانیم که هر شمارندهٔ مشترک از آن دو باید به شکل $p_1^{n_1}\times\cdots\times p_r^{n_r}$ باشد که $p_i$ها عددهای اول حاضر در هر دو تجزیه هستند و $n_i$ها عددهای حسابی (طبیعی یا صفر) کوچکتر یا مساوی توان $p_i$ در هر دو. بزرگترین عددی که به این شکل می‌توان نوشت زمانی است که $n_i$ دقیقا مساوی با مینیمم توان $p_i$ در دو تجزیه باشد. این عدد بزرگترین شمارندهٔ مشترک می‌شود چون شمارندهٔ هر دو است و بزرگترین. اکنون اینکه هر شمارندهٔ مشترک دیگری آن را می‌شمارد، بدیهی می‌شود. چرا؟ چون هر شمارندهٔ مشترک دیگر به همان شکل نوشته می‌شود که فقط ممکن است برخی توان‌های انتخاب‌شده‌اش کوچکتر باشند. در واقع شمردن زمانی که تجزیه به عوامل اول را دارید یعنی عامل‌های اول یکی همگی در دیگری باشند با توان‌های کوچکتر یا مساوی.