۱۰۰ هزار تومان هدیهٔ ثبت‌نام، تا ۱ میلیونبا ثبت‌نام گردونهٔ هدیه را بچرخان: دست‌کم ۱۰۰٬۰۰۰ تومان و تا ۱٬۰۰۰٬۰۰۰ تومان اعتبار هدیه، بدون کارت بانکیگردونهٔ هدیه۱ میلیون برای تو، ۱ میلیون برای دوستتدوستانت را دعوت کن: برای هر دوستی که فعال شود ۱٬۰۰۰٬۰۰۰ تومان اعتبار هدیه می‌گیری و خودش هم ۱٬۰۰۰٬۰۰۰ تومانجوایز
1xAi

خلاصه درس فصل ۱ ریاضیات گسسته دوازدهم؛ درسنامه و نکات مهم

«آشنایی با نظریهٔ اعداد»: ۱۱ درس، هر کدام با توضیح مفاهیم، مثال حل‌شده و نکات مهم.

  • ریاضیات گسسته
  • پایهٔ دوازدهم
  • صفحهٔ ۱ تا ۳۰

این درسنامه را هوش مصنوعی 1xAi از روی صفحه‌های همان درس در کتاب درسی نوشته است (برچسب «تولید هوش مصنوعی»). کنار توضیح‌ها شمارهٔ صفحهٔ کتاب آمده تا با کتاب مقایسه کنی، و مثال حل‌شدهٔ هر درس یک بار دیگر جداگانه حل و بررسی شده؛ مثالی که درست درنیامده حذف شده است.

درس ۱ · صفحهٔ ۱ تا ۵ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

درس 1: استدلال ریاضی

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

پیش از شروع

چطور می‌توان دربارهٔ بی‌نهایت عدد طبیعی حکمی را ثابت کرد، اما فقط دو حالت را بررسی کرد؟

هر عدد طبیعی یا زوج است یا فرد؛ حالت سومی وجود ندارد. اگر حکم را برای یک عدد دلخواه در هر یک از این دو حالت ثابت کنیم، دیگر هیچ عدد طبیعی‌ای از اثبات بیرون نمی‌ماند.

هیچ حالتی جا نماند

هیچ حالتی جا نماند

چطور می‌شود دربارهٔ بی‌نهایت عدد طبیعی، فقط دو حالت را بررسی کرد؟ راز کار این است که هر حالت، یک دستهٔ کامل از عددها را پوشش می‌دهد، نه فقط یک عدد را.

مثلاً هر عدد طبیعی یا زوج است یا فرد؛ امکان دیگری وجود ندارد. پس اگر حکمی را برای یک عدد زوجِ دلخواه و سپس برای یک عدد فردِ دلخواه ثابت کنیم، دیگر هیچ عدد طبیعی بیرون از استدلال ما نمی‌ماند.

این کار شبیه بررسی همهٔ دانش‌آموزان یک مدرسه بر اساس کلاس‌هایشان است: اگر همهٔ کلاس‌ها را بررسی کرده باشیم، کسی جا نمی‌ماند؛ اما بررسی چند دانش‌آموز از چند کلاس کافی نیست.

برای یک اثبات کامل، دو پرسش از خودت بپرس:

  • آیا حالت‌هایم همهٔ امکان‌ها را پوشش می‌دهند؟
  • آیا حکم را در هر حالت، به‌طور کلی ثابت کرده‌ام؟

پس امتحان کردن چند عدد زوج و فرد، جای اثبات برای زوجِ دلخواه و فردِ دلخواه را نمی‌گیرد.

کتاب درسی، صفحهٔ ۴

منطقِ پشتِ حالت‌بندی

منطقِ پشتِ حالت‌بندی

چرا باید حکم را در تک‌تک حالت‌ها ثابت کنیم؟ فرض کن یک بسته یا با پیک می‌رسد یا با پست. برای اطمینان از رسیدن آن تا فردا، کافی نیست فقط بدانیم «اگر با پیک بیاید، تا فردا می‌رسد»؛ مسیر پست هم باید بررسی شود.

در زبان منطق، دو حالت را با pp و qq و نتیجهٔ موردنظر را با rr نشان می‌دهیم. هم‌ارزی زیر می‌گوید نتیجه گرفتن از «این حالت یا آن حالت»، معادل برقرار بودن هر دو شرط است:

((p∨q)⇒r)≡((p⇒r)∧(q⇒r))((p\vee q)\Rightarrow r)\equiv((p\Rightarrow r)\wedge(q\Rightarrow r))

سمت راست را این‌طور بخوان: «اگر pp برقرار باشد، به rr می‌رسیم و اگر qq برقرار باشد، باز هم به rr می‌رسیم.»

برای نمونه، اگر حالت‌ها زوج و فرد بودن عدد طبیعی باشند، هیچ عددی بیرون از این دو حالت نیست. اما اثبات حکم فقط برای عددهای زوج، دربارهٔ عددهای فرد چیزی نمی‌گوید. پس برای کامل شدن اثبات، هم پوشش همهٔ امکان‌ها لازم است و هم اثبات حکم در هر حالت.

کتاب درسی، صفحهٔ ۴

صفر را جدا کن

صفر را جدا کن

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

مثلاً اگر هزینهٔ خرید برابر «تعداد کالا × قیمت هر کالا» باشد و هزینه صفر شود، نمی‌توان بی‌درنگ بر تعداد کالا تقسیم کرد؛ شاید اصلاً کالایی نخریده باشیم!

برای اثبات اینکه از ab=0ab=0 نتیجه می‌شود a=0a=0 یا b=0b=0، دو حالت داریم:

  • اگر a=0a=0 باشد: حکم همین حالا برقرار است؛ چون یکی از دو بخشِ «یا» درست است و لازم نیست bb هم صفر باشد.
  • اگر a≠0a\neq0 باشد: معکوسِ aa وجود دارد. دو طرف تساوی را در a−1a^{-1} ضرب می‌کنیم و به b=0b=0 می‌رسیم.

این دو حالت همهٔ مقدارهای حقیقیِ aa را پوشش می‌دهند. پس هم حکم را ثابت کرده‌ایم و هم هیچ‌جا تقسیم نامجاز انجام نداده‌ایم.

کتاب درسی، صفحهٔ ۴

بررسی عضو به عضو

بررسی عضو به عضو

گاهی دامنهٔ مسئله آن‌قدر کوچک است که می‌توان تک‌تک اعضای آن را بررسی کرد؛ درست مثل وقتی که برای پیدا کردن یک کلید، همهٔ جیب‌های یک کیف را می‌گردی. اگر هیچ جیبی جا نمانده باشد، جست‌وجویت کامل است.

در مسئلهٔ کتاب، می‌دانیم n∈Sn\in S و S={1,2,…,6}S=\{1,2,\ldots,6\} است. پس فقط شش مقدار ممکن داریم. می‌توانیم برای هر عضو، مقدار n2(n+1)24\frac{n^2(n+1)^2}{4} را حساب کنیم و مشخص کنیم زوج است یا فرد. سپس نگاه می‌کنیم کدام عضوها شرطِ زوج بودن را دارند و آیا همگی در A={3,4}A=\{3,4\} هستند.

فرق مهم اینجاست: بررسی چند عدد دلخواه از میان بی‌نهایت عدد، اثبات نیست؛ اما بررسی تمام اعضای دامنه‌ای متناهی، می‌تواند اثبات باشد. در این روش، لازم نیست اعضایی که شرط مسئله را ندارند در مجموعهٔ مقصد باشند؛ باید مطمئن شویم هر عضوی که شرط را دارد، حکم را هم برقرار می‌کند.

کتاب درسی، صفحهٔ ۵

مثال حل‌شده

فرض کن S={1,2,3,4,5,6}S=\{1,2,3,4,5,6\} و A={3,4}A=\{3,4\} باشد؛ ثابت کن اگر n∈Sn\in S و n2(n+1)24\frac{n^2(n+1)^2}{4} زوج باشد، آن‌گاه n∈An\in A.

  1. دامنه فقط شش عضو دارد؛ پس می‌توانیم تمام مقدارهای ممکن nn را بررسی کنیم.

  2. برای محاسبهٔ راحت‌تر می‌نویسیم: n2(n+1)24=(n(n+1)2)2\frac{n^2(n+1)^2}{4}=\left(\frac{n(n+1)}{2}\right)^2.

  3. برای n=1n=1 و n=2n=2، مقدار عبارت به‌ترتیب 11 و 99 است؛ هر دو فردند.

  4. برای n=3n=3 و n=4n=4، مقدار عبارت به‌ترتیب 3636 و 100100 است؛ هر دو زوج‌اند.

  5. برای n=5n=5 و n=6n=6، مقدار عبارت به‌ترتیب 225225 و 441441 است؛ هر دو فردند.

  6. همهٔ اعضای SS بررسی شدند و فقط 33 و 44 شرط زوج بودن را دارند؛ پس n∈{3,4}=An\in\{3,4\}=A.

جواب: فقط برای n=3n=3 و n=4n=4 مقدار عبارت زوج است؛ بنابراین اگر عبارت زوج باشد، n∈An\in A.

نکات مهم

  • در اثبات با درنظر گرفتن همهٔ حالت‌ها، حالت‌ها باید تمام امکان‌ها را بپوشانند و حکم در تک‌تک آن‌ها ثابت شود.
  • پشتوانهٔ منطقی این روش، هم‌ارزی ((p∨q)⇒r)≡((p⇒r)∧(q⇒r))((p\vee q)\Rightarrow r)\equiv((p\Rightarrow r)\wedge(q\Rightarrow r)) است.
  • بسته به مسئله می‌توان حالت‌های صفر و ناصفر را جدا کرد یا در یک دامنهٔ متناهی و کوچک، همهٔ اعضا را بررسی کرد.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۲ · صفحهٔ ۵ تا ۶ · حدود ۱۳ دقیقه · تولید هوش مصنوعی

اثبات غیرمستقیم

در این درس یاد می‌گیری با حفظ فرض‌های مسئله و پذیرفتن موقت نقیض حکم، تناقض را پیدا کنی و با روش برهان خلف گزاره‌هایی دربارهٔ عددهای گویا، گنگ و زوج و فرد را ثابت کنی.

پیش از شروع

چطور می‌توانی برای اثبات یک ادعا، از نادرست بودن همان ادعا شروع کنی و باز هم به اثباتی معتبر برسی؟

در برهان خلف، نادرست بودن حکم را موقتاً می‌پذیریم و پیامدهایش را با استدلال درست دنبال می‌کنیم. اگر به تناقض برسیم، معلوم می‌شود این فرض موقت پذیرفتنی نیست؛ پس حکم درست است.

شروع از نقیض حکم

شروع از نقیض حکم

چطور می‌شود اثبات را از نادرست بودن ادعا شروع کرد؟ در برهان خلف، نادرست بودن حکم را فقط موقتاً می‌پذیریم تا ببینیم چه پیامدی دارد؛ قرار نیست آن را درست بدانیم!

فرض کن مطمئنی کلیدت داخل خانه است و می‌خواهی نشان بدهی داخل کیف نیست. موقتاً می‌پذیری که داخل کیف باشد؛ اگر با دلیل‌های قطعی به نتیجه‌ای ناسازگار با اطلاعاتت برسی، این پذیرش موقت را کنار می‌گذاری.

در اثبات ریاضی هم مسیر همین است:

  • فرض‌های مسئله را نگه می‌داریم.
  • نقیض حکم را به آن‌ها اضافه می‌کنیم؛ یعنی می‌پذیریم چیزی که می‌خواهیم ثابت کنیم، نادرست باشد.
  • با استدلال‌های معتبر پیش می‌رویم تا به تناقض برسیم؛ مثلاً نتیجه بگیریم یک عدد هم زوج است و هم فرد.

این بن‌بست نشان می‌دهد نقیض حکم نمی‌تواند درست باشد؛ پس خود حکم درست است. دقت کن: فرض‌های اصلی را رد نمی‌کنیم و صرفاً دشوار شدن حل هم تناقض نیست.

کتاب درسی، صفحهٔ ۵

تناقض با گنگ بودن

تناقض با گنگ بودن

فرض کن rr عددی گویا و xx عددی گنگ است. می‌خواهیم ثابت کنیم x+rx+r گنگ است. فرض‌های مسئله را نگه می‌داریم و فقط خلاف حکم را موقتاً می‌پذیریم: فرض می‌کنیم x+rx+r گویاست.

حالا از این مجموع، rr را کم می‌کنیم. تفاضل دو عدد گویا، گویاست؛ بنابراین طبق فرض خلف، باید داشته باشیم:

(x+r)−r=x∈Q(x+r)-r=x\in\mathbb{Q}

اما از ابتدا می‌دانستیم xx گنگ است! یک عدد نمی‌تواند هم گویا و هم گنگ باشد؛ پس به تناقض رسیده‌ایم. بنابراین فرضِ گویا بودن مجموع باطل است و x+rx+r گنگ است.

نکتهٔ کلیدی این است: افزودن یک عدد گویا نمی‌تواند گنگ بودن عدد را از بین ببرد؛ چون با کم کردن همان عدد گویا، دوباره به عدد آغازین برمی‌گردیم. دقت کن که در فرض خلف، گنگ بودن xx را تغییر ندادیم؛ فقط گویا بودنِ مجموع را فرض کردیم.

کتاب درسی، صفحهٔ ۵

چرا شرط ناصفر مهم است؟

چرا شرط ناصفر مهم است؟

اگر rr عددی گویا و ناصفر و xx عددی گنگ باشد، می‌خواهیم ثابت کنیم rxrx گنگ است. اینجا شرط ناصفر بودن یک ابزار ضروری در اختیارمان می‌گذارد: معکوسِ rr وجود دارد و گویاست.

فرض‌های مسئله را نگه می‌داریم و موقتاً می‌پذیریم که rxrx گویا باشد؛ این همان فرض خلف است. چون حاصل‌ضرب دو عدد گویا، گویاست، داریم:

1r(rx)=x\frac{1}{r}(rx)=x

پس xx باید گویا باشد؛ اما از ابتدا می‌دانستیم گنگ است! این تناقض نشان می‌دهد فرض خلف نادرست بوده و rxrx گنگ است.

