درسنامه کامل ریاضیات گسسته فصل 1 آشنایی با نظریۀ اعداد
تعداد بازدید : 3.74Mخلاصه نکات ریاضیات گسسته فصل 1 آشنایی با نظریۀ اعداد - درسنامه شب امتحان ریاضیات گسسته فصل 1 آشنایی با نظریۀ اعداد - جزوه شب امتحان ریاضیات گسسته نوبت اول فصل 1 آشنایی با نظریۀ اعداد
انواعی از استدلال
انواعی از استدلال
گزاره
گزاره به يک حکم (يا ادعا) گفته می شود که يا دقيقاً درست و يا دقيقاً نادرست باشد.
اگر گزاره در تمام حالات ممکن درست باشد، گوييم آن گزاره درست است، ولی برای نادرست بودن آن، کافی است فقط در يک مورد نادرست شود.
بنابراين، در مواجهه با يک گزاره، در کل دو راه برای روشن کردن وضعيت آن وجود دارد.
رد کردن يا اثبات درستی
برايی رد يک ادعای کلی، روش زير را به کار می بريم.
مثال نقض
برای نشان دادن اينكه يک حكم کلی نادرست است، کافی است مثالی آورده شود كه كليت آن حكم را رد كند. به چنين مثالی، (مثال نقض) گفته می شود.
اگر بتوانيم برای يک حکم مثال نقض بياوريم، در واقع اثبات کرده ايم که آن حکم نادرست است.
مثال
درستی يا نادرستی گزاره ی زير را تعيين کنيد.
الف برای هر عدد طبيعی n بزرگتر از 1، عدد \({2^n} - 1\) اول است.
نادرست؛ عدد \(n = 4\) براي اين حكم يک مثال نقض است:
\(\begin{array}{l}{2^4} - 1 = 16 - 1 = 15\\ \to 15 = 3 \times 5\end{array}\) اول نیست.
ب مجموع دو عدد گنگ عددی گنگ است.
نادرست است و مثال نقض دارد، عدد های \(a = \sqrt 2 \) و \(b = - \sqrt 2 \) هر دو گنگ هستند ولی جمعشان گویا است:
\(a + b = \sqrt 2 - \sqrt 2 = 0 \in \mathbb{Q}\)
مثالی که برای نقض يک حکم کلی آورده می شود، بايد دارای شرط زير باشد:
فرض عبارت داده شده را برقرار سازد، ولی حکم آن عبارت نادرست شود.
مثال
1 حكم (حاصل جمع سه عدد گنگ، عددی گنگ است.) را با مثال نقض رد کنيد.
بايد سه عدد گنگ ارائه دهيم كه جمعشان گنگ نشود (گويا باشد). عددهای گنگ \(3 - 2\sqrt 2 ,\sqrt 2 + 2,\sqrt 2 - 1\) این شرایط را دارند؛
\(3 - 2\sqrt 2 + \sqrt 2 + 2 + \sqrt 2 - 1 = 4\)
2 هيچ دو عدد صحيح مانند x و y وجود ندارد که تساوي \({x^2} - {y^2} = {(x + y)^2}\) برقرار باشد.
نادرست است و مثال نقض دارد، عدد های \(x = 1\) و \(y = 0\) وجود دارند؛
\({x^2} + {y^2} = {1^2} + {0^2} = 1 + 0 = 1\) و \({(x + y)^2} = {(1 + 0)^2} = {1^2} = 1\)
ممکن است با بررسی مثال های گوناگون، نتوانيم هيچ مثال نقضی پيدا کنيم و تمام مثال های آورده شده، حکم را تاييد کنند. در اين صورت، توجه کنيد:
- هر تعداد مثال در تاييد يک حکم آورده شود، باعث اثبات آن نخواهد شد، چون امکان دارد مثال بعدی، يک مثال نقض باشد.
- وقتی چندين مثال يک حکم را تاييد می کنند، احتمال درست بودن حکم معمولاً بيشتر می شود.
روش نتيجه گيری با بررسی چند مثال و مشاهده ی درستی حکم را (استدلال استقرايی) گويند. اين روش در علوم تجربی کاربرد فراوان دارد. اما در ریاضیات بعد از به کار بردن استدلال استقرايی، حکم را به عنوان يک (حدس) يا (فرضيه) می پذيريم.
برای اينکه فرضيه يا حدس تاييد قطعی شود، نياز به اثبات دارد که توسط دو مؤلفه ی زير انجام می شود.
حقايق پذيرفته شده
اصول و احکامی که قبلاً درستی آنها پذيرفته يا اثبات شده است.
روش های درست استنتاج
معمولاً حقايق پذيرفته شده ی قبلی با روش های درست استدلال، مفروضات مسأله را به کار می برنـد تـا يـک حکـم جديـد اثبات شود.
حقايق پذيرفته شده
برخی حقايق پذيرفته شده که در اثبات ها بيشتر به کار می روند را ببينيد:
هر عدد زوج به صورت \(2k\) و هر عدد فرد به صورت \(2k - 1\) است.
هر عدد گويا را ميتوان به صورت کسر \(\frac{m}{n}\) نوشت که m و n دو عدد صحيح بوده و مخرج غير صفر است.
هر عددی که نتوان آن را به صورت کسر گويا نوشت، گنگ است.
روش های اثبات
می توان روش های اثبات احکام رياضی را در دو نوع کلی طبقه بندی کرد:
اثبات مستقيم و اثبات غيرمستقيم
اثبات مستقيم
در روش هايی که در اين گروه جای می گيرند، فرض مسأله و حقايق قبلی به طور مناسب به کار رفته، حکم تاييد می شود و اثبات صورت می پذيرد.
اثبات غير مستقيم
در اين گروه از روش های اثبات، به نوعی حکم مسأله و حقايق قبلی را مورد استفاده قرار داده و درسـت بـودن حکـم را نتيجه می گيريم.
مثال
1 نشان دهيد مربع هر عدد زوج، زوج و مربع هر عدد فرد هم فرد است.
اگر n عددی زوج باشد:
\(n = 2k \to {n^2} = 4{k^2} = 2 \times 2{k^2} = 2k' \to {n^2} = 2k'\)
اگر n عددی فرد باشد:
\(n = 2k + 1 \to {n^2} = 4{k^2} + 4k + 1 = 2 \times (2{k^2} + 2k) + 1 = 2k' + 1 \to {n^2} = 2k' + 1\)
2 نشان دهيد نتيجه گيری زير برای اعداد درست است.
\(ab = 0 \Rightarrow a = 0 \vee b = 0\)
اگر \(a = 0\) باشد، نتیجه گیری برقرار شده است.
اگر \(a \ne 0\) باشد، در این صورت \(\frac{1}{a}\) وجود دارد و طبق فرض:
\(ab = 0 \Rightarrow \frac{1}{a} \times ab = \frac{1}{a} \times 0 \Rightarrow 1 \times b = 0 \Rightarrow b = 0\)
پس نتیجه گیری همواره درست است.
برسی تمام حالات
گاهی استفاده از تکنيک زير، در اثبات مستقيم احکام مورد نياز است:
تفکیک فرض به تمام حالت های ممکن، و بررسی درستی حکم در هر حالت.
به هم ارزی زير بين گزاره ها توجه کنيد:
\(\begin{array}{l}({P_1} \vee {P_2} \vee ... \vee {P_K}) \Rightarrow q \Leftrightarrow \sim ({P_1} \vee {P_2} \vee ... \vee {P_K}) \vee q\\ \Leftrightarrow ( \sim {P_1} \wedge \sim {P_2} \wedge ... \wedge \sim {P_K}) \vee q\\ \Leftrightarrow ( \sim {P_1} \vee q) \wedge ( \sim {P_2} \vee q) \wedge ... \wedge ( \sim {P_K} \vee q)\\ \Leftrightarrow ({P_1} \Rightarrow q) \wedge ({P_2} \Rightarrow q) \wedge ... \wedge ({P_K} \Rightarrow q)\end{array}\)
یعنی اگر فرض در کل به حالت های \({P_2},{P_1}\) ... و \({P_K}\) تفکيک شده و هرکدام از آن ها درستی q را نشان دهند. درستی q در کل اثبات می گردد.
در ادامه، دو روش در اثبات غير مستقيم و نمونه هايی از هر کدام ببينيد:
برهان خلف
برای استفاده از اين روش، طبق گام های زير عمل می کنيم:
حكم مورد نظر را نادرست در نظر می گيريم؛ يعنی فرض می کنيم حکم نادرست باشد.
با توجه به فرض مرحله ی قبل و بيان استدلالی مناسب، (حقايق شناخته شده) يا (فرض) آن قضيه يا مسأله را نقض می كنيم.
نتيجه می گيريم حكم آن مسأله نمی تواند نادرست باشد و از ابتدا صحيح بوده است.
مثال
1 نشان دهید اگر \({n^2}\) فرد باشد، آنگاه n هم فرد است.
با برهان خلف پیش می رویم؛ فرض كنيد n فرد نباشد. پس n زوج است و چنان كه قبلاً ديديم، بايد\({n^2}\) هم زوج باشد كه با فرض تناقض دارد. پس حكم نمی تواند نادرست باشد و لذا صحيح خواهد بود.
2 اگر \(\alpha \) و \(\beta \) دو عدد گنگ و \(\alpha + \beta \) گویا باشد، نشان دهید عدد \(\alpha + 2\beta \) گنگ است.
با برهان خلف پیش می رویم:
اگر \(\alpha + 2\beta \) گویا باشد، چون تفریق دو عدد گویا، گویا است:
\(\alpha + 2\beta - (\alpha + \beta ) = \beta \) گویا
گویا بودن \(\beta \) با فرض تناقض دارد.
اثبات بازگشتی
در اثبات به طريق بازگشتی به ترتيب زير عمل می کنيم:
درستی حكم را موقتاً می پذيريم.
با شروع از حکم، در چند مرحله به يک رابطه ی بديهی يا فرض داده شده می رسيم.
اکنون اگر تمام مراحل را بتوان از آخر به اول نتيجه گرفت، يعنی اعمال انجام شده برگشت پذير باشـند، درسـتی حكم تأييد می شود.
يک استنتاجِ درست، ممکن است برگشت پذير باشد يا نباشد؛ نمونه ای ببينيد:
استنتاج (\(x = 2 \to {x^2} = 4\) )برگشت پذیر نیست؛ زیرا نتیجه گیری (\({x^2} = 4 \to x = 2\) )
مثال
1 به روش بازگشتی ثابت کنيد: حاصل ضرب هر دو عدد حقيقی، کوچکتر يا مساوی نصف مجموع مربعات آنها است.
باید ثابت کنیم: \(xy \le \frac{{{x^2} + {y^2}}}{2}\)
\(xy \le \frac{{{x^2} + {y^2}}}{2} \to \times 2 \to 2xy \le {x^2} + {y^2} \to 0 \le {x^2} + {y^2} - 2xy \to 0 \le {(x + y)^2}\)
چون نامساوی آخر هميشه صحيح بوده و مراحل بالا برگشتپذير هستند، اثبات كامل است.
2 نامساوی \(a + \frac{1}{a} \ge 2\) را در \(a\rangle 0\) نشان دهید.
کافی است دو طرف حکم \(a + \frac{1}{a} \ge 2\) را در \(a\rangle 0\) ضرب کنیم:
\(a + \frac{1}{a} \ge 2 \to \times a \to {a^2} + 1 \ge 2a \to {a^2} - 2a + 1 \ge 0 \Rightarrow \left( {a - 1} \right) \ge 0\)
عبارت \(\left( {a - 1} \right) \ge 0\) همواره درست است و بعلاوه تمام مراحل بالا برگشت پذير هستند.
وقتی از برگشت پذيری استنتاج ها اطمينان داريد، بهتر است به جای استفاده از نماد \( \to \)، نماد \( \leftrightarrow \) را به کار ببرید.
گزاره ی درست را اثبات کرده و برای گزاره ی نادرست مثال نقض بياوريد.
الف مجموع دو عدد گنگ، عددی گنگ است.
نادرست است و مثال نقض دارد، عدد های \(a = \sqrt 2 \) و \(b = - {\kern 1pt} \sqrt 2 \) هر دو گنگ هستند، ولی جمعشان گویا است؛
\(\begin{array}{l}a + b = \sqrt 2 - \sqrt 2 = 0\\0 \in \mathbb{Q}\end{array}\)
ب اگر \(\alpha \) و \(\beta \) دو عدد گنگ و \(\alpha + \beta \) گویا باشد، نشان دهید عدد \(\alpha + 2\beta \) گنگ است.
با برهان خلف پیش می رویم؛ اگر \(\alpha + 2\beta \) گویا باشد، چون تفریق دو عدد گویا، گویا است؛ \(\alpha + 2\beta - (\alpha + \beta ) = \beta \) گویا بودن \(\beta \) با فرض تناقض دارد.
تهیه کننده: علیرضا نورالدّینی
مای درس ، برترین اپلیکیشن کمک درسی ایران
پوشش تمام محتواهای درسی پایه گسسته- آزمون آنلاین تمامی دروس پایه گسسته
- گام به گام تمامی دروس پایه گسسته
- ویدئو های آموزشی تمامی دروس پایه گسسته
- گنجینه ای از جزوات و نمونه سوالات تمامی دروس پایه گسسته
- فلش کارت های آماده دروس پایه گسسته
- گنجینه ای جامع از انشاء های آماده پایه گسسته
- آموزش جامع آرایه های ادبی، دستور زبان، قواعد زبان انگلیسی و ... ویژه پایه گسسته
کاملا رایگان
+500 هزار کاربر
همین حالا نصب کن
بخش پذیری در Z
بخش پذیری در Z
به بيان دقيق مفهوم (بخش پذيری) در اعداد صحيح توجه کنيد:
بخش پذيری
فرض کنید a و \(b \ne 0\) عددهایی صحیح باشند.
عدد a را بر b(بخش پذير) گوييم، هرگاه عدد صحيح k يافت شود كه \(a = bk\) در این صورت می نویسیم: \(b|a\)
برای نمونه
داریم: \(4| - 12\) ، زیرا عدد \( - 12\) را می توان به صورت \(4( - 3)\) نوشت.
عبارت \(b|a\) به صورت b عاد می کند a را يا b عدد a را می شمارد، خوانده می شود. (b یک شمارنده یا مقسوم علیه a است.)
خواص مقدماتی
تمام اعداد بر 1 و \( - 1\) بخش پذير هستند؛ يعنی همواره: \( \pm 1|a\)
زیرا
\(a = 1 \times a \to 1|a,a = - 1 \times ( - a) \to - 1|a\)
تمام اعداد صحيح، عدد صفر را عاد می کنند، زيرا \(0 = a \times 0\) به عبارت دیگر؛ صفر تنها عددی است که بر تمام اعداد بخش پذير است، يعنی همواره، \(a|0\) .
هيچ عددی بر صفر بخش پذير نيست. ولی چون تساوی \(0 = 0 \times k\) برای هر عدد صحیح k برقرار است، خواهیم داشت \(0|0\) بنابراین:
\(0|a \Rightarrow a = 0\)
يعنی عدد صفر فقط خودش را عاد می کند.
هر عددی بر خودش بخش پذير است؛ زيرا:
\(a = a \times 1 \Rightarrow a|a\)
به صورت مشابه، موارد \(a| - a\) و \( - a|a\) نيز درست هستند. يعنی \( \pm a| \pm a\)
مثال
1 نشان می دهيم برای هر عدد طبيعی n داريم:
\(a|{a^n}\)
در حالت \(n = 1\) ، رابطه ی بدیهی \(a|a\) را داريم که درست است. اگر \(n\rangle 1\) باشد، در این صورت:
\({a^n} = a \times {a^n} - 1 \to {a^n} = ak \Rightarrow a|{a^n}\)
2 نشان می دهيم اگر \(a|b\) ، آنگاه برای هر عدد طبیعی n داریم:
\({a^n}|{b^n}\)
حالت \(n = 1\) بدیهی است. اگر \(n\rangle 1\) باشد، چون \(b = ak\) است، در این صورت:
\(bn = {\left( {ak} \right)^n} = {a^n} \times {k^n} \to {k^n} = k' \to {b^n} = {a^n}k' \Rightarrow {a^n}|{b^n}\)
يادآوری يک مفهوم بسيار پرکاربرد در مبحث نظريه اعداد:
عدد اول
عدد طبیعی \(p\rangle 1\) را اول گوییم. هرگاه غير از 1 و خودش هيچ مقسوم عليه مثبتی نداشته باشد. بنابراين، اگر p عددی اول باشد:
\(a|p \Rightarrow a = \pm 1,a = \pm p\)
ساير اعداد طبيعی بزرگ تر از يک را (مركب) گوييم. بنابراين:
عدد ١ نه اول است و نه مركب.
در ادامه ويژگی های اصلی شمارش، دليل هر کدام و برخی کاربردهای آنها را ببينيد.
1) اگر a عدد b را عاد کند، aهر مضربd از b را نيز عاد می کند؛ يعنی برای هر عدد صحيح m :
\(a|b \Rightarrow a|bm\)
برای نمونه؛
\(5|10 \Rightarrow 5|20,5| - 10,5|50,...\)
2) شمارش، خاصيت تعدی دارد. يعنی اگر a بر b و b بر c بخش پذير باشد، آنگاه:a بر c بخش پذير است.
با صورت نمادين
\(c|b \wedge b|a \Rightarrow c|a\)
برای نمونه؛
از این که \(6|12\) و \(12|48\) می توان نتیجه گرفت: \(6|48\)
برای عددهای صحيح a و b ، با توجه به تجزيه ی عبارت های \({a^n} \pm {b^n}\)
\(\begin{array}{l}{a^n} - {b^n} = (a - b)({a^{n - 1}} + {a^{n - 2}}b + ... + a{b^{n - 2}} + {b^{n - 1}})\\{a^n} + {b^n} = (a + b)({a^{n - 1}} + {a^{n - 2}}b + ... - a{b^{n - 2}} + {b^{n - 1}})\end{array}\)
همواره رابطه ی \(a - b|{a^n} - {b^n}\) برقرار است.
3) اين ويژگی به صورت زير بيان می شود:
اگر دو عدد بر عددی بخش پذير باشند، آنگاه جمع و تفريق آنها هم بر آن عدد بخش پذير است.
با نماد رياضی:
\(a|b \wedge a|c \Rightarrow a|b \pm c\)
4) اگر داشته باشيم \(a|b\) و \(b \ne 0\) باشد، آنگاه \(\left| a \right| \le \left| b \right|\) به صورت نمادین:
\(a|b \wedge b \ne 0 \Rightarrow \left| a \right| \le \left| b \right|\)
به بیان ساده؛ يک عدد مثبت نمی تواند بر عددهای بزرگتر از خود بخش پذير باشد. زیرا:
طبق فرض، عدد \(k \in \mathbb{Z} - \{ 0\} \) هست که \(b = ak\) در نتیجه:
\(\left| b \right| = \left| a \right|\left| k \right| \to \left| k \right| \ge 1 \to \left| b \right| \ge \left| a \right|\)
مثال
1 نشان دهید مربع هر عدد فرد به صورت \(8K + 1\) است.
فرض کنید n عددی فرد باشد، پس؛ \(n = 2q + 1\) و خواهیم داشت:
\({n^2} = {\left( {2q + 1} \right)^2} = 4{q^2} + 4q + 1 = 4q\left( {q + 1} \right) + 1 \to q\left( {q + 1} \right) = 2k \to 8k + 1\)
بيان مهم ديگری از حکم اين مثال چنين است:
(باقی مانده ی تقسيم مربع هر عدد فرد بر 8 برابر 1 است.)
2 نشان دهید اگر k عددی زوج باشد، \({k^3} - 4k\) همواره مضرب 48 است.
می نویسیم \(k = 2n\) و طبق خاصیت گفته شده برای ضرب 3 عدد متوالی:
\({k^3} - 4k = {\left( {2n} \right)^3} - 4\left( {2n} \right) = 8{n^3} - 8n = 8n\left( {{n^2} - 1} \right) = 8n\left( {n - 1} \right)\left( {n + 1} \right) \to n\left( {n - 1} \right)\left( {n + 1} \right) = 6q \to 8n\left( {n - 1} \right)\left( {n + 1} \right) = 48q\)
قضیه تقسیم
در تقسيم عدد صحيح a بر عدد طبيعی b ، اعداد صحيح و يكتای q و r وجود دارند که:
\(\begin{array}{l}a = bq + r\\0 \le r\langle b\end{array}\)
عددهای q و r به ترتيب (خارج قسمت) و (باقيمانده) تقسيم a بر b نام دارند.
در تقسيم a بر b همواره می توان:
خارج قسمت را توسط جزء صحيح \(q = \left[ {\frac{a}{b}} \right]\) و سپس؛ باقيمانده را از رابطه ی \(r = a - bq\) به دست آورد.
دسته بندی اعداد صحیح
فرض کنید \(m\rangle 1\) عدد طبيعی ثابتی باشد. عدد صحيح دلخواه a را در نظر گرفته و آن را بر m تقسيم می کنيم:
\(\begin{array}{l}a = mk + r\\r = 0,1,2,...,m - 1\end{array}\)
می بينيد که می توان عددهای صحيح را بر حسب باقيمانده تقسيم بر m در يک مجموعه قرار داد.
اگر باقيمانده صفر باشد، عددها به صورت زير هستند:
\(a = mk,k \in \mathbb{Z}\)
مجموعه ی تمام اين نوع اعداد را با \({[0]_m}\) نشان می دهیم:
\({[0]_m} = \{ mk|k \in \mathbb{Z}\} \)
اگر باقيمانده ی تقسيم برابر 1 شود، عددها به اين صورت هستند:
\({[1]_m} = \{ mk + 1|k \in \mathbb{Z}\} \)
ساير عددهای صحيح نيز به يکی از صورت های زير خواهند بود:
\(\begin{array}{l}{[2]_m} = \{ mk + 2|k \in \mathbb{Z}\} \\{[3]_m} = \{ mk + 3|k \in \mathbb{Z}\} \\.\\.\\{[m - 1]_m} = \{ mk + m - 1|k \in \mathbb{Z}\} \end{array}\)
بنابراين:
با انتخاب عدد طبيعی m ، مجموعه ی \(\mathbb{Z}\) دقيقاً به تعداد m زير مجموعه افراز می شود:
\({[0]_m},{[1]_m},{[2]_m},...,{[m - 1]_m}\)
یعنی
- اين مجموعه ها هيچکدام تهی نيستند.
- دو به دو اشتراک ندارند.
- هر عدد صحيح در يکی از آنها جای دارد.
هر عدد صحيح a بر حسب عدد طبيعی m به يكی از صورت های زير قابل نوشتن است:
\(mk,mk + 1,mk + 2,...,mk + m - 1\)
مثال
نشان دهيد برای عدد صحيح فرد a ، عدد \({a^4}\) به صورت \(16k + 1\) است.
می دانیم که كه مربع هر عدد فرد به صورت \(8k + 1\) ست، پس می توان نوشت:
\(a4 = {({a^2})^2} = {(8k + 1)^2} = 64{k^2} + 16k + 1 = 16(4{k^2} + k) + 1\)
ثابت کنيد اگر \(p \ge 5\) عددی اول باشد، آنگاه به يکی از دو صورت \(p = 4k + 1\) یا \(p = 4k + 3\) نوشته می شود.
عدد p در تقسيم بر 4 به يكی از چهار حالت زير است:
\(4k,4k + 1,4k + 2,4k + 3\)
در دو حالت زير،p اول نيست:
\(p = 4k:\)
چون p بر 2 بخش پذير است.
\(p = 4k + 2:\)
در اين صورت \(p = 2(2k + 1)\) بوده و باز هم بر 2 بخش پذير است.
در نتيجه:
p فقط می تواند به صورت \(4k + 1\) یا \(4k + 3\) باشد.
تهیه کننده: علیرضا نورالدّینی
جزوات جامع پایه گسسته
جزوه جامع ریاضیات گسسته فصل 1 آشنایی با نظریۀ اعداد
جزوه جامع ریاضیات گسسته فصل 2 گراف و مدل سازی
جزوه جامع ریاضیات گسسته فصل 3 ترکیبیّات (شمارش)
ب.م.م و ک.م.م
ب.م.م و ک.م.م
دو مفهوم ب.م.م و ک.م.م کاربردهای زيادی در نظريه اعداد دارند.
ب.م.م اعداد
فرض كنيد a و b دو عدد صحيح باشند كه لااقل یكی از آنها غيـر صـفر اسـت. عـدد طبيعـی d را (ب.م.م) يعنـی بزرگترين مقسوم عليه مشترک اين دو عدد گوئيم، هرگاه:
1) \(d|b,d|a\)
2) ساير مقسوم عليه های مشترک a و b از d كوچكتر باشند. در اين صورت می نويسيم:
\((a,b) = d\)
در حالت خاص:
اگر \(a|b\) ، آنگاه \((a,b) = \left| a \right|\) است. به ویژه:
\((a,a) = \left| a \right|,(a,0) = \left| a \right|\)
البته عبارت \((0,0)\) بی معنی است.
حالت خاص زير در مورد ب.م.م اعداد اهميت بسياری دارد.
اعداد متباين:
دو عدد a و b را نسبت به هم اول يا (مُتَبايِن) گوئيم، هرگاه:
\((a,b) = 1\)
به دو مورد در ارتباط با اين مفهوم توجه کنيد:
واضح است که \((4,9) = 1\) و بنابراين متباين بودن اعداد ربطی به اول بودن تک تک آنها ندارد.
ولی عکس آن صحيح است:
اگر p و q دو عدد اول مختلف باشند، همواره: \((p,q) = 1\) .
دو عدد a و b وقتی نسبت به هم اول هستند که در تجزيه ی اين دو عدد به عددهای اول، عامـل اول مـشترکی وجود نداشته باشد. برای نمونه؛
چون \(35 = 5 \times 7,48 = {2^2} \times 3\) ، بنابراین \((48,35) = 1\) است.
مثال
1 نشان دهيد عدد 77 نسبت به هر سه عدد 64، 81 و 125 اول است.
تجزيه ی اين عددها به صورت زير است:
\(77 = 7 \times 11,64 = {2^6},81 = {3^4},125 = {5^3}\)
چون 77 با هيچ كدام عامل مشترک ندارد، نسبت به همه ی آنها اول است.
2 نشان دهيد دو عدد فرد متوالی همواره نسبت به هم اول هستند.
دو عدد فرد متوالی به صورت \(2n + 1\) و \(2n + 3\) هستند. قرار می دهیم: \(\left( {2n + 1,2n + 3} \right) = d\) . طبق تعریف:
\(\begin{array}{l}d|2n + 1\\d|2n + 3\\ \to - \to d|2n + 3 - \left( {2n + 1} \right) \to d|2 \to d = 1 \vee d = 2\end{array}\)
چون عدد ها فرد هستند، \(d = 2\) غیرممکن بوده و در نتیجه \(\left( {2n + 1,2n + 3} \right) = 1\) است.
اکنون مضرب های مشترک دو عدد صحيح را بررسی می کنيم:
ک.م.م اعداد
فرض كنيم a و b دو عدد صحيح باشند كه هر دو غير صفر هستند. عدد طبيعـی c را (ک.م.م) يعنـی کوچـکتـرين مضرب مشترک اين دو عدد گوئيم، هرگاه:
1) \(b|c,a|c\)
2) ساير مضرب های مثبت و مشترک a و b از c بزرگتر باشند. در اين صورت می نويسيم:
\([a,b] = c\)
در يک حالت خاص
هر گاه \(a|b\) ، آنگاه \([a,b] = \left| b \right|\) است؛ به ویژه:
\([a, \pm a] = |a|,[ \pm 1,a] = |a|\)
مثال
برای دو عدد صحيح غير صفر a و b ، مقادير زير را حساب کنيد.
\([a,(a,b)],(a,[a,b])\)
چون \((a,b)|a,a|[a,b]\) ، جواب دو مورد برابر \(|a|\) است.
اگر عددهای داده شده را تجزيه کنيد، در اين صورت:
- ب.م.م. برابر ضرب عامل های مشترک با توان کوچکتر است.
- ک.م.م. برابر ضرب عامل های مشترک با توان بزرگتر ضربدر تمام عامل های غير مشترک است.
تکنیک \(a'\) و \(b'\)
ابتدا توجه کنيد:
اگر a و b دو عدد صحيح و \((a,b) = d\) باشد، آنگاه \((\frac{a}{d},\frac{b}{d}) = 1\) است.
اکنون فرض کنيد \((a,b) = d\) باشد، آنگاه:
قرار می دهيم: \(\frac{b}{d} = b',\frac{a}{d} = a'\)
طبق مرحله ی قبل خواهيم داشت: \(a = a'd\) و \(b = b'd\) و البته \((a',b') = 1\)
به جای اينکه دنبال اعداد نسبتاً بزرگ a و b بگرديد، بهتر است دنبال عددهای کوچکتر و متباين \(a'\) و \(b'\) بگردید.
ک.م.م بر حسب \(a'\) و \(b'\)
ک.م.م برابر \([a,b] = a'b'd\) است، زیرا:
\([a,b] = \frac{{a'd \times b'd}}{d} \Rightarrow [a,b] = a'b'd\)
اگر \((a,b) = 1\) باشد، آنگاه \([a,b] = |ab|\)
اگر a و b اعدادی صحيح باشند، آنگاه نشان دهيد \((ab + 1,a) = 1\) .
قرار می دهیم: \((ab + 1,a) = d\)
طبق تعريف بايد \(d|a\) و لذا d هر مضرب a از جمله ab را عاد می كند. بنابراين:
\(\begin{array}{l}d|ab\\d|ab + 1\\ \to d|ab + 1 - d|ab \to d|1 \to d = 1\end{array}\)
تهیه کننده: علیرضا نورالدّینی