شمارنده‌ها و اعداد اول — ریاضی تیزهوشان هفتم (استعداد درخشان)

شمارنده‌ها و اعداد اول (ریاضی تیزهوشان هفتم)

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

قرارداد نماد: ب.م.م دو عدد $a$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $b$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی را $(a,b)$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و ک.م.م آن‌ها را $[a,b]$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی می‌نویسیم.

یک درس از گفتگوی ابتدای فصل

نقل است که ریاضی‌دانی بزرگ در یک سخنرانی عدد ۵۱ را مثال عدد اول زد، در حالی که $51=3\times17$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. حتی متخصص‌ها هم وقتی ذهنشان درگیر بحث سنگین است اشتباه ساده می‌کنند؛ پس همیشه حدس‌هایت را وارسی کن. وارسی ۵۱ ساده است: مجموع رقم‌هایش $6$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است و بر $3$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی بخش‌پذیر است.

تعریف‌های پایه

• شمارندهٔ $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی: عدد طبیعی‌ای که $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی را بدون باقی‌مانده بشمارد؛ شمارنده‌های $12$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی عبارت‌اند از $1,2,3,4,6,12$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.
• عدد اول: عدد طبیعی بزرگ‌تر از ۱ که فقط دو شمارنده دارد: ۱ و خودش.
• عدد مرکب: عدد بزرگ‌تر از ۱ که اول نیست.
• عدد ۱ نه اول است و نه مرکب، و ۲ تنها عدد اول زوج است.

آزمون اول بودن و قاعده‌های بخش‌پذیری

برای اینکه بفهمی $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی اول است یا نه، کافی است بخش‌پذیری آن را فقط بر عددهای اولِ کوچک‌تر یا مساوی $\sqrt n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی امتحان کنی. برای $97$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی چون $\sqrt{97}<10$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی، فقط $2,3,5,7$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی را امتحان می‌کنیم و هیچ‌کدام نمی‌شمارند؛ پس ۹۷ اول است.

دام‌های معروف: عددهایی مثل $91=7\times13$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی، $87=3\times29$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی، $119=7\times17$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $221=13\times17$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی ظاهر «اول» دارند ولی مرکب‌اند.

غربال اراتستن

برای پیدا کردن همهٔ عددهای اول تا ۱۰۰: عدد ۱ را خط بزن؛ ۲ را نگه دار و مضرب‌هایش را خط بزن؛ کوچک‌ترین عدد خط‌نخورده (۳) را نگه دار و مضرب‌هایش را خط بزن؛ همین کار را تا ۷ ادامه بده، چون $11^2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی از ۱۰۰ بزرگ‌تر است. عددهای باقی‌مانده اول‌اند و تا ۱۰۰ دقیقاً ۲۵ عدد اول وجود دارد.

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

قضیهٔ اساسی حساب: هر عدد مرکب فقط به یک شکل (صرف‌نظر از ترتیب) حاصل‌ضرب عددهای اول است:

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

تعداد شمارنده‌ها: اگر $n=p_1^{a_1}\times p_2^{a_2}\times\cdots$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی باشد، تعداد شمارنده‌ها برابر $(a_1+1)(a_2+1)\cdots$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است. مثلاً $360$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی دارای $4\times3\times2=24$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی شمارنده است. بین عددهای تا ۱۰۰، بیشترین تعداد شمارنده ۱۲ است که عددهای $60,72,84,90,96$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی آن را دارند.

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

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

$(a,b)$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی بزرگ‌ترین عددی است که هر دو عدد را می‌شمارد. سه روش:

1. فهرست شمارنده‌ها: شمارنده‌های هر دو را بنویس و بزرگ‌ترین مشترک را بردار.
2. تجزیه: عامل‌های اولِ مشترک را با کمترین توان در هم ضرب کن: از $12=2^2\times3$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $18=2\times3^2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نتیجه می‌شود $(12,18)=6$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.
3. الگوریتم اقلیدس: $(a,b)=(b,\ r)$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی که $r$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی باقی‌ماندهٔ تقسیم $a$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی بر $b$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است؛ این کار را تا رسیدن به باقی‌ماندهٔ صفر ادامه بده.