برای نمونه، اگر طولی برابر 2\sqrt{2} را با ضریب 32\frac{3}{2} بزرگ کنیم، طول جدید همچنان گنگ است. اما ضریب صفر همه‌چیز را عوض می‌کند: 0×2=00\times\sqrt{2}=0 و حاصل گویاست. پس شرط ناصفر بودن هم استفاده از معکوس را ممکن می‌کند و هم جلوی این حالت نقض را می‌گیرد.

کتاب درسی، صفحهٔ ۵

یک مجموع، دو نتیجهٔ ناسازگار

یک مجموع، دو نتیجهٔ ناسازگار

دو فهرست از عددهای صحیح داریم: a1,a2,a3a_1,a_2,a_3 و b1,b2,b3b_1,b_2,b_3. فهرست دوم همان عددهای فهرست اول است، فقط جای آن‌ها عوض شده؛ مثل سه کارت عدددار که دوباره مرتبشان کنیم. پس مجموع دو فهرست برابر است.

می‌خواهیم نشان دهیم (a1−b1)(a2−b2)(a3−b3)(a_1-b_1)(a_2-b_2)(a_3-b_3) زوج است. فرض خلف: این حاصل‌ضرب زوج نباشد؛ پس فرد است. در این صورت هر سه عامل باید فرد باشند، چون وجود حتی یک عامل زوج، حاصل‌ضرب را زوج می‌کند.

حالا به‌جای حاصل‌ضرب، مجموع عامل‌ها را بررسی کن. مجموع سه عدد فرد، فرد است؛ اما از طرف دیگر:

(a1−b1)+(a2−b2)+(a3−b3)=(a1+a2+a3)−(b1+b2+b3)=0(a_1-b_1)+(a_2-b_2)+(a_3-b_3)=(a_1+a_2+a_3)-(b_1+b_2+b_3)=0

چون دو فهرست مجموع یکسانی دارند، این مجموع صفر و در نتیجه زوج است. یک عدد نمی‌تواند هم فرد باشد و هم زوج! پس فرض خلف باطل است و حاصل‌ضرب حتماً زوج است.

نکتهٔ راهگشا این بود: برای بررسی حاصل‌ضرب، سراغ مجموع عامل‌ها رفتیم؛ چون جابه‌جایی عددها مجموعشان را تغییر نمی‌دهد.

کتاب درسی، صفحهٔ ۶

مثال حل‌شده

با استفاده از برهان خلف ثابت کنید اگر xx عددی گنگ باشد، 1x\frac{1}{x} نیز گنگ است.

  1. چون صفر گویاست و xx گنگ است، داریم x≠0x\ne 0؛ بنابراین 1x\frac{1}{x} تعریف شده است.

  2. فرض خلف: فرض می‌کنیم 1x\frac{1}{x} گویا باشد و آن را rr می‌نامیم؛ پس r=1xr=\frac{1}{x}.

  3. چون صورت کسر ناصفر است، r≠0r\ne 0؛ پس معکوسِ عدد گویای rr نیز گویاست.

  4. از r=1xr=\frac{1}{x} نتیجه می‌گیریم x=1rx=\frac{1}{r}؛ بنابراین xx گویاست، درحالی‌که طبق فرض مسئله گنگ است. این تناقض است.

  5. پس فرض خلف باطل است و 1x\frac{1}{x} گنگ است.

جواب: اگر xx گنگ باشد، 1x\frac{1}{x} نیز گنگ است.

نکات مهم

  • در برهان خلف، فرض‌های مسئله را حفظ می‌کنیم و نقیض حکم را موقتاً می‌پذیریم.
  • با استدلال‌های معتبر به تناقض می‌رسیم و سپس با رد فرض خلف، درستی حکم را نتیجه می‌گیریم.
  • در هر گام باید شرط‌های لازم را بررسی کنیم؛ مثلاً استفاده از معکوس یک عدد، به ناصفر بودن آن نیاز دارد.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۳ · صفحهٔ ۶ تا ۹ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

اثبات‌های بازگشتی / گزاره‌های هم‌ارز

در این درس یاد می‌گیری هم‌ارزی دو گزاره را بررسی کنی و با زنجیره‌ای از تبدیل‌های برگشت‌پذیر، درستی یا نادرستی یک گزارهٔ ریاضی را نشان بدهی.

پیش از شروع

چرا می‌توان برابری دو عدد حقیقی را از برابر بودن مکعب‌هایشان فهمید، اما برابر بودن مربع‌هایشان کافی نیست؟

دو عدد مخالف، مثل 22 و −2-2، مربع یکسان دارند؛ پس مربع‌کردن ممکن است تفاوت دو عدد را پنهان کند. اما مکعب دو عدد حقیقی فقط وقتی برابر است که خودشان برابر باشند؛ در اثبات‌های بازگشتی، همین امکانِ برگشتن از هر گام اهمیت دارد.

هم‌ارزی یعنی راه دوطرفه

هم‌ارزی یعنی راه دوطرفه

فرض کن برای ورود به کتابخانه، داشتن کارت معتبر هم لازم باشد و هم کافی. در این صورت «کارت معتبر داری» و «اجازهٔ ورود داری» دو بیان از یک وضعیت‌اند: از هرکدام می‌توانی دیگری را نتیجه بگیری.

در ریاضی هم دو گزارهٔ هم‌ارز همیشه ارزش درستی یکسان دارند؛ یعنی در شرایط مورد بررسی، یا هر دو درست‌اند یا هر دو نادرست. هم‌ارزیِ دو گزارهٔ PP و QQ را با P⇔QP\Leftrightarrow Q نشان می‌دهیم.

این نماد یک راه دوطرفه است:

  • P⇒QP\Rightarrow Q: از درستیِ PP، درستیِ QQ نتیجه می‌شود.
  • Q⇒PQ\Rightarrow P: از درستیِ QQ، درستیِ PP نتیجه می‌شود.

نکتهٔ مهم: هم‌ارز بودن لزوماً یعنی «هر دو درست‌اند» نیست! هم‌ارزی فقط می‌گوید ارزششان یکسان است. پس اگر هم‌ارزی را بدانیم و معلوم شود یکی نادرست است، دیگری هم نادرست خواهد بود.

کتاب درسی، صفحهٔ ۶

هر تغییر، هم‌ارزی نیست

هر تغییر، هم‌ارزی نیست

علامت ⇔\Leftrightarrow یعنی مسیر استدلال هم رفت دارد، هم برگشت. پس هر بار که آن را می‌نویسی، بپرس: «آیا از عبارت تازه می‌توانم حتماً به عبارت قبلی برگردم؟»

برای عددهای حقیقی، از a=ba=b می‌توان نتیجه گرفت a2=b2a^2=b^2؛ اما برگشت همیشه ممکن نیست. مربع‌کردن، نشانهٔ مثبت یا منفی عدد را از بین می‌برد؛ مثلاً 33 و −3-3 برابر نیستند، ولی مربع‌هایشان برابر است. بنابراین برابر بودن مربع‌ها، به‌تنهایی برابری خود عددها را تضمین نمی‌کند.

در مقابل، مکعب‌کردن چنین مشکلی ندارد: دو عدد حقیقی متفاوت نمی‌توانند مکعب یکسانی داشته باشند. پس a=b⇔a3=b3a=b\Leftrightarrow a^3=b^3 درست است.

شرط‌های مسئله تعیین‌کننده‌اند: اگر بدانیم هر دو عدد نامنفی‌اند، برابر بودن مربع‌هایشان هم برابری خودشان را نتیجه می‌دهد. در نامساوی‌ها نیز ضرب یا تقسیم در عدد مثبت جهت را حفظ می‌کند، ولی عدد منفی جهت را عوض می‌کند. پس پیش از هر تبدیل، دامنه و شرط‌ها را بررسی کن.

کتاب درسی، صفحهٔ ۶

زنجیره‌ای تا یک حقیقت روشن

زنجیره‌ای تا یک حقیقت روشن

گاهی حکم مسئله در نگاه اول پیچیده است؛ اما می‌توانیم آن را به شکل ساده‌تری بیان کنیم، بدون اینکه ارزش درستی‌اش عوض شود. اگر این کار را چند بار انجام دهیم، یک زنجیرهٔ هم‌ارزی می‌سازیم:

P⇔Q⇔RP\Leftrightarrow Q\Leftrightarrow R

هدف این است که در پایان به گزاره‌ای برسیم که درستی آن روشن باشد؛ مثلاً مربع هر عدد حقیقی نامنفی است، پس (a−1)2≥0(a-1)^2\ge 0 همیشه برقرار است. مجموع چند مربع نیز نامنفی است.

اما چرا این پایان، حکم اول را ثابت می‌کند؟ چون می‌توانیم مسیر را از آخر به اول برگردیم: درستی گزارهٔ آخر، درستی گزارهٔ قبلی و سرانجام درستی حکم آغازین را نتیجه می‌دهد.

این روش شبیه عوض‌کردن بیان یک پیام است: عبارت‌ها ساده‌تر می‌شوند، ولی معنا ثابت می‌ماند. فقط یادت باشد هر پیکان باید واقعاً دوطرفه باشد؛ رسیدن به یک حقیقت روشن با تغییرهای یک‌طرفه، به‌تنهایی اثبات حکم اولیه نیست.

کتاب درسی، صفحهٔ ۷

هم‌ارزی برای رد کردن

هم‌ارزی برای رد کردن

زنجیرهٔ هم‌ارزی قرار نیست همیشه به نتیجه‌ای درست برسد! هم‌ارزی، ارزش درستی را حفظ می‌کند؛ بنابراین اگر آخر زنجیره به گزاره‌ای نادرست برسیم، گزارهٔ آغازین هم تحت همان شرط‌ها نادرست است.

مثلاً کسی ادعا می‌کند: «اگر به موجودی کیف پولت مبلغی اضافه کنی، موجودی تغییر نمی‌کند.» با کم‌کردن موجودی اولیه از دو طرفِ برابری، ادعایش معادل این می‌شود که مبلغ اضافه‌شده صفر بوده است. اگر مبلغ اضافه‌شده مثبت باشد، این نتیجه نادرست است؛ پس ادعای اولیه هم نادرست بوده است.

در ریاضی هم می‌توانیم یک برابری را با تبدیل‌های برگشت‌پذیر به شرطی برسانیم که با فرض مسئله ناسازگار است. اینجا دیگر دنبال یک حقیقت روشن نیستیم؛ رسیدن به یک ناسازگاری روشن، راه رد کردن ادعاست.

فقط حواست باشد: اگر حتی یکی از پیکان‌ها صرفاً یک‌طرفه باشد، نمی‌توانی بدون بررسی جهت آن، ارزش درستی را در سراسر زنجیره یکسان بدانی.

کتاب درسی، صفحهٔ ۸

مثال حل‌شده

با روش گزاره‌های هم‌ارز ثابت کن برای هر سه عدد حقیقی x,y,zx,y,z داریم: x2+y2+z2≥xy+yz+zxx^2+y^2+z^2\ge xy+yz+zx.

  1. همهٔ جمله‌ها را به سمت چپ می‌بریم؛ این کار برگشت‌پذیر است: x2+y2+z2≥xy+yz+zx⇔x2+y2+z2−xy−yz−zx≥0x^2+y^2+z^2\ge xy+yz+zx\Leftrightarrow x^2+y^2+z^2-xy-yz-zx\ge 0.

  2. دو طرف را در عدد مثبت 22 ضرب می‌کنیم، پس جهت نامساوی تغییر نمی‌کند: x2+y2+z2−xy−yz−zx≥0⇔2x2+2y2+2z2−2xy−2yz−2zx≥0x^2+y^2+z^2-xy-yz-zx\ge 0\Leftrightarrow 2x^2+2y^2+2z^2-2xy-2yz-2zx\ge 0.

  3. عبارت را به صورت مجموع مربع‌ها بازنویسی می‌کنیم: 2x2+2y2+2z2−2xy−2yz−2zx≥0⇔(x−y)2+(y−z)2+(z−x)2≥02x^2+2y^2+2z^2-2xy-2yz-2zx\ge 0\Leftrightarrow (x-y)^2+(y-z)^2+(z-x)^2\ge 0.

  4. هر مربع نامنفی است، پس گزارهٔ پایانی همواره درست است. چون همهٔ مراحل هم‌ارزی‌اند، نامساوی آغازین نیز ثابت می‌شود؛ مجموع مربع‌ها دقیقاً وقتی صفر است که x=y=zx=y=z.

جواب: برای هر سه عدد حقیقی x,y,zx,y,z، نامساوی x2+y2+z2≥xy+yz+zxx^2+y^2+z^2\ge xy+yz+zx برقرار است؛ تساوی دقیقاً وقتی رخ می‌دهد که x=y=zx=y=z.

نکات مهم

  • دو گزارهٔ هم‌ارز ارزش درستی یکسان دارند؛ ممکن است هر دو درست یا هر دو نادرست باشند.
  • برای نوشتن ⇔\Leftrightarrow باید هر تبدیل، با توجه به دامنه و شرط‌های مسئله، در هر دو جهت معتبر باشد.
  • در زنجیرهٔ هم‌ارزی، رسیدن به گزاره‌ای با ارزش معلوم، درستی یا نادرستی گزارهٔ آغازین را مشخص می‌کند.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۴ · صفحهٔ ۹ تا ۱۰ · حدود ۱۲ دقیقه · تولید هوش مصنوعی

درس دوم: بخش‌پذیری در اعداد صحیح^۱

در این درس یاد می‌گیری بخش‌پذیری اعداد صحیح را با تعریف ضربی بررسی کنی، ویژگی مضرب‌ها و توان‌ها را به کار ببری و ادعاهای نادرست دربارهٔ حاصل‌ضرب و حذف عامل مشترک را تشخیص بدهی.

پیش از شروع

اگر عددی حاصل‌ضرب دو عدد را بشمارد، حتماً دست‌کم یکی از آن دو عدد را هم می‌شمارد؟

نه، همیشه این‌طور نیست! مثلاً 66 حاصل‌ضرب 3×43\times4 را می‌شمارد، اما نه 33 و نه 44 بر 66 بخش‌پذیر نیستند. در این درس یاد می‌گیری چطور با تعریف بخش‌پذیری، درستی چنین ادعاهایی را بررسی کنی.

بخش‌پذیری یعنی یک ضرب صحیح

بخش‌پذیری یعنی یک ضرب صحیح

