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

نظریه اعداد

ب‌ م‌ م (تعریف و قضایا)

آخرین ویرایش: 15 تیر 1403

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

امتیاز:

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

مقسوم علیه مشترک دو عدد

عدد صحیح $c$ را مقسوم علیه مشترک یا شمارنده مشترک دو عدد $a$ و $b$ می‌نامیم، در صورتی‌که هر دو را بشمارد، یعنی $c | a$ و $c | b$ .

به‌عنوان نمونه $3$ یک شمارنده مشترک برای دو عدد $6$ و $- 9$ است، زیرا:

$3 | 6, 3 | - 9$

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

دو عدد $12$ و $18$ را در نظر می‌گیریم:

مجموعه مقسوم علیه مشترک مثبت دو عدد $12$ و $18$ به‌صورت زیر نشان می‌دهیم:

$\{\begin{cases} D_{1} = \{1, 2, 3, 4, 6, 12\} \\ D_{2} = \{1, 2, 3, 6, 9, 18\} \end{cases}$

اشتراک دو مجموعه فوق، مجموعه مقسوم علیه مشترک مثبت دو عدد $12$ و $18$ عبارتند از:

$D_{1} \cap D_{2} = \{1, 2, 3, 6\}$

بزرگ‌ترین عضو این مجموعه یعنی $6$ را به‌عنوان بزرگ‌ترین مقسوم علیه مشترک دو عدد $12$ و $18$ تعریف می‌کنیم.

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

تعریف

اگر $a$ و $b$ دو عدد صحیح دل‌خواهی باشند که دست کم یکی از آنها مخالف صفر باشد، در این‌صورت بزرگ‌ترین مقسوم علیه مشترک (ب‌م‌م) $a$ و $b$ عددی مثبت است مانند $d$ و با نماد $d = (a, b)$ نشان می‌دهند، به‌طوری‌که:

$d = (a, b) \Leftrightarrow \{\begin{cases} 1) d |a, d |b \\ 2) \forall c > 0; c |a, c |b \Rightarrow c \leq d \end{cases}$

هر مقسوم علیه مشترک $a$ و $b$ از $d$ کوچک‌تر است.

شرط $(1)$ مقسوم علیه مشترک بودن را برای $d$ تامین می‌کند.
شرط $(2)$ نشان می‌دهد که $d$ از هر مقسوم علیه مشترک دل‌خواهی مانند $c$ بزرگ‌تر است.

به‌عنوان نمونه داریم:

$\begin{array}{l} (3, - 6) = 3 \end{array}$

$\begin{array}{l} (4, 9) = 1 \end{array}$

$\begin{array}{l} (6, 8) = 2 \end{array}$

$\begin{array}{l} (- 8, - 12) = 4 \end{array}$

$(- 6, 18) = 6$

نکته

1- توجه داشته باشید که اگر $a$ و $b$ هر دو صفر باشد، در این‌صورت مجموعه مقسوم علیه های مشترک مثبت $a$ و $b$ مجموعه اعداد طبیعی $N$ است.

اما $N$ از راست بی‌کران است و بزرگ‌ترین عضوی ندارد، لذا در حالتی که $a$ و $b$ هر دو صفر باشند، بزرگ‌ترین مقسوم علیه (بزرگترین شمارنده مشترک) وجود ندارد.

2- اگر برای دو عدد صحیح $a$ و $b$ داشته باشیم $(a, b) = 1$ در این‌صورت می‌گوییم $a$ و $b$ نسبت به‌هم اول (متباین) هستند.

به‌عنوان نمونه داریم:

$\begin{array}{l} (5, 6) = 1 \\ (3, 5) = 1 \\ (4, 9) = 1 \end{array}$

تمرین

اگر $a$ یک عدد صحیح مخالف صفر باشد، نشان دهید:

$(a, 0) = |a|$

مجموعه شمارنده های مثبت $a$ :

$A = \{1, ...., |a|\}$

مجموعه شمارنده های مثبت صفر:

$N = \{1, 2, 3, ....\}$

مجموعه شمارنده های مشترک مثبت صفر و $a$ :