دو عدد را نسبت به هم اول می‌گوییم اگر ب.م.م آن‌ها ۱ باشد. کسری ساده‌نشدنی است که ب.م.م صورت و مخرجش ۱ باشد.

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

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

$[a,b]$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی کوچک‌ترین عدد طبیعی است که مضرب هر دو باشد. با تجزیه، همهٔ عامل‌های اول را با بیشترین توان در هم ضرب کن: $[12,18]=2^2\times3^2=36$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

رابطهٔ طلایی برای دو عدد:

این رابطه فقط برای دو عدد برقرار است، نه سه عدد.

کدام را کجا به کار ببریم؟

درست یا نادرست؟ ب.م.م دو عدد زوج همیشه زوج است، چون ۲ شمارندهٔ مشترک آن‌هاست. ب.م.م دو عدد فرد همیشه فرد است، چون عدد فرد شمارندهٔ زوج ندارد. ولی ب.م.م یک عدد زوج و یک عدد فرد لزوماً زوج نیست؛ مثلاً $(6,9)=3$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. چنین استدلال‌های کوتاهی در امتحان‌های تشریحیِ تیزهوشان زیاد پرسیده می‌شود.

مسئلهٔ حوض‌ها: برای پیدا کردن بزرگ‌ترین سطلی که چند حوض با حجم‌های $870$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $899$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $928$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی لیتر را دقیق پر کند، به‌جای تجزیهٔ هر سه عدد، به تفاضل‌ها نگاه کن: هر شمارندهٔ مشترک، تفاضل‌ها را هم می‌شمارد و تفاضل‌ها هر دو $29$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است.

نمونه: دو چراغ که هر ۶ و هر ۸ ثانیه چشمک می‌زنند، بعد از $[6,8]=24$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی ثانیه دوباره با هم روشن می‌شوند. اگر عددی بر $2,3,4,7,8$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی به ترتیب باقی‌ماندهٔ $1,2,3,6,7$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی بدهد، یعنی یکی بیشتر از آن بر همهٔ این عددها بخش‌پذیر است؛ این نوع «یکی کم» را در مسئله‌ها زیاد می‌بینی.

نمودار شمارنده‌ها و خاصیت تعدی

اگر از $a$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی به $b$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی پیکان بکشیم هرگاه $a$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی شمارندهٔ $b$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی باشد، یک قانون همیشه برقرار است: اگر $a$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی شمارندهٔ $b$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $b$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی شمارندهٔ $c$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی باشد، $a$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی هم شمارندهٔ $c$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است. به این خاصیت تعدی می‌گویند. پس نموداری که در آن از $a$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی به $b$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و از $b$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی به $c$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی پیکان هست ولی از $a$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی به $c$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نیست، برای هیچ سه عددی ساخته نمی‌شود. در مسئله‌های مسیریابی روی جدول هم (رفتن از هر خانه به خانهٔ همسایه‌ای که شمارنده یا مضرب عدد فعلی است) همین رابطه‌ها راهنمای مسیرند.

تجزیه در مسئله‌های ساختاری

تجزیه به عامل اول در مسئله‌هایی که ظاهرشان ربطی به عددهای اول ندارد هم کلید حل است:

• مکعب‌مستطیل از مکعب‌های کوچک: اگر از یک وجه ۷۷ مکعب برداشته شود، چون $77=7\times11$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی، ابعاد آن وجه $7$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $11$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است.
• عامل‌های اول به‌عنوان «بچه‌ها»ی یک عدد: $144=2^4\times3^2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی شش عامل اول (با تکرار) دارد. اگر بخواهیم عددی دو جفت عامل یکسان داشته باشد، باید به شکل $p^2q^2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی باشد؛ تنها عدد دورقمی از این نوع $36$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است.
• حاصل‌ضرب‌های برابر: وقتی دو گروه عدد حاصل‌ضرب برابر دارند، هر دو طرف را تجزیه کن و عامل‌های اول را برابر بگذار؛ عدد مجهول از عامل‌های باقی‌مانده پیدا می‌شود.
• جدا کردن عامل‌ها: اگر $500=2^2\times5^3$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی را به دو عدد بشکنیم که هیچ‌کدام بر ۱۰ بخش‌پذیر نباشد، باید همهٔ ۲ها در یک عدد و همهٔ ۵ها در عدد دیگر باشند؛ پس جواب $4$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $125$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است.