فرض کن می‌خواهی 1212 مداد را در بسته‌های 44تایی بچینی. چون 12=4×312=4\times3، هیچ مدادی باقی نمی‌ماند؛ می‌نویسیم 4∣124|12 و می‌خوانیم «44، عدد 1212 را می‌شمارد».

همین فکر را به عددهای صحیح گسترش می‌دهیم: برای a≠0a\ne0، رابطهٔ a∣ba|b یعنی یک عدد صحیح مثل qq وجود دارد که b=aqb=aq باشد. دقت کن: عدد سمت چپِ نشانه، شمارنده است و عدد سمت راست، عددی است که شمرده می‌شود.

منفی بودن مانعی ندارد؛ مثلاً 4∣−284|-28، چون −28=4×(−7)-28=4\times(-7). مهم این است که عاملِ qq صحیح باشد، نه اینکه مثبت باشد. در مقابل، 5∤125\nmid12، چون هیچ عدد صحیحی نیست که حاصل‌ضربش در 55 برابر 1212 شود.

پس برای بررسی بخش‌پذیری، از خودت بپرس: «آیا می‌توانم عدد سمت راست را به شکلِ عدد سمت چپ ضرب‌در یک عدد صحیح بنویسم؟»

کتاب درسی، صفحهٔ ۹

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

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

فرض کن تعدادی مهره را بدون باقی‌مانده در بسته‌های aaتایی چیده‌ای. اگر چند برابر همان تعداد مهره داشته باشی، باز هم بسته‌بندی کامل می‌شود. در زبان ریاضی، اگر a∣ba|b باشد، برای هر عدد صحیح mm داریم a∣mba|mb؛ حتی اگر mm منفی یا صفر باشد.

چرا؟ چون از a∣ba|b می‌دانیم b=aqb=aq، که qq صحیح است. پس:

mb=a(mq)mb=a(mq)

حاصل‌ضرب mqmq هم صحیح است؛ بنابراین تعریف بخش‌پذیری برقرار می‌ماند.

توان‌ها هم مضرب‌اند. برای هر عدد طبیعیِ مثبت nn می‌توان نوشت bn=b×bn−1b^n=b\times b^{n-1}؛ پس از a∣ba|b نتیجه می‌گیریم a∣bna|b^n.

برای توان‌های هم‌پایه هم دنبال همین «عامل صحیح» بگرد: اگر a≠0a\ne0 و m≤nm\le n باشند، داریم:

an=am×an−ma^n=a^m\times a^{n-m}

چون عامل دوم عددی صحیح است، am∣ana^m|a^n. پس لازم نیست مقدار توان‌های بزرگ را حساب کنی؛ کافی است بتوانی توان بزرگ‌تر را به شکل یک مضرب صحیح از توان کوچک‌تر بنویسی.

کتاب درسی، صفحهٔ ۱۰

دامِ حاصل‌ضرب

دامِ حاصل‌ضرب

اگر عددی حاصل‌ضرب دو عدد را بشمارد، آیا حتماً یکی از عامل‌ها را هم می‌شمارد؟ نه، لزوماً چنین نیست. ممکن است حاصل‌ضرب بر آن عدد بخش‌پذیر باشد، ولی هیچ‌کدام از عامل‌ها به‌تنهایی بخش‌پذیر نباشند.

مثلاً یک چیدمان با 33 ردیف و 44 مهره در هر ردیف را تصور کن. تعداد کل مهره‌ها 1212 است و می‌توان آن‌ها را به دسته‌های 66تایی تقسیم کرد، چون 12=6×212=6\times2. پس 6∣3×46\mid3\times4؛ اما نه 33 و نه 44 بر 66 بخش‌پذیر نیستند.

این نمونه یک مثال نقض است: ادعایی که قرار است همیشه درست باشد، با همین یک مورد رد می‌شود. بنابراین از a∣bca\mid bc به‌تنهایی نمی‌توان نتیجه گرفت که a∣ba\mid b یا a∣ca\mid c است. البته ممکن است در بعضی نمونه‌ها یکی از عامل‌ها بخش‌پذیر باشد؛ اشتباه این است که آن را همیشگی بدانیم.

کتاب درسی، صفحهٔ ۱۰

ضرب و حذف عامل مشترک

ضرب و حذف عامل مشترک

فرض کن a≠0a\ne0 و k≠0k\ne0 باشند. اگر a∣ba|b، طبق تعریف، عدد صحیحی مثل qq داریم که b=aqb=aq. با ضرب دو طرف در kk می‌رسیم به:

kb=(ka)qkb=(ka)q

پس ka∣kbka|kb؛ همان عدد صحیح qq هنوز کار می‌کند!

مسیر برگشت هم برقرار است: اگر ka∣kbka|kb، می‌توان نوشت kb=(ka)qkb=(ka)q. چون k≠0k\ne0 است، دو طرف را بر kk تقسیم می‌کنیم و به b=aqb=aq می‌رسیم؛ پس a∣ba|b.

بنابراین برای عامل مشترک ناصفر:

a∣b  ⟺  ka∣kba|b\iff ka|kb

مثلاً 4∣124|12 و (−8)∣(−24)(-8)|(-24) هر دو درست‌اند؛ در رابطهٔ دوم، هر دو عدد در −2-2 ضرب شده‌اند.

اما اگر k=0k=0 باشد چه؟ هر دو عدد به صفر تبدیل می‌شوند و طبق قرارداد کتاب، 0∣00|0 پذیرفته است. این رابطه دیگر چیزی دربارهٔ عددهای اولیه نمی‌گوید! مثلاً 0∣00|0 درست است، ولی 4∤64\nmid6. پس ضرب در صفر رابطهٔ درست را حفظ می‌کند، اما برای برگشت نمی‌توان صفر را حذف کرد.

کتاب درسی، صفحهٔ ۱۰

مثال حل‌شده

با استفاده از تعریف بخش‌پذیری نشان بده 53∣575^3\mid5^7؛ سپس بررسی کن آیا (−2)53∣(−2)57(-2)5^3\mid(-2)5^7 نیز برقرار است.

  1. برای اثبات رابطهٔ نخست، باید 575^7 را به‌صورت حاصل‌ضرب 535^3 در یک عدد صحیح بنویسیم.

  2. با قانون توان‌ها داریم: 57=53×57−3=53×545^7=5^3\times5^{7-3}=5^3\times5^4.

  3. چون 545^4 عددی صحیح است، تعریف بخش‌پذیری نشان می‌دهد 53∣575^3\mid5^7.

  4. دو طرف تساوی را در −2-2 ضرب می‌کنیم: (−2)57=((−2)53)×54(-2)5^7=\bigl((-2)5^3\bigr)\times5^4. پس رابطهٔ دوم هم با همان ضریب صحیح برقرار است.

جواب: هر دو رابطه برقرارند: 53∣575^3\mid5^7 و (−2)53∣(−2)57(-2)5^3\mid(-2)5^7؛ در هر دو، ضریب صحیحِ تعریف بخش‌پذیری q=54q=5^4 است.

نکات مهم

  • برای a≠0a\ne0، رابطهٔ a∣ba\mid b یعنی عدد صحیحی مانند qq وجود دارد که b=aqb=aq؛ منفی بودن عددها مانعی نیست.
  • اگر a∣ba\mid b باشد، هر مضرب صحیح و هر توان طبیعیِ مثبتِ bb نیز بر aa بخش‌پذیر است.
  • از a∣bca\mid bc نمی‌توان بخش‌پذیری یکی از عامل‌ها را نتیجه گرفت، و حذف عامل مشترک از ka∣kbka\mid kb فقط برای k≠0k\ne0 معتبر است.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۵ · صفحهٔ ۱۰ تا ۱۳ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

ویژگی‌های رابطهٔ عاد کردن

در این درس یاد می‌گیری … با ویژگی‌های رابطهٔ عاد کردن، بخش‌پذیری و محدودیت شمارنده‌های مشترک را استدلال کنی و ب‌م‌م و ک‌م‌م را از روی تعریف تشخیص دهی.

پیش از شروع

بدون دانستن مقدار عدد صحیح mm، می‌توانی بگویی کدام عددهای صحیح ممکن است هر دو عدد 7m+67m+6 و 6m+56m+5 را عاد کنند؟

بله؛ تنها امکان‌ها 11 و −1-1 هستند! با ساختن دو مضرب مناسب و کم‌کردن آن‌ها، عبارت‌های دارای mm حذف می‌شوند و می‌فهمیم شمارندهٔ مشترک باید عدد 11 را هم عاد کند.

از یک عدد به مضرب‌هایش

از یک عدد به مضرب‌هایش

فرض کن مدادها را در بسته‌های 66تایی گذاشته‌ای و می‌توانی هر بسته را بدون باقی‌مانده بین 33 نفر تقسیم کنی. هر تعداد از این بسته‌ها هم داشته باشی، باز تقسیم بدون باقی‌مانده ممکن است؛ چون تعداد کل مدادها مضربی از 66 است.

دلیل ریاضی: وقتی a∣ba\mid b، یعنی عدد صحیحی مانند qq وجود دارد که b=aqb=aq. پس برای هر عدد صحیح mm داریم:

mb=a(mq)mb=a(mq)

چون mqmq صحیح است، نتیجه می‌گیریم a∣mba\mid mb. این استدلال حتی برای ضریب‌های منفی و صفر هم برقرار است.

توان‌های طبیعیِ مثبتِ bb نیز مضربِ bb هستند؛ بنابراین:

a∣b⇒a∣bn(n≥1)a\mid b\Rightarrow a\mid b^n\qquad(n\ge 1)

اما مراقب جهت استدلال باش! اگر یک حاصل‌ضرب بر عددی بخش‌پذیر باشد، لزوماً هیچ‌یک از عامل‌ها به‌تنهایی بر آن بخش‌پذیر نیست. مثلاً 6∣3×46\mid 3\times4، درحالی‌که 6∤36\nmid3 و 6∤46\nmid4. پس بخش‌پذیری حاصل‌ضرب را نباید به یکی از عامل‌ها نسبت بدهیم.

کتاب درسی، صفحهٔ ۱۰

زنجیره، جمع و تفاضل

زنجیره، جمع و تفاضل

رابطهٔ عاد کردن مثل یک زنجیره عمل می‌کند: اگر a∣ba\mid b و b∣cb\mid c، آن‌وقت a∣ca\mid c. چرا؟ از تعریف داریم b=aq1b=aq_1 و c=bq2c=bq_2؛ پس با جای‌گذاری:

c=a(q1q2)c=a(q_1q_2)

چون q1q2q_1q_2 عددی صحیح است، aa شمارندهٔ cc است. این ویژگی را خاصیت تعدی می‌نامیم.

حالا فرض کن تعدادی مداد در دو جعبه داریم و تعداد مدادهای هر جعبه بر aa بخش‌پذیر است. اگر مدادها را یکی کنیم، باز می‌توانیم دسته‌های کاملِ aaتایی بسازیم. اختلاف تعداد مدادها هم بر aa بخش‌پذیر است.

برای دلیل ریاضی، بنویس b=aq1b=aq_1 و c=aq2c=aq_2. آن‌گاه:

b+c=a(q1+q2)b+c=a(q_1+q_2)

b−c=a(q1−q2)b-c=a(q_1-q_2)

پس هر شمارندهٔ مشترک، مجموع و تفاضل را هم می‌شمارد. حتی اگر تفاضل منفی یا صفر شود، استدلال برقرار است؛ چون مجموع و تفاضل دو عدد صحیح، صحیح‌اند.

کتاب درسی، صفحهٔ ۱۱

اندازهٔ شمارنده چقدر است؟

اندازهٔ شمارنده چقدر است؟

آیا شمارنده می‌تواند از عددی که می‌شمارد بزرگ‌تر باشد؟ برای عددهای منفی، باید قدر مطلق را مقایسه کنیم، نه خود عددها را. مثلاً −4∣12-4\mid 12 و داریم ∣−4∣≤∣12∣|-4|\le |12|.

اگر a∣ba\mid b، طبق تعریف عدد صحیحی مانند qq هست که b=aqb=aq. حالا اگر b≠0b\ne0 باشد، qq هم صفر نیست؛ پس ∣q∣≥1|q|\ge1. بنابراین:

∣b∣=∣a∣∣q∣≥∣a∣|b|=|a||q|\ge|a|

پس قدر مطلقِ شمارنده از قدر مطلقِ عدد ناصفر بزرگ‌تر نیست. شرط ناصفر بودن مهم است: مثلاً 8∣08\mid0، اما ∣8∣≤∣0∣|8|\le|0| درست نیست.

حالا اگر دو عدد ناصفر یکدیگر را بشمارند، از یک طرف ∣a∣≤∣b∣|a|\le|b| و از طرف دیگر ∣b∣≤∣a∣|b|\le|a|؛ پس ∣a∣=∣b∣|a|=|b|. یعنی a=ba=b یا a=−ba=-b؛ لازم نیست خودشان برابر باشند! مثلاً 55 و −5-5 یکدیگر را می‌شمارند. اگر یکی از دو عدد صفر باشد و هر دو یکدیگر را بشمارند، دیگری هم ناچار صفر است؛ پس نتیجهٔ برابری قدرمطلق‌ها همچنان برقرار می‌ماند.

کتاب درسی، صفحهٔ ۱۱

حذف متغیر با ترکیب مناسب

حذف متغیر با ترکیب مناسب

اگر a∣ba\mid b و a∣ca\mid c باشد، می‌توانیم هرکدام از این دو عدد را در یک عدد صحیح ضرب کنیم؛ حاصل‌ها همچنان بر aa بخش‌پذیرند. جمع و تفاضل آن‌ها هم بر aa بخش‌پذیر است. پس برای عددهای صحیح mm و nn داریم:

a∣mb+ncوa∣mb−nca\mid mb+nc\qquad\text{و}\qquad a\mid mb-nc

این ویژگی چه کمکی می‌کند؟ گاهی دو عبارتِ دارای متغیر، شمارنده‌ای مشترک دارند، ولی مقدار متغیر را نمی‌دانیم. می‌توانیم عبارت‌ها را در عددهایی مناسب ضرب کنیم تا ضریب متغیرشان برابر شود. با تفریق، بخش متغیردار حذف می‌شود و فقط یک عدد ثابت باقی می‌ماند!

