سرفصل‌های این مبحث

نظریه اعداد

ب‌ م‌ م (قضیه بزو)

آخرین ویرایش: 20 آبان 1403

دسته‌بندی: نظریه اعداد

امتیاز:

نظر کاربران: برای نظر دادن اولین باش!

مقدمه‌ای بر قضیه بزو

قبل از بیان قضیه بزو، لازم است مقدمات زیر را بیان کنیم:

تمرین

دو عدد $12$ و $18$ را در نظر می‌گیریم. هر ترکیب خطی از این دو عدد به‌صورت $12 x + 18 y$ است.

چند ترکیب خطی از این دو عدد می‌نویسیم:

$\begin{array}{l} \{\begin{matrix} x = 1 \\ y = 1 \end{matrix}〉 12 (1) + 18 (1) = 30 \\ \{\begin{matrix} x = 3 \\ y = - 2 \end{matrix}〉 12 (3) + 18 (- 2) = 0 \end{array}$

$\begin{array}{l} \{\begin{array}{l} x = 2 \\ y = - 1 \end{array}〉 12 (2) + 18 (- 1) = 6 \\ \{\begin{array}{l} x = 3 \\ y = 2 \end{array}〉 12 (3) + 18 (2) = 72 \end{array}$

آیا تمام ترکیبات خطی فوق بر $6$ بخش پذیرند؟

$12 x + 18 y = 6 (2 x + 3 y) = 6 k$

همان‌طور که ملاحظه می‌کنید، تمام ترکیبات خطی فوق بر $6$ بخش پذیرند، که در آن $6$ بزرگ‌ترین مقسوم علیه مشترک دو عدد $12$ و $18$ می‌باشد.

کدام‌یک از ترکیبات خطی دو عدد $12$ و $18$ مساوی ب.م.م این دو عدد است؟

اما آن‌چه مورد توجه ماست آن است که یکی از ترکیبات خطی دو عدد $12$ و $18$ مساوی ب.م.م این دو عدد یعنی $6$ است که در این‌جا به ازای $\{\begin{cases} x = 2 \\ y = - 1 \end{cases}$ اتفاق افتاده است.

این مطلب به‌طور کلی برای هر دو عدد صحیح $a$ و $b$ برقرار است که در قضیه بزو آمده است.

قضیه بزو

قضیه

فرض کنید $a$ و $b$ دو عدد صحیحی باشند که دست‌کم یکی از آنها مخالف صفر است:

در این‌صورت دو عدد صحیح $r$ و $s$ می‌توان یافت به‌طوری‌که:

$a r + b s = (a, b) = d$

یعنی حداقل یک ترکیب خطی از دو عدد صحیح $a$ و $b$ مساوی ب‌‌‌م‌م آن دو عدد است:

$i f (a, b) = d \Rightarrow \exists r, s \in Z; r a + s b = d$

اثبات

مجموعه کلیه ترکیبات خطی مثبت $a$ و $b$ را در زیر مشاهده می‌کنید:

$A = \{m a + n b |m, n \in Z; m a + n b > 0\}$

این مجموعه، غیر تهی است زیرا:

$\begin{array}{l} |a| = (\pm 1) \times a + (0) \times b > 0 \Rightarrow |a| \in A \Rightarrow A \neq \emptyset \end{array}$

$|b| = (0) \times a + (\pm 1) \times b > 0 \Rightarrow |b| \in A \Rightarrow A \neq \emptyset$

$A$ زیر مجموعه $N$ یعنی $A \subset N$ می‌باشد و $N$ خوش ترتیب است، زیرا مجموعه $N$ تهی نیست و دارای عضو ابتدا است در نتیجه مجموعه $A$ دارای عضو ابتدایی مانند $d$ بوده و داریم:

$\forall d \in A \Rightarrow \exists r, s \in Z; d = r a + s b > 0$

باید ثابت کنیم که $d$ همان ب‌م‌م دو عدد $a$ و $b$ هست، یعنی در دو شرط تعریف زیر صادق است:

$\begin{array}{l} 1) d |a, d |b \\ 2) \forall c > 0; c |a \land c |b \Rightarrow c \leq d \end{array}$

برای اثبات $(1)$ داریم:

ابتدا $a$ را بر $d$ تقسیم می‌کنیم:

بنا بر قضیه تقسیم، اعداد صحیح منحصر به‌فرد $q$ و $t$ یافت می‌شود به‌قسمی‌که:

$a = d q + t; 0 \leq t \leq d$

ثابت می‌کنیم $t = 0$ است.

بر اساس برهان خلف اگر $t \neq 0$ باشد، فرض می‌کنیم $t > 0$ باشد:

$\begin{array}{l} a = d q + t \\ \Rightarrow t = a - d q; d = r a + s b \\ \Rightarrow t = a - (r a + s b) q \end{array}$

$\begin{array}{l} \Rightarrow t = a (1 - r q) + b (- s q); \{\begin{cases} 1 - r q = m^{'} \in Z \\ - s q = n^{'} \in Z \end{cases} \end{array}$

$\begin{array}{l} \Rightarrow t = m^{'} a + n^{'} b > 0 \\ \Rightarrow t > 0 \end{array}$

$t > 0$ است و این مطلب خلاف عضو ابتدا بودن $d$ است در نتیجه $\{\begin{cases} t = 0 \\ a = d q \end{cases}$ و به‌همین ترتیب ثابت می‌شود که $a |b$ .

برای اثبات $(2)$ داریم:

$\begin{array}{l} \forall c > 0, c |a, c |b \Rightarrow c \overset{?}{\leq} d \end{array}$

$\{\begin{cases} c |a \Rightarrow c |r a \\ c |b \Rightarrow c |s b \end{cases}〉 c |r a + s b \Rightarrow c |d \Rightarrow c \leq d$

نکته

1- عکس قضیه بزو در حالت کلی برقرار نمی‌باشد.

اگر عددی مانند $d$ برابر با ترکیب خطی دو عدد صحیح مانند $a$ و $b$ باشد، نمی‌توان نتیجه گرفت که $d$ ب‌م‌م دو عدد $a$ و $b$ است.

به‌عنوان نمونه:

$3 (5) + 4 (3) = 27 \Rightarrow (5, 3) = 27$

2- صورت و فرم دیگری از قضیه بزو به‌شکل زیر مطرح می‌شود:

اگر $a$ و $b$ دو عدد صحیح و حداقل یکی از آنها مخالف صفر باشد، در مجموعه زیر:

$A = \{r a + s b > 0 |r, s \in Z\}$

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

$d = \min (A) = (a, b)$

3- آن‌چه لازم است بدانیم این است که قضیه بزو فقط وجود $r$ و $s$ را بیان می‌کند، اما راه حل عملی برای پیدا کردن آنها ارائه نمی‌دهد، البته بعدا روش‌هایی برای یافتن آنها ارائه خواهیم داد.

نتایج حاصل از قضیه بزو

$i f r a + s b = 1 \Leftrightarrow (a, b) = 1$

اثبات

هرگاه ترکیب خطی دو عدد صحیح $a$ و $b$ عدد $1$ باشد، آن دو عدد نسبت به هم اولند و برعکس.

ثابت می‌کنیم:

$i f r a + s b = 1 \Rightarrow (a, b) = 1$

بنابر برهان خلف، فرض می‌کنیم $(a, b) \neq 1$ :

$(a, b) \neq 1$

$\Rightarrow \exists c > 1; (a, b) = c$

$\Rightarrow \{\begin{cases} c |a \Rightarrow c |r a \\ c |b \Rightarrow c |s b \end{cases}$

$\Rightarrow c |r a + s b$

$\Rightarrow c |1$

$\Rightarrow c \leq 1$

به یک تناقض رسیدیم پس فرض باطل است و $(a, b) = 1$ است.

ثابت می‌کنیم:

$i f (a, b) = 1 \Rightarrow r a + s b = 1$

بنابر قضیه بزو داریم:

$i f (a, b) = 1 \Rightarrow \exists r, s \in Z; r a + s b = 1$

$\{\begin{cases} (a, b) = 1 \\ a |b c \end{cases}〉 a |c$

نتیجه فوق به لم اقلیدس معروف است.

اثبات

$\{\begin{cases} a |b c \Rightarrow b c = a q \\ (a, b) = 1 \Rightarrow \exists r, s \in Z; r a + s b = 1 \end{cases}$

$\begin{array}{l} r a + s b = 1 \\ \Rightarrow c \times (r a + s b) = c \times 1 \end{array}$

$\begin{array}{l} \Rightarrow r a c + s b c = c; b c = a q \end{array}$

$\begin{array}{l} \Rightarrow r a c + s (a q) = c \end{array}$

$\begin{array}{l} \Rightarrow a (r c + s q) = c; r c + s q = q^{'} \end{array}$

$\begin{array}{l} \Rightarrow a q^{'} = c \\ \Rightarrow a |c \end{array}$

$(a, b) = d \Rightarrow (\frac{a}{d}, \frac{b}{d}) = 1$

اثبات

$\begin{array}{l} (a, b) = d \\ \Rightarrow \exists r, s \in Z; r a + s b = d \\ \Rightarrow \frac{1}{d} (r a + s b) = \frac{1}{d} (d) \\ \Rightarrow r \frac{a}{d} + s \frac{b}{d} = 1 \\ \Rightarrow (\frac{a}{d}, \frac{b}{d}) = 1 \end{array}$

تساوی $r \frac{a}{d} + s \frac{b}{d} = 1$ ترکیب خطی از $r$ و $s$ هست و ثابت می‌شود که $(r, s) = 1$ یعنی در قضیه بزو، ضرایب ترکیب خطی که $d$ را می‌سازد، همواره نسبت به‌هم اول هستند.

$i f (a, b) = 1, (a, c) = 1 \Leftrightarrow (a, b c) = 1$

اثبات

ثابت می‌کنیم:

$i f (a, b) = 1, (a, c) = 1 \Rightarrow (a, b c) = 1$

$\begin{array}{l} (a, b) = 1 \Rightarrow \exists r_{1}, s_{1} \in Z; r_{1} a + s_{1} b = 1 \end{array}$

$(a, c) = 1 \Rightarrow \exists r_{2}, s_{2} \in Z; r_{2} a + s_{2} c = 1$

$\begin{array}{l} (r_{1} a + s_{1} b) \times (r_{2} a + s_{2} c) = 1 \end{array}$

$\begin{array}{l} \Rightarrow r_{1} r_{2} a^{2} + r_{1} s_{2} a c + s_{1} r_{2} a b + s_{1} s_{2} b c = 1 \end{array}$

$\begin{array}{l} \Rightarrow a (r_{1} r_{2} a + r_{1} s_{2} c + s_{1} r_{2} b) + (s_{1} s_{2}) b c = 1; \{\begin{cases} r_{1} r_{2} a + r_{1} s_{2} c + s_{1} r_{2} b = r \\ s_{1} s_{2} = s \end{cases} \end{array}$

$\begin{array}{l} \Rightarrow r a + s b c = 1 \\ \Rightarrow (a, b c) = 1 \end{array}$

ثابت می‌کنیم:

$i f (a, b c) = 1 \Rightarrow (a, b) = 1, (a, c) = 1$

$\begin{array}{l} (a, b c) = 1 \\ \Rightarrow r a + s b c = 1 \end{array}$

$\Rightarrow \{\begin{cases} r a + (s b) c = 1 \Rightarrow (a, c) = 1 \\ r a + (s c) b = 1 \Rightarrow (a, b) = 1 \end{cases}$

فرمول فوق را به‌صورت زیر می‌توان بسط داد.

$(a, b_{1}) = 1, (a, b_{2}) = 1, ..., (a, b_{n}) = 1 \Leftrightarrow (a, b_{1} b_{2} ... b_{n}) = 1$

$a |b, a |c \Rightarrow a |(b, c)$

اثبات

هرگاه عددی دو عدد را بشمارد، آن‌گاه همواره ب‌م‌م آن دو عدد را می‌شمارد.

فرض می‌کنیم $(b, c) = d$ آن‌گاه ثابت می‌کنیم $a |d$ .

$\begin{array}{l} (b, c) = d \Rightarrow \exists r, s \in Z; r b + s c = d \end{array}$

$\{\begin{matrix} a |b \Rightarrow a |r b \\ a |c \Rightarrow a |s c \end{matrix}〉 a |r b + s c = d \Rightarrow a |d$

$a |k, b |k, (a, b) = 1 \Rightarrow a b |k$

اثبات

$\{\begin{cases} a |k \Rightarrow k = a q^{'} \\ b |k \Rightarrow k = b q^{''} \end{cases}$

$\begin{array}{l} (a, b) = 1 \\ \Rightarrow \exists r, s \in Z; r a + s b = 1 \\ \Rightarrow k (r a + s b) = k (1) \\ \Rightarrow r a k + s b k = k; \{\begin{cases} k = a q^{'} \\ k = b q^{''} \end{cases} \\ \Rightarrow r a (b q^{''}) + s b (a q^{'}) = k \end{array}$

$\begin{array}{l} \Rightarrow a b (r q^{''} + s q^{'}) = k; r q^{''} + s q^{'} = q \end{array}$

$\begin{array}{l} \Rightarrow a b (q) = k \\ \Rightarrow a b |k \end{array}$

$i f p |a b \Rightarrow p |a \lor p |b$

$p$ عددی اول است و یکی از دو عدد $a$ و $b$ را عاد می‌کند.

اثبات

اگر $p |a$ حکم ثابت است، اگر $p | a$ باید $(p, a) = 1$ آن‌گاه:

$i f p | a \Rightarrow (p, a) = 1$

بر طبق لم اقلیدس داریم:

$\Rightarrow p |a b \Rightarrow p |b$

$(a, b) = d, k \in N \Leftrightarrow (k a, k b) = k d$

اثبات

هرگاه دو عدد صحیح $a$ و $b$ را در عدد طبیعی $k$ ضرب کنیم، بزرگ‌ترین شمارنده مشترک آن دو عدد در $k$ ضرب می‌شود.

ثابت می‌کنیم:

$(a, b) = d \Rightarrow (k a, k b) = k d$

$(a, b) = d$

$\Rightarrow \{\begin{cases} 1) \{\begin{cases} d |a \\ d |b \Rightarrow k d |k b \end{cases} \\ 2) \forall x > 0; x |k a, x |k b \Rightarrow x \overset{?}{\leq} k d \end{cases}$

$\begin{array}{l} (a, b) = d \\ \Rightarrow \exists r, s \in Z; r a + s b = d \\ \Rightarrow k (r a + s b) = k (d) \\ \Rightarrow r a k + s b k = d k \end{array}$

$\{\begin{matrix} x |k a \Rightarrow x |r a k \\ x |k b \Rightarrow x |s b k \end{matrix}$

$\Rightarrow x |r a k + s b k$

$\Rightarrow x |k d \Rightarrow x \leq k d$

ثابت می‌کنیم:

$(k a, k b) = k d \Rightarrow (a, b) = d$

$(k a, k b) = k d$

$\Rightarrow \{\begin{cases} 1) \{\begin{matrix} k d |k a \Rightarrow d |a \\ k d |k b \Rightarrow d |b \end{matrix} \\ 2) c > 0, c |a, c |b \Rightarrow c \overset{?}{\leq} d \end{cases}$

$\begin{array}{l} (k a, k b) = k d \Rightarrow r (k a) + s (k b) = k d \Rightarrow r a + s b = d \end{array}$

$\{\begin{cases} c |a \Rightarrow c |r a \\ c |b \Rightarrow c |s b \end{cases}〉 c |r a + s b = d \Rightarrow c |d \Rightarrow c \leq d$

$i f (a^{n}, b^{m}) = 1 \Rightarrow (a, b) = 1; m, n \in N$

اثبات

$\begin{array}{l} i f (a^{n}, b^{m}) = 1 \\ \Rightarrow r a^{n} + s b^{m} = 1 \end{array}$

$\begin{array}{l} \Rightarrow (r a^{n - 1}) a + (s b^{m - 1}) b = 1; \{\begin{cases} r_{1} = r a^{n - 1} \\ s_{1} = s b^{m - 1} \end{cases} \end{array}$

$\begin{array}{l} \Rightarrow r_{1} a + s_{1} b = 1 \\ \Rightarrow (a, b) = 1 \end{array}$

$i f a, b, c \in Z; (a, b) = 1, c |a, d |b \Rightarrow (c, d) = 1$

اثبات

$\begin{array}{l} (a, b) = 1 \Rightarrow \exists r, s \in Z; r a + s b = 1 \end{array}$

$\{\begin{matrix} c |a \Rightarrow a = c k_{1} \\ d |b \Rightarrow b = d k_{2} \end{matrix}$

$\begin{array}{l} r a + s b = 1 \\ \Rightarrow r (c k_{1}) + s (d k_{2}) = 1 \end{array}$

$\begin{array}{l} \Rightarrow (r k_{1}) c + (s k_{2}) d = 1; \{\begin{cases} r_{1} = r k_{1} \\ s_{1} = s k_{2} \end{cases} \end{array}$

$\begin{array}{l} \Rightarrow r_{1} c + s_{1} d = 1 \\ \Rightarrow (c, d) = 1 \end{array}$

$i f a, b, c \in Z; (a, b) = 1, c |a + b \Rightarrow (a, c) = (b, c) = 1$

اثبات

$(a, b) = 1 \Rightarrow \exists r, s \in Z; r a + s b = 1$

ثابت می‌کنیم $(b, c) = 1$ :

$\begin{array}{l} c |a + b \Rightarrow a + b = c k \Rightarrow a = c k - b \end{array}$

$\begin{array}{l} r a + s b = 1 \\ \Rightarrow r (c k - b) + s b = 1 \end{array}$

$\begin{array}{l} \Rightarrow (r k) c + (s - r) b = 1; \{\begin{cases} r_{1} = r k \\ s_{1} = s - r \end{cases} \end{array}$

$\begin{array}{l} \Rightarrow r_{1} c + s_{1} b = 1 \\ \Rightarrow (c, b) = 1 \end{array}$

ثابت می‌کنیم $(a, c) = 1$ :

$\begin{array}{l} c |a + b \Rightarrow a + b = c k \Rightarrow b = c k - a \end{array}$

$\begin{array}{l} r a + s b = 1 \\ \Rightarrow r a + s (c k - a) = 1 \end{array}$

$\begin{array}{l} \Rightarrow (r - s) a + (s k) c = 1; \{\begin{cases} r_{1} = r - s \\ s_{1} = s k \end{cases} \end{array}$

$\begin{array}{l} \Rightarrow r_{1} a + s_{1} c = 1 \\ \Rightarrow (a, c) = 1 \end{array}$

قضیه

هر ترکیب خطی $a$ و $b$ مانند $a x + b y = t$ بر ب‌م‌م دو عدد $a$ و $b$ یعنی $(a, b) = d$ بخش پذیر است:

$\begin{array}{l} a x + b y = t \end{array}$

$d = (a, b) \Rightarrow \{\begin{matrix} d |a \Rightarrow d |a x \\ d |b \Rightarrow d |b y \end{matrix}〉 d |a x + b y$

$\Rightarrow d |t$

دریافت مثال

دریافت فایل PDF

تست‌های این مبحث

تست شماره 1

کنکور ریاضی اردیبهشت 1403

اگر کوچکترین عضو مثبت مجموعه زیر باشد:

$\{407 r + 592 s| r, s \in Z\}$

مجموع ارقام m کدام است؟

$2$
$7$
$10$
$11$

مشاهده پاسخ تست

خرید پاسخ‌ها

ب‌م‌م (قضیه بزو)

2,000تومان

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

نظریه اعداد

ب‌ م‌ م (قضیه بزو)

مقدمه‌ای بر قضیه بزو

قضیه بزو

نتایج حاصل از قضیه بزو

تست‌های این مبحث

nenomatica

مجموعه قوانین

دسترسی سریع

آیا می‌خواهید فیلم معرفی را مشاهده نمایید؟