ب.م.م و ک.م.م کسرها

برای دو کسر ساده‌نشدنی مثل $\frac{2}{39}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و $\frac{3}{26}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی:

• کوچک‌ترین کسری که بر هر دو بخش‌پذیر باشد (حاصل تقسیمش بر هر دو عدد طبیعی شود) برابر است با ک.م.م صورت‌ها تقسیم بر ب.م.م مخرج‌ها: $\frac{6}{13}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.
• بزرگ‌ترین کسری که هر دو کسر بر آن بخش‌پذیر باشند برابر است با ب.م.م صورت‌ها تقسیم بر ک.م.م مخرج‌ها: $\frac{1}{78}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

کسرهای واحد و مثلث لایب‌نیتس

کسرهایی با صورت ۱ را کسر واحد می‌گویند. هر کسر واحد را می‌شود مجموع دو کسر واحد دیگر نوشت؛ مثلاً $\frac14=\frac15+\frac1{20}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. ایدهٔ پشت آن این تساوی است:

در مثلث هارمونیک لایب‌نیتس هم همهٔ کسرها صورت ۱ دارند و هر کسر برابر مجموع دو کسرِ زیر خودش است.

جفت عددهایی که جمع و ضربشان برابر است: اگر $xy=x+y$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی باشد، با کمی جابه‌جایی به $(x-1)(y-1)=1$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی می‌رسیم؛ پس اگر $x=1+t$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی باشد، $y=1+\frac1t$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است. مثلاً $3\times\frac32=3+\frac32$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

حرکت و هم‌رسیدن

در مسئله‌های «جهنده‌ها» که یکی از عدد ۴ با گام ۱۵ و دیگری از عدد ۱ با گام ۱۲ حرکت می‌کند، اولین نقطهٔ مشترک را با حل $4+15k=1+12m$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی پیدا کن؛ بعد از آن، نقطه‌های مشترک هر $[15,12]=60$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی واحد یک بار تکرار می‌شوند. در مسئلهٔ دو دونده روی پیست دایره‌ای هم، زمان رسیدن دوباره به نقطهٔ شروع با ک.م.م زمان یک دور هر کدام به دست می‌آید.

قضیهٔ ویلسون

اگر $p$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی اول باشد، $(p-1)!+1$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی بر $p$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی بخش‌پذیر است؛ مثلاً $6!+1=721=7\times103$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. این یکی از آزمون‌های نظری اول بودن است.

بازی‌ها و مسئله‌های ویژهٔ فصل

• بازی شمارنده‌ها: بازیکن‌ها عددی را برمی‌دارند و شمارنده‌هایش را خط می‌زنند؛ بهترین شروع عددی است که بیشترین شمارنده را دارد.
• مسابقهٔ دارت ضربی: امتیاز حاصل‌ضرب امتیاز پرتاب‌هاست و نواحی سیبل فقط $2,3,5,7$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی دارند؛ پس هر امتیازی که عامل اولِ بزرگ‌تر از ۷ داشته باشد (مثل ۲۹) غیرممکن است. تجزیه به عامل اول کلید همهٔ پرسش‌های این بازی است.
• عددهای پشت سر هم مرکب: عددهای $1001!+2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تا $1001!+1001$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی هزار عدد متوالی‌اند که هیچ‌کدام اول نیست، چون $1001!+k$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی بر $k$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی بخش‌پذیر است.
• دنبالهٔ حسابی از اول‌ها: مثلاً $5,11,17,23,29$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی پنج عدد اول با فاصلهٔ ۶ هستند.
• حدس گلدباخ: هر عدد زوج بزرگ‌تر از ۲ مجموع دو عدد اول است؛ این حدس هنوز اثبات نشده است.

اشتباه‌های رایج