درست مثل دو صورت‌حساب که هزینهٔ کالای مشترکشان برابر است؛ با کم‌کردنشان، آن هزینه حذف می‌شود.

نکتهٔ مهم: اگر در پایان به a∣pa\mid p برسیم و pp عددی اول و aa طبیعی باشد، فقط دو حالت داریم: a=1a=1 یا a=pa=p. این‌ها حالت‌های ممکن‌اند؛ برای بررسی هر حالت باید فرض‌های اولیه را هم در نظر بگیریم.

کتاب درسی، صفحهٔ ۱۲

بزرگ‌ترین شمارنده، کوچک‌ترین مضرب

بزرگ‌ترین شمارنده، کوچک‌ترین مضرب

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

برای اینکه عدد مثبت dd ب‌م‌مِ aa و bb باشد، باید دو شرط داشته باشد:

  • هر دو عدد را بشمارد: d∣ad\mid a و d∣bd\mid b.
  • از هر شمارندهٔ مشترکِ مثبتِ دیگر کوچک‌تر نباشد.

می‌نویسیم: d=(a,b)d=(a,b). دو عدد نباید هم‌زمان صفر باشند. اگر (a,b)=1(a,b)=1، می‌گوییم دو عدد نسبت به هم اول‌اند؛ لازم نیست خودشان عدد اول باشند!

حالا به جای بریدن نوارها، چیدن قطعه‌های هم‌اندازه را تصور کن: کوچک‌ترین طول مثبتی که هم با قطعه‌های یک اندازه و هم با قطعه‌های اندازهٔ دیگر ساخته می‌شود، کوچک‌ترین مضرب مشترک یا ک‌م‌م است.

برای دو عدد ناصفر، عدد مثبت c=[a,b]c=[a,b] باید:

  • مضرب هر دو باشد: a∣ca\mid c و b∣cb\mid c.
  • از هر مضرب مشترکِ مثبتِ دیگر بزرگ‌تر نباشد.

فرق مهم: ب‌م‌م هر دو عدد را می‌شمارد؛ اما ک‌م‌م را هر دو عدد می‌شمارند.

کتاب درسی، صفحهٔ ۱۳

مثال حل‌شده

اگر عدد صحیحِ ناصفرِ aa هر دو عددِ 7m+67m+6 و 6m+56m+5 را عاد کند و mm صحیح باشد، ثابت کن a=±1a=\pm1.

  1. برای حذف mm، ضریب‌های آن را یکسان می‌کنیم؛ از a∣7m+6a\mid7m+6 نتیجه می‌شود a∣6(7m+6)a\mid6(7m+6)، یعنی a∣42m+36a\mid42m+36.

  2. از فرضِ دیگر نیز داریم a∣7(6m+5)a\mid7(6m+5)، پس a∣42m+35a\mid42m+35.

  3. چون aa هر دو عبارت را عاد می‌کند، تفاضلشان را نیز عاد می‌کند: a∣(42m+36)−(42m+35)a\mid(42m+36)-(42m+35).

  4. تفاضل برابر 11 است؛ بنابراین a∣1a\mid1 و با ویژگیِ اندازهٔ شمارنده داریم ∣a∣≤1|a|\le1.

  5. چون aa صحیح و ناصفر است، فقط a=1a=1 یا a=−1a=-1 ممکن است؛ هر دو نیز هر عدد صحیحی را عاد می‌کنند.

جواب: تنها مقدارهای ممکن a=1a=1 و a=−1a=-1 هستند.

نکات مهم

  • از a∣ba\mid b می‌توان بخش‌پذیریِ مضرب‌ها و توان‌های طبیعیِ bb بر aa را نتیجه گرفت و با خاصیت تعدی، زنجیره‌های بخش‌پذیری را به هم وصل کرد.
  • هر شمارندهٔ مشترکِ bb و cc، ترکیبِ mb±ncmb\pm nc را برای ضرایب صحیح نیز عاد می‌کند؛ این ابزار با حذف متغیر و استفاده از a∣da\mid d و d≠0⇒∣a∣≤∣d∣d\ne0\Rightarrow|a|\le|d|، شمارنده‌ها را محدود می‌کند.
  • ب‌م‌م بزرگ‌ترین شمارندهٔ مشترکِ مثبت و ک‌م‌م کوچک‌ترین مضرب مشترکِ مثبت است و ب‌م‌مِ برابر با 11، نسبت به هم اول بودن را نشان می‌دهد.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۶ · صفحهٔ ۱۳ تا ۱۴ · حدود ۱۲ دقیقه · تولید هوش مصنوعی

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

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

پیش از شروع

آیا باقی‌ماندهٔ تقسیم یک عدد منفی هم می‌تواند منفی باشد؟ مثلاً در تقسیم −25-25 بر 77، باقی‌مانده را چه عددی می‌گیری؟

باقی‌ماندهٔ تقسیم باید نامنفی و از مقسوم‌علیه کوچک‌تر باشد؛ حتی وقتی مقسوم منفی است. چون −25=7×(−4)+3-25=7\times(-4)+3، باقی‌ماندهٔ این تقسیم 33 است، نه −4-4.

بزرگ‌ترین شمارندهٔ مشترک

بزرگ‌ترین شمارندهٔ مشترک

فرض کن می‌خواهی دو روبان به طول‌های 1212 و 1818 سانتی‌متر را به قطعه‌های هم‌اندازه ببُری؛ طوری که چیزی اضافه نماند. بزرگ‌ترین طول ممکن برای هر قطعه را چطور پیدا می‌کنی؟

باید دنبال عددی باشی که هر دو طول بر آن بخش‌پذیر باشند؛ یعنی شمارندهٔ مشترک آن‌ها باشد. شمارنده‌های مثبت مشترک این دو عدد، 11، 22، 33 و 66 هستند. بزرگ‌ترینشان 66 است؛ پس می‌نویسیم: (12,18)=6(12,18)=6.

به‌طور کلی، نوشتنِ d=(a,b)d=(a,b) یعنی دو شرط برقرار است:

  • dd مثبت است و هر دو عدد را عاد می‌کند: d∣ad\mid a و d∣bd\mid b.
  • هیچ شمارندهٔ مثبت مشترکی از dd بزرگ‌تر نیست.

دو عدد صحیح نباید هر دو صفر باشند؛ چون هر عدد مثبت، صفر را عاد می‌کند و در این حالت بزرگ‌ترین شمارنده‌ای وجود ندارد.

اگر ب م م دو عدد برابر 11 باشد، آن‌ها را نسبت به هم اول می‌نامیم. لازم نیست خودِ آن دو عدد اول باشند؛ مثلاً 44 و 99 هر دو مرکب‌اند، اما (4,9)=1(4,9)=1.

کتاب درسی، صفحهٔ ۱۳

کوچک‌ترین مضرب مشترک

کوچک‌ترین مضرب مشترک

فرض کن دو چراغ، یکی هر 44 ثانیه و دیگری هر 66 ثانیه روشن می‌شوند. اگر الان با هم روشن شوند، زمان روشن‌شدن دوبارهٔ هر دو باید مضربی مشترک از 44 و 66 باشد. اولین زمان مثبت، همان ک م م این دو عدد است.

برای دو عدد صحیح ناصفر، [a,b][a,b] باید دو ویژگی داشته باشد:

  • هر دو عدد آن را عاد کنند: a∣[a,b]a\mid[a,b] و b∣[a,b]b\mid[a,b].
  • از هر مضرب مشترکِ مثبت دیگر کوچک‌تر یا با آن برابر باشد.

حالا اگر a∣ba\mid b باشد، خودِ ∣b∣|b| مضرب مشترک است و هیچ مضرب مثبتِ bb از آن کوچک‌تر نیست؛ پس [a,b]=∣b∣[a,b]=|b|. از طرف دیگر، ∣a∣|a| هر دو عدد را عاد می‌کند و هیچ شمارندهٔ مثبتِ aa از آن بزرگ‌تر نیست؛ پس (a,b)=∣a∣(a,b)=|a|.

یادت باشد: این دو میان‌بُر فقط وقتی کاربرد دارند که یکی دیگری را عاد کند. قدرمطلق هم باعث می‌شود پاسخ، حتی برای ورودی‌های منفی، مثبت باشد.

کتاب درسی، صفحهٔ ۱۳

عدد اول و ب م م

عدد اول و ب م م

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

فرض کن pp عددی اول است و p∤ap\nmid a. ب م م آن‌ها را dd بنامیم. چون dd شمارندهٔ مثبتِ pp است و عدد اول فقط دو شمارندهٔ مثبت دارد، تنها دو حالت داریم: d=1d=1 یا d=pd=p. اما حالت دوم یعنی p∣ap\mid a؛ درست برخلاف فرض ما! پس فقط d=1d=1 می‌ماند و دو عدد نسبت به هم اول‌اند.

مثلاً برای دسته‌بندی 77 مداد و 1010 پاک‌کن در بسته‌های یکسان و بدون باقی‌مانده، تعداد بسته‌ها باید شمارندهٔ مشترک هر دو عدد باشد. چون 77 اول است و 1010 بر آن بخش‌پذیر نیست، بیش از یک بسته نمی‌توان ساخت.

اول بودن شرط مهمی است: برای دو عدد مرکب، بخش‌پذیر نبودن یکی بر دیگری کافی نیست؛ مثلاً 4∤64\nmid 6، ولی (4,6)=2(4,6)=2.

کتاب درسی، صفحهٔ ۱۴

قاعدهٔ باقی‌مانده

قاعدهٔ باقی‌مانده

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

اگر عدد صحیح aa را بر عدد طبیعیِ مثبت bb تقسیم کنیم، می‌توانیم بنویسیم:

a=bq+ra=bq+r

در این رابطه، qq خارج‌قسمت و rr باقی‌مانده است؛ اما فقط درست بودن تساوی کافی نیست! باقی‌مانده باید این شرط را هم داشته باشد:

0≤r<b0\le r<b

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

برای عددهای منفی هم همین قانون برقرار است. پس اگر در نوشتن تساوی به باقی‌مانده‌ای منفی رسیدی، هنوز تقسیم را به شکل درست ننوشته‌ای؛ باید خارج‌قسمت را تغییر بدهی تا باقی‌مانده در بازهٔ مجاز قرار بگیرد. با رعایت این شرط، فقط یک جفت خارج‌قسمت و باقی‌مانده وجود دارد؛ این همان معنای «منحصربه‌فرد» است.

کتاب درسی، صفحهٔ ۱۴

محاسبه با باقی‌مانده‌ها

محاسبه با باقی‌مانده‌ها

اگر خودِ دو عدد را ندانیم، اما باقی‌مانده‌هایشان را بدانیم، آیا می‌توانیم باقی‌ماندهٔ یک ترکیب از آن‌ها را پیدا کنیم؟ بله؛ کافی است بخشِ مضربِ مقسوم‌علیه را از بخشِ باقی‌مانده جدا کنیم.

فرض کن باقی‌ماندهٔ تقسیم mm و nn بر bb، به‌ترتیب rr و ss باشد. می‌نویسیم:

m=bq1+rm=bq_1+r و n=bq2+sn=bq_2+s.

برای ترکیبی مانند 2m−5n2m-5n، با جای‌گذاری و دسته‌بندی داریم:

2m−5n=b(2q1−5q2)+(2r−5s)2m-5n=b(2q_1-5q_2)+(2r-5s).

بخش اول مضربی از bb است؛ پس برای یافتن باقی‌مانده، فقط بخش 2r−5s2r-5s را بررسی می‌کنیم. این بخش لزوماً باقی‌ماندهٔ نهایی نیست! اگر منفی یا بزرگ‌تر از محدودهٔ مجاز بود، باید با افزودن یا کاستن مضرب‌های bb، آن را به بازهٔ 0≤R<b0\le R<b ببریم.

مثل شمردن وسایل در بسته‌های هم‌اندازه است: بسته‌های کامل در باقی‌مانده اثری ندارند؛ فقط وسایل بیرونِ بسته‌ها مهم‌اند.

کتاب درسی، صفحهٔ ۱۴

مثال حل‌شده

اگر باقی‌ماندهٔ تقسیم عددهای صحیح mm و nn بر 1111 به‌ترتیب 44 و 77 باشد، باقی‌ماندهٔ تقسیم 3m−2n3m-2n بر 1111 را به دست آور.

  1. طبق قضیهٔ تقسیم، برای عددهای صحیحی مانند q1q_1 و q2q_2 می‌نویسیم: m=11q1+4m=11q_1+4 و n=11q2+7n=11q_2+7.

  2. این عبارت‌ها را جای‌گذاری می‌کنیم: 3m−2n=3(11q1+4)−2(11q2+7)3m-2n=3(11q_1+4)-2(11q_2+7).

  3. مضرب‌های 1111 را جدا می‌کنیم: 3m−2n=11(3q1−2q2)−23m-2n=11(3q_1-2q_2)-2.

  4. عدد −2-2 باقی‌ماندهٔ مجاز نیست؛ با نوشتن −2=−11+9-2=-11+9 داریم: 3m−2n=11(3q1−2q2−1)+93m-2n=11(3q_1-2q_2-1)+9.

  5. چون 0≤9<110\le9<11، باقی‌ماندهٔ موردنظر 99 است.

جواب: باقی‌ماندهٔ تقسیم 3m−2n3m-2n بر 1111 برابر 99 است.

نکات مهم

  • ب م م بزرگ‌ترین شمارندهٔ مثبت مشترک است؛ اگر (a,b)=1(a,b)=1 باشد، دو عدد نسبت به هم اول‌اند و به‌ویژه اگر عدد اول pp شمارندهٔ aa نباشد، (p,a)=1(p,a)=1 است.
  • ک م م کوچک‌ترین مضرب مثبت مشترک دو عدد ناصفر است و اگر a∣ba\mid b باشد، داریم (a,b)=∣a∣(a,b)=|a| و [a,b]=∣b∣[a,b]=|b|.
  • در قضیهٔ تقسیم، a=bq+ra=bq+r و 0≤r<b0\le r<b است؛ برای محاسبهٔ باقی‌ماندهٔ ترکیب‌ها نیز باید نتیجهٔ نهایی را به همین بازه برسانیم.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۷ · صفحهٔ ۱۴ تا ۱۵ · حدود ۱۲ دقیقه · تولید هوش مصنوعی