$\begin{array}{l} \{1, ..., |a|\} = A \\ (a, 0) = |a| \end{array}$

تمرین

اگر $D (a)$ و $D (b)$ به‌ترتیب مجموعه شمارنده های $a$ و $b$ باشند، نشان دهید:

$i f a | b \Rightarrow D (a) \subset D (b)$

$x$ یک شمارنده $a$ است:

$x \in D (a) \Rightarrow x |a, a |b \Rightarrow x |b \Rightarrow x \in D (b)$

تمرین

ثابت کنید:

هر دو عدد صحیح و متوالی نسبت به هم اولند.

$\begin{array}{l} (m, m + 1) = d \\ \Rightarrow \{\begin{cases} d| m \\ d| m + 1 \end{cases} \\ \Rightarrow d| (m + 1) - (m) \end{array}$

$\begin{array}{l} \Rightarrow d| 1 \\ \Rightarrow d = 1; d > 0 \end{array}$

هر دو عدد صحیح و فرد متوالی نسبت به هم اولند.

$\begin{array}{l} (2 m + 1, 2 m + 3) = d \\ \Rightarrow \{\begin{cases} d| 2 m + 1 \\ d| 2 m + 3 \end{cases} \\ \Rightarrow d| (2 m + 3) - (2 m + 1) \end{array}$

$\begin{array}{l} \Rightarrow d| 2 \\ \Rightarrow \{\begin{cases} d = 1 \\ d \neq 2 \end{cases} \end{array}$

تمرین

اگر $p \neq q$ و $p, q$ هر دو عدد اول باشند، ثابت کنید:

$(p, q) = 1$

اثبات به روش برهان خلف:

فرض کنیم $(p, q) = d$ و $d \neq 1$ باشد، بنابراین طبق تعریف بزرگ ترین مقسوم علیه مشترک دو عدد داریم:

$(p, q) = d \Rightarrow \{\begin{cases} d| p \\ d| q \end{cases}$

در تعریف فوق $p, q$ و اعدادی اول هستند و هم‌چنین، $d \neq 1$ پس داریم:

$\{\begin{cases} d| p \\ d| q \end{cases}〉 \{\begin{cases} d = p \\ d = q \end{cases}〉 p = q$

$p = q$ با فرض ما در تناقض است، در نتیجه فرض خلف باطل است و حکم اثبات می‌گردد.

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

قضیه

همواره بزرگ‌ترین مقسوم علیه مشترک دو عدد صحیح که حداقل یکی از آنها مخالف صفر باشد، موجود است.

اثبات

اگر دو عدد $a$ و $b$ مفروض باشند و مجموعه همه مقسوم علیه های مشترک $a$ و $b$ را $A$ بنامیم.

فرض می‌کنیم:

$A = \{c > 0 |c | a, c | b\}$

واضح است که $A \subseteq Ζ$ و $A \neq O$ زیرا حداقل $1 \in A$ .

از طرف دیگر فرض کنیم $a < b$ در این‌صورت $|a|$ یک کران بالا برای مجموعه $A$ است زیرا عددی بزرگ‌تر $|a|$ نمی‌توان یافت که $a$ را عاد کند.

پس طبق قضیه‌های بیان شده، هر زیرمجموعه ناتهی که از بالا کراندار باشد، دارای عضو انتها است، بنابراین مجموعه $A$ دارای انتها می‌باشد که این عضو همان عضو انتهای بزرگ‌ترین مقسوم علیه مشترک است.

قضیه

$\forall a, b \in Z; a \neq 0, a | b \Rightarrow (a, b) = |a|$

اثبات

باید ثابت کنیم که $|a|$ هر دو شرط ( ب‌م‌م) را دارد:

$|a|$ یک مقسوم علیه مشترک $a$ و $b$ است:

$1) \{\begin{cases} a | a, - a | a \Rightarrow | a | |a \\ a | b, - a | b \Rightarrow | a | |b \end{cases}$

$2) i f c > 0, c | a, c | b$

$|a|$ از هر مقسوم علیه مشترک $a$ و $b$ بزرگ‌تر است:

$c | a \Rightarrow |c| \leq |a| \Rightarrow c \leq | a |; c > 0$

قضیه

$i f (a, b) = 1 \Leftrightarrow (k a \pm b, a) = 1; (k \in Ζ)$

اثبات

فرض کنیم $(k a \pm b, a) = d$ ، ثابت می‌کنیم $d = 1$ است.

$\begin{array}{l} (k a \pm b, a) = d \end{array}$

$1) \{\begin{cases} d | k a \pm b \\ d | a \Rightarrow d | k a \end{cases}〉 d | (k a) \mp (k a \pm b) \Rightarrow d | b$

$2) d | a, d | b \Rightarrow d |(a, b)$

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

$i f k = 1; (a, b) = 1 \Rightarrow (a \pm b, a) = 1$

قضیه

$(a, b) = (- a, b) = (a, - b) = (- a, - b)$

اثبات

فرض کنیم $\{\begin{cases} (a, b) = d_{1} \\ (- a, b) = d_{2} \end{cases}$ آن‌گاه ثابت می‌کنیم $d_{1} = d_{2}$ .

$(a, b) = d_{1}$

$\Rightarrow \{\begin{cases} d_{1} | a \Rightarrow d_{1} | - a \\ d_{1} | b \end{cases}$

$d_{1} | (- a, b) = d_{2} \Rightarrow d_{1} | d_{2} \Rightarrow d_{1} \leq d_{2}$

به‌طریق مشابه ثابت می‌کنیم اگر $d_{2} \leq d_{1}$ می‌توان نتیجه گرفت $d_{1} = d_{2}$ و در بقیه حالات، مطابق بالا عمل می‌کنیم.

تذکر

اگر $a$ مقسوم علیه یک عدد باشد، $(- a)$ نیز مقسوم علیه دیگر آن عدد است.

به ‌عنوان نمونه مجموعه مقسوم علیه های عدد $6$ عبارت است از:

$\{\pm 1, \pm 2, \pm 3, \pm 6\}$

بنابراین برای به‌دست آوردن مجموعه مقسوم علیه های یک عدد صحیح، کافی است مقسوم علیه های مثبت آن را یافته و قرینه آنها را به این مجموعه بیفزاییم.

قضیه

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

اثبات

با استقرای ریاضی داریم:

$p (1) : (a, b) = 1 \Rightarrow (a^{1}, b) = 1 \Rightarrow p (1) \equiv T$

تساوی به‌ازای $n = 1$ برقرار است.

فرض استقرای ریاضی:

$P (k) : (a, b) = 1 \Rightarrow (a^{k}, b) = 1$

حکم استقرای ریاضی:

$p (k + 1) : (a, b) = 1 \Rightarrow (a^{k + 1}, b) = 1$

$\{\begin{cases} (a, b) = 1 \\ (a^{k}, b) = 1 \end{cases}$

$(a . a^{k}, b) = 1 \Rightarrow (a^{k + 1}, b) = 1$

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

با توجه به این مطلب، برای حالت $(a^{n}, b^{m}) = 1$ نیازی به استفاده از استقرا روی $m$ نداریم و می‌نویسیم:

$(a, b) = 1 \Rightarrow (a^{n}, b) = 1 \Rightarrow (b, a^{n}) = 1 \Rightarrow (b^{m}, a^{n}) = 1 \Rightarrow (a^{n}, b^{m}) = 1$

قضیه

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

اثبات

یادآوری می‌کنیم که:

$(a, b) = 1 \Rightarrow (a, a \pm b) = 1$

$\{\begin{cases} (a, b) = 1 \Rightarrow (a \pm b, a) = 1 \\ (a, b) = 1 \Rightarrow (a \pm b, b) = 1 \end{cases}$

$(a \pm b, a b) = 1$

قضیه

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

اثبات

$\begin{array}{l} \{\begin{cases} (a, b) = 1 \\ (a, c) = 1 \end{cases} \end{array}$

$(a, b c) = 1 \Rightarrow (a, a b + a c + b c) = 1; a b + a c =ka$

$\begin{array}{l} \{\begin{cases} (a, b) = 1 \\ (c, b) = 1 \end{cases} \end{array}$

$(a c, b) = 1 \Rightarrow (b, a b + b c + a c) = 1; a b + b c =kb$

$\begin{array}{l} \{\begin{cases} (a, c) = 1 \\ (b, c) = 1 \end{cases} \end{array}$

$(c, a b) = 1 \Rightarrow (c, a c + b c + a b) = 1; a c + b c =kc$

$(a b c, a b + a c + b c) = 1$

قضیه

$i f (a, b) = d \Rightarrow (a^{n}, b^{n}) = d^{n}$

اثبات

$\begin{array}{l} (a, b) = d \\ \Rightarrow (\frac{a}{d}, \frac{b}{d}) = \frac{d}{d} \\ \Rightarrow (\frac{a}{d}, \frac{b}{d}) = 1 \end{array}$

$\begin{array}{l} \Rightarrow ({(\frac{a}{d})}^{n}, {(\frac{b}{d})}^{n}) = {(1)}^{n} \\ \Rightarrow (\frac{a^{n}}{d^{n}}, \frac{b^{n}}{d^{n}}) = 1 \end{array}$

$\begin{array}{l} \Rightarrow d^{n} \times (\frac{a^{n}}{d^{n}}, \frac{b^{n}}{d^{n}}) = d^{n} \times 1 \\ \Rightarrow d^{n} (\frac{a^{n}}{d^{n}}, \frac{b^{n}}{d^{n}}) = d^{n} \\ \Rightarrow (a^{n}, b^{n}) = d^{n} \end{array}$

قضیه

$(a, b) = 1 \Rightarrow (a + b, a^{2} + b^{2} + a b) = 1$

اثبات

اثبات از طریق برهان خلف:

فرض کنیم $(a + b, a^{2} + b^{2} + a b) \neq 1$ بنابراین داریم:

$\begin{array}{l} (a + b, a^{2} + b^{2} + a b) = d \end{array}$

$\exists p \in Ν; \{\begin{cases} p | d \\ p | a + b \\ p | a^{2} + b^{2} + a b \Rightarrow p | {(a + b)}^{2} - a b \end{cases}$

چون $p | a + b$ پس $p | a . b$ و از رابطه اخیر خواهیم داشت:

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

که این غیر ممکن است زیرا $p$ عددی است اول، بنابراین بایستی تساوی زیر را داشته باشیم:

$(a + b, a^{2} + b^{2} + a b) = 1$

قضیه

عمل (ب‌م‌م) خاصیت شرکت پذیری دارد، یعنی به ازای هر سه عدد صحیح که تمامشان صفر نیستند:

$\forall a, b, c \in Ζ; ((a, b), c) = (a, (b, c))$

اثبات

فرض می‌کنیم $((a, b), c) = d_{1}$ و $(a, (b, c)) = d_{2}$ باشد، داریم:

$\begin{array}{l} ((a, b), c) = d_{1} \end{array}$

$\Rightarrow \{\begin{cases} d_{1} | (a, b) \Rightarrow d_{1} | a, d_{1} | b \\ d_{1} | c \end{cases}$

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

$\Rightarrow d_{1} |(a, (b, c))$

$\Rightarrow d_{1} | d_{2} \Rightarrow d_{1} \leq d_{2}$

$(a, (b, c)) = d_{2}$

$\begin{array}{l} \Rightarrow \{\begin{cases} d_{2} | a \\ d_{2} | (b, c) \Rightarrow d_{2} | b, d_{2} | c \end{cases} \end{array}$

$\Rightarrow \{\begin{cases} d_{2} | c \\ d_{2} |(a, b) \end{cases}$

$\Rightarrow d_{2} |((a, b), c)$

$\Rightarrow d_{2} | d_{1}$

$\Rightarrow d_{2} \leq d_{1}$

$d_{1} = d_{2}$

تمرین

بزرگ‌ترين مقسوم عليه مشترک اعداد زير را به‌دست آوريد.

$\begin{array}{l} (5 n + 4, 9 n + 7) \end{array}$

$\begin{array}{l} (5 n + 4, 9 n + 7) = d \\ \Rightarrow \{\begin{cases} d | 5 n + 4 \Rightarrow d | 9 (5 n + 4) \\ d | 9 n + 7 \Rightarrow d | 5 (9 n + 7) \end{cases} \\ \Rightarrow d | 9 (5 n + 4) - 5 (9 n + 7) \\ \Rightarrow d | 1 \\ \Rightarrow d = 1 \end{array}$

$(4 a^{2} - 5 a - 4, a - 2)$

$\begin{array}{l} (4 a^{2} - 5 a - 4, a - 2) = d \\ \Rightarrow d | 4 a^{2} - 5 a - 4 \\ \Rightarrow d | a - 2 \end{array}$

$\begin{array}{l} \Rightarrow d | 4 a (a - 2) \end{array}$

$\begin{array}{l} \Rightarrow d | (4 a^{2} - 5 a - 4) - 4 a (a - 2) \end{array}$

$\begin{array}{l} \Rightarrow d | 3 a - 4 \end{array}$

$\begin{array}{l} \{\begin{cases} d | a - 2 \Rightarrow d | 3 (a - 2) \\ d | 3 a - 4 \end{cases} \\ d | 3 (a - 2) - (3 a - 4) \\ \Rightarrow d | - 2 \\ \Rightarrow \{\begin{cases} d = 1 \\ d = 2 \end{cases} \end{array}$

تمرین

ثابت کنید:

$i f \{\begin{cases} (b, 4) = 2 \\ (a, 4) = 2 \end{cases}〉 (a + b, 4) = 4$

$\begin{matrix} (a, 4) = 2 \Rightarrow (\frac{a}{2}, 2) = 1 \Rightarrow \frac{a}{2} = 2 k + 1 \Rightarrow a = 4 k + 2 \end{matrix}$

$\begin{matrix} (b, 4) = 2 \Rightarrow (\frac{b}{2}, 2) = 1 \Rightarrow \frac{b}{2} = 2 k + 1 \Rightarrow b = 4 k + 2 \end{matrix}$

$\begin{array}{l} a + b = (4 k + 2) + (4 k + 2) \\ \Rightarrow a + b = 4 (k + k) + 4 \end{array}$

$\begin{array}{l} \Rightarrow a + b = 4 (k + k + 1); k + k + 1 = q \end{array}$

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

$\forall m, n \in Ν; i f \{\begin{cases} (m, 4) = 2 \\ (n, 4) = 2 \end{cases}〉 (m + n, 4) = 4$

$\begin{array}{l} \{\begin{cases} (m, 4) = 2 \Rightarrow m = 2 (2 k + 1) \\ (n, 4) = 2 \Rightarrow n = 2 (2 k + 1) \end{cases} \end{array}$

$m + n = [2 (2 k + 1)] + [2 (2 k + 1)]$

$\begin{array}{l} \begin{array}{l} \Rightarrow m + n = 8 k + 4 \\ \Rightarrow m + n = 4 (2 k + 1) \\ \Rightarrow (m + n, 4) = 4 \end{array} \end{array}$

$i f (a, b) = 1 \Rightarrow (a + b, a^{2} + b^{2}) = 1 \lor 2$

$\begin{array}{l} i f (a + b, a^{2} + b^{2}) = d \\ \Rightarrow \{\begin{cases} d | a + b \Rightarrow d | {(a + b)}^{2} \\ d | a^{2} + b^{2} \end{cases} \end{array}$

$\begin{array}{l} d | {(a + b)}^{2} - (a^{2} + b^{2}) \\ \Rightarrow d | 2 a b \\ \{\begin{cases} d | 2 a b \\ d | a + b \Rightarrow d | 2 (a + b) \end{cases} \end{array}$

$\begin{array}{l} d | (2 a b, 2 (a + b)) \\ \Rightarrow d | 2 (a b, a + b) \\ \Rightarrow d | 2 \times 1 \\ \Rightarrow \{\begin{cases} d = 1 \\ d = 2 \end{cases} \end{array}$