قضیهٔ تقسیم و کاربردها

در این درس یاد می‌گیری با قضیهٔ تقسیم، باقی‌ماندهٔ عددها و ترکیب‌های آن‌ها را پیدا کنی و با دسته‌بندی اعداد بر اساس باقی‌مانده، ویژگی‌هایی از عددهای اول و مربع عددهای فرد را ثابت کنی.

پیش از شروع

اگر باقی‌ماندهٔ تقسیم باید نامنفی باشد، باقی‌ماندهٔ تقسیم −25-25 بر 77 را چطور پیدا می‌کنیم؟ آیا اصلاً می‌توان عدد منفی را با همین قانون تقسیم کرد؟

بله؛ کافی است خارج‌قسمت را طوری انتخاب کنیم که باقی‌مانده در بازهٔ مجاز قرار بگیرد. چون −25=7×(−4)+3-25=7\times(-4)+3 و 0≤3<70\leq3<7، باقی‌مانده برابر 33 است، نه −4-4.

تقسیم با باقی‌ماندهٔ مجاز

تقسیم با باقی‌ماندهٔ مجاز

آیا منفی بودن عدد، قانون تقسیم را عوض می‌کند؟ نه؛ فقط باید در انتخاب باقی‌مانده دقت کنیم.

قضیهٔ تقسیم می‌گوید برای هر عدد صحیح aa و هر عدد طبیعیِ مثبت bb، می‌توان نوشت:

a=bq+r0≤r<ba=bq+r\qquad 0\leq r<b

در این رابطه، aa مقسوم، bb مقسوم‌علیه، qq خارج‌قسمت و rr باقی‌مانده است. شرط آخر یعنی باقی‌مانده باید نامنفی و کوچک‌تر از مقسوم‌علیه باشد؛ درست مثل تقسیم مدادها به بسته‌های مساوی: اگر مدادهای باقی‌مانده برای یک بستهٔ دیگر کافی باشند، بسته‌بندی هنوز تمام نشده است!

برای عدد منفی هم همین شرط برقرار است. تساویِ −25=7(−3)−4-25=7(-3)-4 درست است، اما −4-4 باقی‌ماندهٔ مجاز نیست. در عوض، −25=7(−4)+3-25=7(-4)+3 هم تساوی درستی است و هم شرط باقی‌مانده را دارد.

یکتا بودن یعنی وقتی aa و bb مشخص‌اند، فقط یک جفت عدد صحیحِ qq و rr هر دو شرط را هم‌زمان دارند. پس درست بودنِ تساوی به‌تنهایی کافی نیست؛ بازهٔ باقی‌مانده را هم بررسی کن.

کتاب درسی، صفحهٔ ۱۴

باقی‌ماندهٔ ترکیب اعداد

باقی‌ماندهٔ ترکیب اعداد

اگر باقی‌ماندهٔ دو عدد را بدانیم، برای پیدا کردن باقی‌ماندهٔ جمع یا تفاضل آن‌ها لازم نیست خود عددها را بدانیم؛ بخش‌های مضربِ مقسوم‌علیه را می‌توان کنار گذاشت.

فرض کن هنگام تقسیم بر bb داشته باشیم:

m=bq1+r1m=bq_1+r_1 و n=bq2+r2n=bq_2+r_2.

برای بررسی ترکیبی مثل 2m−5n2m-5n، این نمایش‌ها را جای‌گذاری می‌کنیم:

2m−5n=b(2q1−5q2)+(2r1−5r2)2m-5n=b(2q_1-5q_2)+(2r_1-5r_2).

جملهٔ اول مضربی از bb است؛ پس برای یافتن باقی‌مانده، کافی است عبارت 2r1−5r22r_1-5r_2 را بررسی کنیم.

اما مراقب باش: این عبارت هنوز لزوماً باقی‌ماندهٔ مجاز نیست! اگر منفی باشد، با افزودن مضرب مناسبی از bb آن را به بازهٔ 0≤r<b0\le r<b می‌بریم؛ اگر برابر یا بزرگ‌تر از bb باشد، مضرب مناسبی از bb را کم می‌کنیم. این تغییر، باقی‌ماندهٔ تقسیم بر bb را عوض نمی‌کند؛ درست مثل جابه‌جایی به اندازهٔ دورهای کامل روی یک صفحهٔ ساعت.

کتاب درسی، صفحهٔ ۱۴

دسته‌بندی با باقی‌مانده‌ها

دسته‌بندی با باقی‌مانده‌ها

فرض کن می‌خواهیم همهٔ عددهای صحیح را در چند کشو بچینیم؛ برچسب هر کشو، باقی‌ماندهٔ تقسیم بر bb است. طبق قضیهٔ تقسیم، باقی‌مانده فقط می‌تواند یکی از عددهای 0,1,…,b−10,1,\ldots,b-1 باشد؛ پس دقیقاً bb دسته داریم.

هر عدد صحیح در یک دسته جا می‌گیرد و چون باقی‌مانده یکتاست، هیچ عددی هم‌زمان در دو دسته نیست. در ریاضی به چنین دسته‌بندی‌ای افراز می‌گوییم.

برای دیدن یک نمونهٔ آشنا، مقسوم‌علیه را 22 بگیر. هر عدد صحیح مانند mm را می‌توان به صورت m=2k+rm=2k+r نوشت. باقی‌مانده فقط 00 یا 11 است؛ بنابراین:

  • اگر r=0r=0 باشد، m=2km=2k است؛ یعنی عدد زوج است.
  • اگر r=1r=1 باشد، m=2k+1m=2k+1 است؛ یعنی عدد فرد است.

اینجا kk عددی صحیح است، نه لزوماً مثبت؛ پس عددهای منفی هم در همین دو دسته قرار می‌گیرند. هیچ عدد صحیحی بیرون از این دسته‌بندی نمی‌ماند.

کتاب درسی، صفحهٔ ۱۵

عددهای اول در کدام دسته‌اند؟

عددهای اول در کدام دسته‌اند؟

فرض کن می‌خواهیم عددهای اول بزرگ‌تر از 33 را در دسته‌های باقی‌ماندهٔ تقسیم بر 66 پیدا کنیم. طبق قضیهٔ تقسیم، هر عدد صحیح به صورت 6k+r6k+r نوشته می‌شود و rr یکی از عددهای 0،1،2،3،4،50،1،2،3،4،5 است.

بیاییم دسته‌های نامناسب را کنار بگذاریم:

  • باقی‌مانده‌های 00، 22 و 44 عددی زوج می‌سازند. چون عدد موردنظر بزرگ‌تر از 33 است، چنین عددی اول نیست.
  • باقی‌ماندهٔ 33 هم مناسب نیست؛ چون 6k+3=3(2k+1)6k+3=3(2k+1) بر 33 بخش‌پذیر است و عدد موردنظر خودِ 33 نیست.

پس برای عدد اول p>3p>3 فقط دو صورت می‌ماند: p=6k+1p=6k+1 یا p=6k+5p=6k+5.

اما حواست به جهت استدلال باشد! این قانون مثل یک صافی، بعضی عددها را حذف می‌کند؛ اول بودنِ عددهای باقی‌مانده را تضمین نمی‌کند. مثلاً 25=6×4+125=6\times4+1 از این صافی می‌گذرد، ولی چون 25=5×525=5\times5 است، اول نیست.

کتاب درسی، صفحهٔ ۱۵

الگوی مربع عددهای فرد

الگوی مربع عددهای فرد

آیا مربع همهٔ عددهای فرد، با وجود تفاوتشان، الگوی مشترکی دارد؟ برای کشف الگو، عدد فرد aa را بر 44 تقسیم می‌کنیم. باقی‌مانده فقط می‌تواند 11 یا 33 باشد؛ چون باقی‌مانده‌های 00 و 22 عددی زوج می‌سازند. پس برای یک عدد صحیح kk، دو حالت داریم:

حالت اول: اگر a=4k+1a=4k+1 باشد، آنگاه:

a2=(4k+1)2=16k2+8k+1=8(2k2+k)+1a^2=(4k+1)^2=16k^2+8k+1=8(2k^2+k)+1

حالت دوم: اگر a=4k+3a=4k+3 باشد، آنگاه:

a2=(4k+3)2=16k2+24k+9=8(2k2+3k+1)+1a^2=(4k+3)^2=16k^2+24k+9=8(2k^2+3k+1)+1

در هر دو حالت، عبارت داخل پرانتز عددی صحیح است؛ پس مربع عدد فرد به شکل 8t+18t+1 نوشته می‌شود که tt صحیح است. چون 0≤1<80\leq1<8، باقی‌ماندهٔ تقسیم مربع هر عدد فرد بر 88 برابر 11 است. این استدلال عددهای فرد منفی را هم پوشش می‌دهد؛ چون از ابتدا aa را هر عدد صحیح فردی گرفتیم.

کتاب درسی، صفحهٔ ۱۵

مثال حل‌شده

باقی‌ماندهٔ تقسیم اعداد صحیح mm و nn بر 1111 به‌ترتیب 33 و 77 است؛ باقی‌ماندهٔ تقسیم 2m−3n2m-3n بر 1111 را پیدا کن.

  1. طبق قضیهٔ تقسیم، برای عددهای صحیحی مانند uu و vv داریم: m=11u+3m=11u+3 و n=11v+7n=11v+7.

  2. این دو نمایش را جای‌گذاری می‌کنیم: 2m−3n=2(11u+3)−3(11v+7)2m-3n=2(11u+3)-3(11v+7).

  3. مضرب‌های 1111 را جدا می‌کنیم: 2m−3n=11(2u−3v)−152m-3n=11(2u-3v)-15؛ مقدار −15-15 هنوز باقی‌ماندهٔ مجاز نیست.

  4. می‌نویسیم −15=11(−2)+7-15=11(-2)+7؛ پس 2m−3n=11(2u−3v−2)+72m-3n=11(2u-3v-2)+7.

  5. چون 2u−3v−22u-3v-2 صحیح است و 0≤7<110\leq7<11، باقی‌ماندهٔ موردنظر 77 است.

جواب: باقی‌ماندهٔ تقسیم 2m−3n2m-3n بر 1111 برابر 77 است.

نکات مهم

  • در قضیهٔ تقسیم، نمایش a=bq+ra=bq+r برای عدد صحیح aa و عدد طبیعی bb یکتاست و باقی‌مانده باید شرط 0≤r<b0\leq r<b را داشته باشد.
  • برای یافتن باقی‌ماندهٔ ترکیب اعداد، نمایش تقسیمی آن‌ها را جای‌گذاری می‌کنیم و مقدار باقی‌مانده را به بازهٔ مجاز می‌بریم.
  • دسته‌بندی بر اساس باقی‌مانده نشان می‌دهد هر عدد اول بزرگ‌تر از 33 به شکل 6k+16k+1 یا 6k+56k+5 است، نه لزوماً برعکس، و مربع هر عدد فرد به شکل 8t+18t+1 است.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۸ · صفحهٔ ۱۵ تا ۱۸ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

افراز مجموعهٔ $\mathbb{Z}$ به کمک قضیهٔ تقسیم

در این درس یاد می‌گیری با استفاده از باقی‌مانده‌های قضیهٔ تقسیم، مجموعهٔ Z\mathbb{Z} را افراز کنی و با بررسی حالت‌های ممکن، ویژگی‌هایی دربارهٔ عددهای اول و مربع عددهای فرد ثابت کنی.

پیش از شروع

بدون حساب‌کردن مربع یک عدد فردِ خیلی بزرگ، می‌توانی بگویی باقی‌ماندهٔ تقسیم مربع آن بر 88 چیست؟

باقی‌مانده همیشه 11 است؛ بزرگی عدد هیچ تفاوتی ایجاد نمی‌کند. با دسته‌بندی عددهای صحیح بر اساس باقی‌مانده و بررسی چند حالت محدود، می‌توانیم این نتیجه را برای همهٔ عددهای فرد ثابت کنیم.

بی‌نهایت عدد، چند حالت محدود

بی‌نهایت عدد، چند حالت محدود

چطور دربارهٔ همهٔ عددهای صحیح حرف بزنیم، وقتی تعدادشان بی‌نهایت است؟ راهش این است که به‌جای خود عددها، باقی‌مانده‌هایشان را بررسی کنیم.

طبق قضیهٔ تقسیم، برای هر عدد صحیح aa و عدد طبیعیِ مثبت bb می‌توان نوشت:

a=bk+r,0≤r<ba=bk+r,\qquad 0\le r<b

در این رابطه، kk عددی صحیح است. باقی‌مانده فقط می‌تواند یکی از عددهای 0,1,…,b−10,1,\ldots,b-1 باشد؛ پس با وجود بی‌نهایت عدد صحیح، فقط bb حالت برای باقی‌مانده داریم.

مثلاً در تقسیم بر 55، هر عدد صحیح یکی از این صورت‌ها را دارد:

5k,5k+1,5k+2,5k+3,5k+45k,\quad 5k+1,\quad 5k+2,\quad 5k+3,\quad 5k+4

همین نگاه، دسته‌بندی آشنای زوج و فرد را هم می‌سازد: در تقسیم بر 22، باقی‌مانده یا 00 است یا 11؛ بنابراین هر عدد صحیح به صورت 2k2k یا 2k+12k+1 نوشته می‌شود. مثل وقتی می‌خواهی بدانی با دوتادوتا جفت‌کردن مدادها، مدادی تنها می‌ماند یا نه.

این قاعده برای عددهای منفی هم برقرار است؛ فقط یادت باشد باقی‌مانده منفی نیست و kk می‌تواند منفی باشد.

کتاب درسی، صفحهٔ ۱۵

جای عددهای اول در دسته‌ها

جای عددهای اول در دسته‌ها

فرض کن pp عددی اول و بزرگ‌تر از 33 باشد. اگر آن را بر 66 تقسیم کنیم، فقط این شش حالت را داریم؛ در همهٔ آن‌ها kk عددی صحیح است:

6k6k، 6k+16k+1، 6k+26k+2، 6k+36k+3، 6k+46k+4، 6k+56k+5.

حالا مثل یک غربال، حالت‌های ناممکن را کنار می‌گذاریم:

  • صورت‌های 6k6k، 6k+26k+2 و 6k+46k+4 زوج‌اند. چون p>3p>3 است، نمی‌تواند هم زوج باشد و هم اول.
  • صورت 6k+3=3(2k+1)6k+3=3(2k+1) بر 33 بخش‌پذیر است. چون p>3p>3 است، این حالت هم با اول‌بودن سازگار نیست.

پس فقط دو حالت ممکن می‌ماند: p=6k+1p=6k+1 یا p=6k+5p=6k+5.

اما مراقب جهت نتیجه باش! گفتیم هر عدد اولِ بزرگ‌تر از 33 یکی از این دو شکل را دارد؛ نگفتیم هر عددی با این شکل‌ها اول است. مثلاً 25=6×4+125=6\times4+1، ولی 25=5×525=5\times5 اول نیست. این دسته‌بندی بعضی عددها را از فهرست نامزدهای اول‌بودن حذف می‌کند، نه اینکه اول‌بودن بقیه را تضمین کند.

کتاب درسی، صفحهٔ ۱۵

راز مربع عددهای فرد

راز مربع عددهای فرد

برای کشف این راز، عدد صحیح و فردِ aa را بر 44 تقسیم کن. باقی‌مانده یکی از عددهای 00، 11، 22 یا 33 است. حالت‌های a=4ka=4k و a=4k+2a=4k+2 زوج‌اند؛ پس برای عدد فرد فقط دو حالت می‌ماند. در هر دو حالت، kk عددی صحیح است.

حالت اول: اگر a=4k+1a=4k+1 باشد، داریم:

a2=(4k+1)2=16k2+8k+1=8(2k2+k)+1a^2=(4k+1)^2=16k^2+8k+1=8(2k^2+k)+1

عبارت داخل پرانتز عددی صحیح است؛ پس مربع عدد، یک واحد بیشتر از مضربی از 88 است.

حالت دوم: اگر a=4k+3a=4k+3 باشد، داریم:

a2=(4k+3)2=16k2+24k+9=8(2k2+3k+1)+1a^2=(4k+3)^2=16k^2+24k+9=8(2k^2+3k+1)+1

اینجا هم همان نتیجه به دست آمد! چون همهٔ عددهای فرد را پوشش داده‌ایم، مربع هر عدد فرد در تقسیم بر 88 باقی‌ماندهٔ 11 دارد. این استدلال برای عددهای فرد منفی هم برقرار است.

پس اگر تعداد کاشی‌های یک چیدمان مربعی با ضلعِ فرد را در بسته‌های 88تایی بگذاری، دقیقاً یک کاشی اضافه می‌ماند؛ حتی بدون شمردن همهٔ کاشی‌ها.

کتاب درسی، صفحهٔ ۱۵

افراز؛ دسته‌بندی بدون جاافتادگی و هم‌پوشانی

افراز؛ هر عدد دقیقاً در یک دسته

فرض کن می‌خواهی همهٔ عددهای صحیح را در کشوهایی بچینی؛ نه عددی بیرون بماند و نه عددی هم‌زمان در دو کشو باشد. به چنین دسته‌بندی‌ای افراز می‌گوییم.

برای تقسیم بر 44، چهار کشو با برچسب‌های 00، 11، 22 و 33 داریم. در کشوی rr، عددهایی را می‌گذاریم که به صورت 4k+r4k+r نوشته می‌شوند؛ در اینجا k∈Zk\in\mathbb{Z} است.

چرا این دسته‌ها افراز می‌سازند؟

  • هیچ عددی جا نمی‌افتد: طبق قضیهٔ تقسیم، باقی‌ماندهٔ هر عدد صحیح بر 44 یکی از همین چهار مقدار است.
  • دسته‌ها هم‌پوشانی ندارند: باقی‌ماندهٔ تقسیم هر عدد بر 44 یکتاست؛ پس یک عدد نمی‌تواند در دو کشو باشد.

عددهای منفی هم جای مشخص دارند؛ مثلاً چون −5=4(−2)+3-5=4(-2)+3، عدد −5-5 در دستهٔ باقی‌ماندهٔ 33 است، نه در دسته‌ای با باقی‌ماندهٔ منفی.

این کار برای هر مقسوم‌علیه طبیعی bb شدنی است: دسته‌های باقی‌ماندهٔ 00 تا b−1b-1، مجموعهٔ Z\mathbb{Z} را افراز می‌کنند.

کتاب درسی، صفحهٔ ۱۸

مثال حل‌شده

اگر aa عددی صحیح و فرد باشد و b∣a+2b\mid a+2، باقی‌ماندهٔ تقسیم a2+b2+3a^2+b^2+3 بر 88 را بیابید.

  1. چون aa فرد است، a+2a+2 نیز فرد است. از b∣a+2b\mid a+2 می‌دانیم عدد صحیحی مانند qq وجود دارد که a+2=bqa+2=bq.

  2. عدد bb باید فرد باشد؛ زیرا اگر زوج بود، حاصل‌ضرب bqbq زوج می‌شد، در حالی که a+2a+2 فرد است.

  3. مربع هر عدد فرد در تقسیم بر 88 باقی‌ماندهٔ 11 دارد؛ پس برای عددهای صحیحی مانند uu و vv داریم: a2=8u+1a^2=8u+1 و b2=8v+1b^2=8v+1.

  4. جای‌گذاری می‌کنیم: a2+b2+3=(8u+1)+(8v+1)+3=8(u+v)+5a^2+b^2+3=(8u+1)+(8v+1)+3=8(u+v)+5.

  5. چون u+vu+v صحیح است و 0≤5<80\le 5<8، این رابطه صورت استاندارد قضیهٔ تقسیم است؛ بنابراین باقی‌مانده برابر 55 است.

جواب: باقی‌ماندهٔ تقسیم a2+b2+3a^2+b^2+3 بر 88 برابر 55 است.

نکات مهم

  • در تقسیم بر عدد طبیعی bb، باقی‌مانده‌های 00 تا b−1b-1 دسته‌هایی می‌سازند که هر عدد صحیح دقیقاً در یکی از آن‌ها قرار می‌گیرد؛ این دسته‌بندی یک افراز است.
  • هر عدد اول بزرگ‌تر از 33 به صورت 6k+16k+1 یا 6k+56k+5 نوشته می‌شود، اما داشتن این صورت‌ها برای اول‌بودن کافی نیست.
  • هر عدد صحیح فرد به صورت 4k+14k+1 یا 4k+34k+3 نوشته می‌شود و مربع آن در تقسیم بر 88 باقی‌ماندهٔ 11 دارد.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۹ · صفحهٔ ۱۸ تا ۲۴ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

درس ۳: همنهشتی در اعداد صحیح و کاربردها

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

پیش از شروع

اگر امروز شنبه باشد، بدون شمردن تک‌تک روزها چطور می‌توانی بفهمی هزار روز دیگر چه روزی از هفته است؟

روزهای هفته پس از هر هفت روز تکرار می‌شوند؛ پس فقط باقی‌ماندهٔ تقسیم هزار بر هفت اهمیت دارد. این باقی‌مانده 66 است، بنابراین هزار روز بعد، جمعه خواهد بود؛ هم‌نهشتی همین نگاه به باقی‌مانده‌ها را به یک ابزار ریاضی تبدیل می‌کند.

هم‌نهشتی؛ هم‌گروهی با باقی‌مانده‌ها

هم‌نهشتی؛ هم‌گروهی با باقی‌مانده‌ها

فرض کن مهره‌ها را در بسته‌های 44تایی می‌چینی. از 99 مهره، 11 مهره اضافه می‌ماند؛ از 1313 مهره هم همین‌طور. پس این دو عدد، با اینکه برابر نیستند، از نظر باقی‌مانده در یک گروه‌اند.

می‌گوییم 99 و 1313 به پیمانهٔ 44 هم‌نهشت‌اند و می‌نویسیم:

9≡13(mod4)9\equiv13\pmod{4}

راه دیگرِ تشخیص، بررسی تفاضل است: 9−13=−49-13=-4 مضرب 44 است. به‌طور کلی:

a≡b(modm)  ⟺  m∣(a−b)a\equiv b\pmod m\iff m\mid(a-b)

یعنی هم‌نهشتی برابر است با یکسان‌بودن باقی‌مانده‌ها، نه برابر بودن خود عددها.

همهٔ عددهایی که در تقسیم بر mm باقی‌ماندهٔ rr دارند، یک «کلاس هم‌نهشتی» می‌سازند که نمادش [r]m[r]_m است. مثلاً:

[1]4={…,−7,−3,1,5,9,13,…}[1]_4=\{\ldots,-7,-3,1,5,9,13,\ldots\}

عددهای منفی هم عضو این گروه‌اند؛ چون مثلاً −3=4(−1)+1-3=4(-1)+1. هر عدد صحیح دقیقاً در یکی از کلاس‌های باقی‌مانده به پیمانهٔ 44 قرار می‌گیرد؛ هیچ عددی هم‌زمان دو باقی‌ماندهٔ متفاوت ندارد.

کتاب درسی، صفحهٔ ۱۹

چه محاسبه‌هایی مجازند؟

چه محاسبه‌هایی مجازند؟

هم‌نهشتی شبیه تساوی است، اما همهٔ قانون‌های تساوی را ندارد! اگر a≡b(modm)a\equiv b\pmod m باشد، می‌توانیم:

  • به دو طرف یک عدد صحیح یکسان اضافه کنیم یا از آن‌ها کم کنیم؛
  • دو طرف را در یک عدد صحیح یکسان ضرب کنیم؛
  • دو طرف را به یک توان طبیعی یکسان برسانیم.

چرا؟ در هر حالت، تفاضلِ دو طرف همچنان مضربی از پیمانه می‌ماند؛ مثلاً در ضرب، تفاضل جدید c(a−b)c(a-b) است.

اگر دو رابطه پیمانهٔ یکسان داشته باشند، می‌توانیم طرف‌های متناظرشان را جمع، تفریق یا ضرب کنیم:

a≡b(modm),c≡d(modm)a\equiv b\pmod m,\quad c\equiv d\pmod m

⇒a+c≡b+d,a−c≡b−d,ac≡bd(modm)\Rightarrow a+c\equiv b+d,\quad a-c\equiv b-d,\quad ac\equiv bd\pmod m

همچنین هم‌نهشتی زنجیره می‌شود: اگر a≡b(modm)a\equiv b\pmod m و b≡c(modm)b\equiv c\pmod m، آنگاه a≡c(modm)a\equiv c\pmod m.

برای تصور جمع، دو جایگاه هم‌نام روی ساعت را در نظر بگیر؛ با جلو رفتن به‌اندازه‌ای یکسان، باز هم به جایگاه‌های هم‌نام می‌رسی.

اما مسیر برگشت همیشه مجاز نیست! از هم‌نهشتیِ حاصل‌ضرب‌ها نمی‌توان بی‌شرط عامل مشترک را حذف کرد؛ از هم‌نهشتیِ توان‌ها هم نمی‌توان هم‌نهشتیِ پایه‌ها را نتیجه گرفت.

کتاب درسی، صفحهٔ ۲۰

ساده‌سازی، با احتیاط در تقسیم

ساده‌سازی، با احتیاط در تقسیم

برای محاسبهٔ باقی‌مانده، لازم نیست عددهای بزرگ را با خودمان حمل کنیم؛ می‌توانیم آن‌ها را با عددهای هم‌نهشتِ ساده‌تر جایگزین کنیم. همچنین افزودن یا کم‌کردن هر مضربِ پیمانه، حتی فقط از یک طرف، هم‌نهشتی را حفظ می‌کند؛ چون باقی‌مانده تغییر نمی‌کند. درست مثل روزهای هفته که حذف چند هفتهٔ کامل، روز هفته را عوض نمی‌کند.

اما حذف عامل مشترک، مثل تقسیم در تساوی نیست! اگر

ac≡bc(modm)ac\equiv bc\pmod m

و d=gcd⁡(c,m)d=\gcd(c,m) باشد، با حذف عاملِ cc داریم:

a≡b(modm/d)a\equiv b\pmod{m/d}

یعنی باید پیمانه را هم بر ب‌م‌مِ عامل حذف‌شده و پیمانه تقسیم کنیم. فقط وقتی gcd⁡(c,m)=1\gcd(c,m)=1 است، پیمانه بدون تغییر می‌ماند.

در پایان هم بین «یک عدد هم‌نهشت» و «باقی‌ماندهٔ تقسیم» فرق بگذار: عدد هم‌نهشت می‌تواند منفی باشد، اما باقی‌مانده باید در بازهٔ 0≤r<m0\le r<m قرار بگیرد. اگر نتیجه منفی شد، با افزودن مضرب مناسبی از پیمانه آن را به این بازه برسان.

کتاب درسی، صفحهٔ ۲۲

راز قاعده‌های بخش‌پذیری

راز قاعده‌های بخش‌پذیری

چرا برای بخش‌پذیری بر 99 رقم‌ها را جمع می‌کنیم؟ راز آن در بسط ده‌دهی است: هر رقم در توانی از 1010 ضرب می‌شود، مثل A=100a+10b+cA=100a+10b+c.

برای پیمانه‌های 33 و 99، داریم 10≡110\equiv1؛ پس همهٔ توان‌های 1010 هم با 11 هم‌نهشت‌اند. بنابراین عدد با مجموع ارقامش هم‌نهشت است. دقت کن: خودِ مجموع ارقام لزوماً باقی‌مانده نیست؛ باید باقی‌ماندهٔ تقسیم آن مجموع بر پیمانه را پیدا کنی.

برای پیمانهٔ 1111، چون 10≡−1(mod11)10\equiv-1\pmod{11}، توان‌های زوجِ 1010 با 11 و توان‌های فرد با −1-1 هم‌نهشت‌اند. پس از یکان با علامت مثبت شروع کن و رقم‌ها را یکی‌درمیان کم و زیاد کن. مثلاً برای عدد سه‌رقمی بالا، A≡c−b+a(mod11)A\equiv c-b+a\pmod{11}. اگر حاصل منفی شد، آن را به باقی‌مانده‌ای در بازهٔ 0≤r<110\le r<11 تبدیل کن.

برای پیمانه‌های 22، 55 و 1010، همهٔ توان‌های مثبتِ 1010 با صفر هم‌نهشت‌اند؛ فقط رقم یکان می‌ماند. البته برای 22 و 55، باید باقی‌ماندهٔ تقسیم یکان را بگیری. در همهٔ این روش‌ها، باقی‌ماندهٔ صفر یعنی عدد بخش‌پذیر است.

کتاب درسی، صفحهٔ ۲۳

از تقویم تا معادلهٔ هم‌نهشتی

از تقویم تا معادلهٔ هم‌نهشتی

برای پیدا کردن روز هفته، لازم نیست روزها را یکی‌یکی بشماری؛ هر هفته یک چرخهٔ 77 روزه است. پس اگر فاصلهٔ دو تاریخ dd روز باشد، کافی است باقی‌ماندهٔ تقسیم dd بر 77 را پیدا کنی و به همان اندازه از روز آغاز جلو بروی. هفته‌های کامل روز هفته را تغییر نمی‌دهند. دقت کن که روز آغاز، فاصلهٔ صفر دارد؛ فردای آن، یک روز فاصله دارد.

حالا جهت سؤال را عوض کنیم: به‌جای اینکه بپرسیم «بعد از چند روز، چه روزی است؟»، می‌توانیم بپرسیم «چه فاصله‌هایی ما را به روز دلخواه می‌رسانند؟» اینجا یک مجهول وارد رابطه می‌شود.

به رابطه‌ای مانند ax≡b(modm)ax\equiv b\pmod m، معادلهٔ هم‌نهشتی می‌گوییم. حل آن یعنی پیدا کردن همهٔ عددهای صحیح xx که رابطه را درست می‌کنند؛ نه فقط یک عدد. معیار بررسی هر پاسخ هم همان تعریف آشناست: باید m∣(ax−b)m\mid(ax-b) برقرار باشد. در مسئلهٔ تقویمی، از میان جواب‌های صحیح، فاصله‌های زمانیِ مناسبِ موقعیت مسئله را در نظر می‌گیریم.

کتاب درسی، صفحهٔ ۲۴

مثال حل‌شده

بدون محاسبهٔ مقدار بزرگِ A=345×8+6A=34^5\times8+6، باقی‌ماندهٔ تقسیم آن را بر 77 پیدا کن.

  1. نمایندهٔ کوچکی برای پایه انتخاب می‌کنیم: چون 34=7×5−134=7\times5-1، داریم 34≡−1(mod7)34\equiv-1\pmod7.

  2. دو طرف را به توان می‌رسانیم: 345≡(−1)5=−1(mod7)34^5\equiv(-1)^5=-1\pmod7.

  3. در عامل بعدی ضرب می‌کنیم: 345×8≡−8(mod7)34^5\times8\equiv-8\pmod7.

  4. عدد ثابت را اضافه می‌کنیم: A≡−8+6=−2(mod7)A\equiv-8+6=-2\pmod7.

  5. نمایندهٔ منفی را به باقی‌ماندهٔ مجاز تبدیل می‌کنیم: −2+7=5-2+7=5 و 0≤5<70\le5<7؛ بنابراین باقی‌مانده 55 است.

جواب: باقی‌ماندهٔ تقسیم AA بر 77 برابر با 55 است.

نکات مهم

  • هم‌نهشتیِ a≡b(modm)a\equiv b\pmod m یعنی m∣(a−b)m\mid(a-b) و نشان می‌دهد دو عدد در تقسیم بر mm باقی‌ماندهٔ یکسان دارند.
  • جمع، تفریق، ضرب و توان طبیعی محاسبات هم‌نهشتی را ساده می‌کنند، اما هنگام حذف عامل مشترکِ cc باید پیمانه را بر gcd⁡(c,m)\gcd(c,m) تقسیم کنیم.
  • هم‌نهشتی با کوچک‌کردن عددها، محاسبهٔ باقی‌مانده و روز هفته را آسان می‌کند و حل معادلهٔ هم‌نهشتی یعنی یافتن همهٔ جواب‌های صحیح آن.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۱۰ · صفحهٔ ۲۴ تا ۲۶ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

معادلهٔ هم‌نهشتی

در این درس یاد می‌گیری … با هم‌نهشتی روز هفته را پیدا کنی، شرط وجود جواب و جواب‌های عمومی معادلهٔ هم‌نهشتی را به دست آوری و معادلهٔ سیّالهٔ خطی را به هم‌نهشتی تبدیل کنی.

پیش از شروع

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

لازم نیست روزها را یکی‌یکی بشماری؛ کافی است فاصلهٔ دو تاریخ را پیدا کنی و باقی‌ماندهٔ تقسیم آن بر 77 را به دست بیاوری. چون روزهای هفته هر 77 روز تکرار می‌شوند، فقط همین باقی‌مانده تعیین می‌کند چند روز در هفته جلو برویم.

تقویم و باقی‌مانده‌ها

تقویم و باقی‌مانده‌ها

برای پیدا کردن روز هفته، لازم نیست روزها را یکی‌یکی بشماری! روزهای هفته هر 77 روز تکرار می‌شوند؛ پس گذشت هر هفتهٔ کامل، تو را دوباره به همان روز هفته می‌رساند. فقط روزهای اضافه بر هفته‌های کامل مهم‌اند.

اگر فاصلهٔ دو تاریخ dd روز باشد و d≡r(mod7)d\equiv r\pmod{7}، از روز هفتهٔ مبدأ فقط rr روز جلو می‌رویم. روز مبدأ را با 00 مشخص می‌کنیم؛ یعنی یک روز بعد از آن، شمارهٔ 11 است، نه خود آن روز.

حواست به فاصله باشد: در یک ماه، فاصلهٔ دو تاریخ برابر تفاضل شمارهٔ روزهای آن‌هاست؛ روز شروع را دوباره نمی‌شماریم. برای تاریخ‌هایی در ماه‌های متفاوت، باید تعداد روزهای ماه‌های بین آن‌ها را هم در نظر بگیریم: شش ماه نخست سال 3131 روزه‌اند و مهر تا بهمن 3030 روزه‌اند.

این روش برای پیدا کردن روز یک قرار آینده هم به کارت می‌آید: هفته‌های کامل را کنار بگذار و فقط به‌اندازهٔ باقی‌مانده جلو برو.

کتاب درسی، صفحهٔ ۲۴

از یک جواب تا همهٔ جواب‌ها

از یک جواب تا همهٔ جواب‌ها

اگر عددی برای مجهول پیدا کنی که هم‌نهشتی را درست کند، یک جواب یافته‌ای؛ اما آیا کار تمام است؟ حل معادلهٔ هم‌نهشتی یعنی پیدا کردن همهٔ جواب‌های صحیح، نه فقط یک جواب.

در رابطهٔ x≡r(modm)x\equiv r\pmod m، اختلاف xx و rr بر mm بخش‌پذیر است؛ پس این اختلاف را می‌توان به‌صورت mkmk نوشت. بنابراین:

x−r=mk⟹x=mk+r,k∈Zx-r=mk\quad\Longrightarrow\quad x=mk+r,\qquad k\in\mathbb{Z}

این عبارت را جواب عمومی می‌نامیم؛ چون با جای‌گذاری عددهای صحیح به‌جای kk، همهٔ جواب‌ها به دست می‌آیند. مثبت، صفر یا منفی بودن kk مجاز است؛ پس جواب‌های منفی را هم نباید فراموش کنیم.

مثلاً در x≡2(mod3)x\equiv2\pmod3، عددهای 22، 55 و 88 جواب‌اند، اما فهرست به همین‌ها محدود نیست: −1-1 هم جواب است، چون اختلافش با 22، یعنی −3-3، بر 33 بخش‌پذیر است. جواب عمومی، همهٔ این عددها را یک‌جا و بدون فهرست‌کردنِ بی‌پایان نشان می‌دهد.

کتاب درسی، صفحهٔ ۲۴

حذف ضریب، با احتیاط

حذف ضریب، با احتیاط

در معادلهٔ معمولی، برای تنهاکردن مجهول دو طرف را بر ضریب آن تقسیم می‌کنیم؛ اما در هم‌نهشتی باید حواسمان به پیمانه هم باشد.

اول می‌توانیم طرف دیگر را با عددی هم‌نهشت جایگزین کنیم: افزودن یا کم‌کردن مضرب‌های پیمانه، هم‌نهشتی را تغییر نمی‌دهد. این کار کمک می‌کند طرف دیگر بر ضریب مجهول بخش‌پذیر شود.

برای حذف عامل مشترک از این قاعده استفاده می‌کنیم: اگر

du≡dv(modm)du\equiv dv\pmod m

باشد، با قرار دادن g=gcd⁡(d,m)g=\gcd(d,m) داریم:

u≡v(modm/g)u\equiv v\pmod{m/g}

پس اگر عامل حذف‌شده و پیمانه نسبت به هم اول باشند، پیمانه تغییر نمی‌کند؛ وگرنه پیمانه هم باید بر بزرگ‌ترین مقسوم‌علیه مشترکشان تقسیم شود.

مثلاً از 2x≡2(mod6)2x\equiv 2\pmod 6 نتیجه می‌گیریم x≡1(mod3)x\equiv 1\pmod 3، نه لزوماً x≡1(mod6)x\equiv 1\pmod 6. برای بررسی، x=4x=4 در هم‌نهشتی اولیه صدق می‌کند، ولی با 11 به پیمانهٔ 66 هم‌نهشت نیست. حذف ضریب نباید باعث ازدست‌رفتن جواب‌ها شود.

کتاب درسی، صفحهٔ ۲۵

پیش از حل، وجود جواب

پیش از حل، وجود جواب

آیا هر معادلهٔ هم‌نهشتی حتماً جواب دارد؟ نه! پس قبل از شروع حل، بهتر است یک بررسی کوتاه انجام دهیم.

برای معادلهٔ ax≡b(modm)ax\equiv b\pmod m، ابتدا بزرگ‌ترین مقسوم‌علیه مشترکِ ضریب مجهول و پیمانه را پیدا می‌کنیم و آن را d=gcd⁡(a,m)d=\gcd(a,m) می‌نامیم. معادله دقیقاً وقتی جواب دارد که d∣bd\mid b باشد. یعنی تقسیم bb بر dd باقی‌مانده نداشته باشد.

چرا این شرط طبیعی است؟ هم‌نهشتی می‌گوید ax−bax-b مضربی از mm است؛ پس برای عدد صحیحی مانند tt داریم ax−b=mtax-b=mt. چون dd هم aa و هم mm را تقسیم می‌کند، باید b=ax−mtb=ax-mt را هم تقسیم کند. قضیه تضمین می‌کند که این شرط نه‌تنها لازم، بلکه کافی هم هست.

یک حالت مهم: اگر gcd⁡(a,m)=1\gcd(a,m)=1 باشد، معادله برای هر عدد صحیحِ bb جواب دارد؛ چون 11 همهٔ اعداد صحیح را تقسیم می‌کند. یادت باشد این آزمون فقط وجود جواب را مشخص می‌کند، نه خود جواب‌ها را.

کتاب درسی، صفحهٔ ۲۵

از دو مجهول به هم‌نهشتی

از دو مجهول به هم‌نهشتی

فرض کن می‌خواهی با وزنه‌های 44 و 33 کیلوگرمی، یک کیسهٔ 1919 کیلوگرمی را وزن کنی. اگر تعداد وزنه‌ها را xx و yy بنامیم، رابطهٔ 4x+3y=194x+3y=19 به دست می‌آید. وقتی جواب‌های صحیح چنین معادله‌ای را می‌خواهیم، با معادلهٔ سیّالهٔ خطی سروکار داریم.

چطور دو مجهول را به یکی تبدیل کنیم؟ در رابطهٔ ax+by=cax+by=c، عبارت c−axc-ax برابر با byby است؛ پس بر bb بخش‌پذیر است. بنابراین، اگر b≠0b\ne0 باشد، می‌نویسیم:

ax≡c(mod∣b∣)ax\equiv c\pmod{|b|}

قدر مطلق را می‌گذاریم تا پیمانه مثبت باشد. پس از یافتن xx، مجهول دیگر از رابطهٔ y=c−axby=\frac{c-ax}{b} به دست می‌آید؛ هم‌نهشتی تضمین می‌کند که این مقدار صحیح است.

اما صحیح‌بودن همیشه کافی نیست! در مسئلهٔ وزنه‌ها، تعداد منفی معنا ندارد؛ بنابراین باید x≥0x\ge0 و y≥0y\ge0 را هم بررسی کنیم. همچنین، وجود جواب صحیح برای معادلهٔ سیّاله دقیقاً به شرط gcd⁡(a,b)∣c\gcd(a,b)\mid c بستگی دارد؛ این شرط به‌تنهایی وجود جواب نامنفی را تضمین نمی‌کند.

کتاب درسی، صفحهٔ ۲۶

مثال حل‌شده

برای آماده‌کردن مجموعه‌ای شامل 4545 مداد، بسته‌های 66تایی و 99تایی در اختیار داریم. اگر xx تعداد بسته‌های 66تایی و yy تعداد بسته‌های 99تایی باشد، همهٔ حالت‌های ممکن را پیدا کن؛ استفاده‌نکردن از یکی از انواع بسته‌ها مجاز است.

  1. مدل مسئله 6x+9y=456x+9y=45 است و چون مجهول‌ها تعداد بسته‌اند، باید x,y∈Zx,y\in\mathbb{Z} و x,y≥0x,y\ge0 باشند.

  2. ابتدا وجود جواب صحیح را بررسی می‌کنیم: gcd⁡(6,9)=3\gcd(6,9)=3 و 3∣453\mid45؛ پس معادله جواب صحیح دارد.

  3. با درنظرگرفتن پیمانهٔ 99، جملهٔ 9y9y کنار می‌رود و می‌نویسیم: 6x≡45(mod9)6x\equiv45\pmod9.

  4. عامل مشترک 33 را حذف می‌کنیم و پیمانه را نیز بر 33 تقسیم می‌کنیم: 2x≡15(mod3)2x\equiv15\pmod3، پس 2x≡0(mod3)2x\equiv0\pmod3. چون gcd⁡(2,3)=1\gcd(2,3)=1، نتیجه می‌شود x≡0(mod3)x\equiv0\pmod3 و بنابراین x=3kx=3k با k∈Zk\in\mathbb{Z}.

  5. در معادلهٔ اصلی جای‌گذاری می‌کنیم: 18k+9y=4518k+9y=45؛ پس y=5−2ky=5-2k. اکنون شرط‌های 3k≥03k\ge0 و 5−2k≥05-2k\ge0 می‌دهند 0≤k≤520\le k\le\frac52؛ بنابراین k∈{0,1,2}k\in\{0,1,2\}.

  6. با جای‌گذاری این مقدارها، حالت‌های ممکن عبارت‌اند از (x,y)=(0,5),(3,3),(6,1)(x,y)=(0,5),(3,3),(6,1)؛ مثلاً برای حالت میانی، 6×3+9×3=456\times3+9\times3=45 است.

جواب: همهٔ جواب‌های صحیح معادله به‌صورت x=3kx=3k و y=5−2ky=5-2k با k∈Zk\in\mathbb{Z} هستند؛ برای تعداد بسته‌ها فقط (x,y)=(0,5),(3,3),(6,1)(x,y)=(0,5),(3,3),(6,1) پذیرفتنی است.

نکات مهم

  • برای پیدا کردن روز هفته، از روز مبدأ به‌اندازهٔ باقی‌ماندهٔ تقسیم فاصلهٔ روزها بر 77 جلو می‌رویم.
  • معادلهٔ ax≡b(modm)ax\equiv b\pmod m دقیقاً وقتی جواب دارد که gcd⁡(a,m)∣b\gcd(a,m)\mid b؛ هنگام حذف عامل مشترک باید پیمانه را هم طبق قاعده ساده کنیم و همهٔ جواب‌ها را بنویسیم.
  • معادلهٔ سیّالهٔ ax+by=cax+by=c با b≠0b\ne0 به ax≡c(mod∣b∣)ax\equiv c\pmod{|b|} تبدیل می‌شود و در مسئله‌های شمارشی باید نامنفی‌بودن جواب‌ها را نیز بررسی کنیم.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس ۱۱ · صفحهٔ ۲۶ تا ۳۰ · حدود ۱۵ دقیقه · تولید هوش مصنوعی

حل معادلات سیّاله و کاربردهای آن

در این درس یاد می‌گیری … معادلهٔ سیّالهٔ خطی را به هم‌نهشتی تبدیل کنی، امکان وجود جواب صحیح را بسنجی، جواب‌های عمومی را بیابی و با اعمال محدودیت‌های مسئله، حالت‌های مجاز را بشماری.

پیش از شروع

چرا می‌توان یک کیسهٔ 1919 کیلویی را با وزنه‌های 33 و 44 کیلویی وزن کرد، اما با وزنه‌های 22 و 44 کیلویی نمی‌توان؟

با یک وزنهٔ 44 کیلویی و پنج وزنهٔ 33 کیلویی، مجموع جرم وزنه‌ها 1919 کیلوگرم می‌شود. اما هر ترکیبی از وزنه‌های 22 و 44 کیلویی جرمی زوج دارد و نمی‌تواند برابر با 1919 شود. قرار است همین فکر را به روشی منظم برای پیدا کردن جواب‌های صحیح و شمردن حالت‌های ممکن تبدیل کنیم.

جواب صحیح یعنی چه؟

جواب صحیح یعنی چه؟

فرض کن می‌خواهی یک کیسهٔ 1919 کیلویی را با وزنه‌های 44 و 33 کیلویی وزن کنی؛ وزنه‌ها را همگی در کفهٔ مقابل کیسه می‌گذاری. اگر تعداد وزنه‌های این دو نوع را به‌ترتیب xx و yy بنامیم، باید داشته باشیم: 4x+3y=194x+3y=19.

اما هر جوابی برای این مسئله معنی ندارد! مثلاً تعداد وزنه نمی‌تواند کسری یا منفی باشد.

معادلهٔ سیّالهٔ خطی معادله‌ای به شکل ax+by=cax+by=c با ضرایب صحیح است که در آن دنبال مقدارهای صحیح برای xx و yy هستیم. پس در خودِ معادله، جواب منفی هم پذیرفتنی است، به شرط آنکه تساوی را برقرار کند.

در مسئله‌های شمارشی، یک شرط دیگر اضافه می‌شود: چون مجهول‌ها تعداد وزنه، اسکناس یا غذا هستند، باید صحیح و نامنفی باشند؛ یعنی از مجموعهٔ {0,1,2,…}\{0,1,2,\ldots\} انتخاب شوند. صفر هم مجاز است، مگر صورت مسئله استفاده از هر دو نوع را الزامی کرده باشد.

پس همیشه بپرس: «فقط جواب صحیح می‌خواهم، یا جوابِ قابل‌قبول برای یک موقعیت واقعی؟»

کتاب درسی، صفحهٔ ۲۶

از دو مجهول به یک مجهول

از دو مجهول به یک مجهول

چطور یکی از دو مجهول را موقتاً کنار بگذاریم؟ پیمانه را طوری انتخاب می‌کنیم که یکی از جمله‌ها مضرب آن باشد. باقی‌ماندهٔ آن جمله صفر می‌شود و دیگر در هم‌نهشتی دیده نمی‌شود.

در معادلهٔ ax+by=cax+by=c، جملهٔ byby بر ∣b∣|b| بخش‌پذیر است؛ پس اگر b≠0b\ne0 باشد، داریم:

ax≡c(mod∣b∣)ax\equiv c\pmod{|b|}

همین نتیجه را از ax−c=−byax-c=-by هم می‌توان فهمید: اختلافِ axax و cc مضربِ ∣b∣|b| است.

اگر بخواهیم به‌جای yy، مجهول xx را کنار بگذاریم، برای a≠0a\ne0 پیمانهٔ ∣a∣|a| را می‌گیریم:

by≡c(mod∣a∣)by\equiv c\pmod{|a|}

مثلاً در مسئلهٔ وزنه‌ها، از 4x+3y=194x+3y=19 با گرفتن پیمانهٔ 33 به 4x≡19(mod3)4x\equiv19\pmod{3} می‌رسیم؛ چون 3y3y هرچه باشد، مضربِ 33 است.

دقت کن: جملهٔ دوم را دلخواه پاک نکرده‌ایم؛ باقی‌مانده‌اش در پیمانهٔ انتخاب‌شده صفر است. قدرمطلق هم باعث می‌شود پیمانه مثبت باشد.

کتاب درسی، صفحهٔ ۲۶

پیش از حل، امکانش را بسنج

پیش از حل، امکانش را بسنج

قبل از حل هم‌نهشتی، یک بررسی کوتاه انجام بده: ب.م.مِ ضرایب باید عدد سمت راست را تقسیم کند. اگر d=gcd⁡(a,b)d=\gcd(a,b) باشد، معادلهٔ ax+by=cax+by=c دقیقاً وقتی جواب صحیح دارد که d∣cd\mid c.

چرا این شرط لازم است؟ چون aa و bb هر دو مضرب dd هستند، برای هر دو عدد صحیح xx و yy، مجموع ax+byax+by هم مضرب dd است. پس اگر cc مضرب dd نباشد، جست‌وجوی جواب بی‌فایده است! قضیه تضمین می‌کند که اگر این بخش‌پذیری برقرار باشد، دست‌کم یک جواب صحیح وجود دارد.

مثلاً با وزنه‌های 22 و 44 کیلویی نمی‌توان کیسهٔ 1919 کیلویی را وزن کرد؛ چون ب.م.مِ ضرایب، 22 است و 2∤192\nmid19.

اما جواب صحیح لزوماً جواب نامنفی نیست. این آزمون اجازه می‌دهد مجهول‌ها منفی هم باشند؛ بنابراین در مسئلهٔ تعداد وزنه یا اسکناس، پس از آن باید نامنفی بودن جواب‌ها را جداگانه بررسی کنیم.

کتاب درسی، صفحهٔ ۲۶

ساختن جواب‌های عمومی

ساختن جواب‌های عمومی

حل هم‌نهشتی پایان کار نیست؛ هنوز باید هر دو مجهول را پیدا کنیم. اگر از حل هم‌نهشتی به x≡r(modm)x\equiv r\pmod m برسیم، یعنی همهٔ مقدارهای ممکنِ مجهول اول به شکل x=mk+rx=mk+r هستند، که در آن k∈Zk\in\mathbb{Z} است. پارامتر kk مثل یک گردونه عمل می‌کند: با تغییر آن، جواب‌های مختلف ساخته می‌شوند.

حالا این عبارت را در معادلهٔ اصلی جای‌گذاری می‌کنیم و مجهول دوم را هم برحسب همان kk به دست می‌آوریم. برای معادلهٔ ax+by=cax+by=c، وقتی b≠0b\ne0 باشد، داریم:

y=c−a(mk+r)by=\dfrac{c-a(mk+r)}{b}

عبارت را ساده می‌کنیم و دو رابطهٔ حاصل برای xx و yy را کنار هم می‌نویسیم؛ این‌ها جواب‌های عمومی‌اند. دقت کن که در هر زوج جواب، مقدار kk در هر دو رابطه باید یکسان باشد؛ نمی‌توان دو مقدار دلخواه و مستقل انتخاب کرد.

فعلاً kk هر عدد صحیحی است؛ اگر مسئله دربارهٔ تعداد اشیا باشد، محدودیت‌های آن را در گام بعد بررسی می‌کنیم.

کتاب درسی، صفحهٔ ۲۷

از جواب عمومی تا حالت‌های مجاز

از جواب عمومی تا حالت‌های مجاز

جواب عمومی همهٔ جواب‌های صحیح را نشان می‌دهد، اما همهٔ آن‌ها لزوماً در مسئله پذیرفتنی نیستند. مثلاً تعداد وزنه یا اسکناس نمی‌تواند منفی باشد؛ پس باید شرط‌های x≥0x\geq0 و y≥0y\geq0 را هم اعمال کنیم. صفر را حذف نکن: استفاده نکردن از یک نوع وزنه هم می‌تواند مجاز باشد.

برای انتخاب جواب‌ها، این مسیر را برو:

  • نامنفی بودن هر مجهول را به یک نامساوی برای kk تبدیل کن.
  • مقدارهای صحیح kk را که هر دو نامساوی را هم‌زمان برقرار می‌کنند، نگه دار.
  • اگر مسئله شرط دیگری دارد، آن را هم بررسی کن؛ مثلاً «کمتر از 1515 تیر» یعنی x+y<15x+y<15، نه x+y≤15x+y\leq15.

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

کتاب درسی، صفحهٔ ۲۷

مثال حل‌شده

به چند طریق می‌توان 2900029000 تومان را به اسکناس‌های 20002000 و 50005000 تومانی تبدیل کرد؟ استفاده نکردن از یکی از دو نوع اسکناس هم مجاز است.

  1. تعداد اسکناس‌های 20002000 و 50005000 تومانی را به‌ترتیب xx و yy می‌گیریم؛ پس 2000x+5000y=290002000x+5000y=29000 و با تقسیم بر 10001000 داریم 2x+5y=292x+5y=29، با شرط‌های x,y∈Zx,y\in\mathbb{Z} و x,y≥0x,y\geq0.

  2. چون gcd⁡(2,5)=1\gcd(2,5)=1 و 1∣291\mid29، معادله جواب صحیح دارد؛ اما هنوز باید وجود و تعداد جواب‌های نامنفی را بررسی کنیم.

  3. به پیمانهٔ 55 می‌نویسیم: 2x≡29≡4(mod5)2x\equiv29\equiv4\pmod{5}. چون 22 و 55 نسبت به هم اول‌اند، نتیجه می‌شود x≡2(mod5)x\equiv2\pmod{5}؛ بنابراین x=5k+2x=5k+2 و k∈Zk\in\mathbb{Z}.

  4. در معادلهٔ اصلی جای‌گذاری می‌کنیم: 2(5k+2)+5y=292(5k+2)+5y=29؛ پس 10k+5y=2510k+5y=25 و در نتیجه y=5−2ky=5-2k.

  5. نامنفی بودن تعدادها می‌دهد: 5k+2≥05k+2\geq0 و 5−2k≥05-2k\geq0؛ یعنی k≥−25k\geq-\frac{2}{5} و k≤52k\leq\frac{5}{2}. پس مقدارهای صحیح مجاز فقط k∈{0,1,2}k\in\{0,1,2\} هستند.

  6. با جای‌گذاری این مقدارها، زوج‌های (x,y)(x,y) برابر با (2,5)(2,5)، (7,3)(7,3) و (12,1)(12,1) می‌شوند؛ بنابراین سه روش وجود دارد.

جواب: به سه طریق: 22 اسکناسِ 20002000 تومانی و 55 اسکناسِ 50005000 تومانی؛ 77 اسکناسِ 20002000 تومانی و 33 اسکناسِ 50005000 تومانی؛ یا 1212 اسکناسِ 20002000 تومانی و 11 اسکناسِ 50005000 تومانی.

نکات مهم

  • در معادلهٔ سیّاله به دنبال جواب صحیح هستیم و وجود چنین جوابی برای ax+by=cax+by=c با شرط gcd⁡(a,b)∣c\gcd(a,b)\mid c سنجیده می‌شود.
  • با انتخاب پیمانهٔ ناصفرِ ∣b∣|b|، هم‌نهشتیِ ax≡c(mod∣b∣)ax\equiv c\pmod{|b|} را حل می‌کنیم و سپس با جای‌گذاری، جواب‌های عمومی هر دو مجهول را با یک پارامتر صحیح می‌نویسیم.
  • در مسئله‌های شمارشی، فقط مقدارهای صحیح پارامتر را می‌پذیریم که نامنفی بودن تعدادها و همهٔ محدودیت‌های مسئله را برقرار کنند.

تمرین تعاملی این درس (رایگان)تمرین تعاملی این درس

درس‌های فصل ۱ را تعاملی بخوان

در پنل یادگیری 1xAi هر کدام از این درس‌ها قدم به قدم پیش می‌رود: بعد از هر بخش یک سوال کوتاه، بعد مثال حل‌شده و در پایان برگهٔ خروج. جوابت ثبت می‌شود و سوال‌های هر درس در روزهای بعد برای مرور برمی‌گردند. درس‌های تعاملی رایگان‌اند؛ فقط تصحیح پاسخ کوتاه سهمیهٔ روزانهٔ رایگان دارد.

ساختن حساب رایگان است و بعد از ثبت‌نام مستقیم به همین بخش از پنل برمی‌گردی.

فصل ۱ ریاضیات گسسته دوازدهم · رایگان