عددهای اول (هشتم)

عددهای اول (هشتم)

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

عدد اول و عدد مرکب

عدد اول هر عدد طبیعیِ بزرگ‌تر از $1$ است که هیچ شمارنده‌ای جز $1$ و خودش ندارد؛ یعنی دقیقاً دو شمارنده دارد. مثلاً $7$ اول است چون فقط بر $1$ و $7$ بخش‌پذیر است.

عدد مرکب عددی است که بتوان آن را حاصل‌ضرب دو عدد طبیعیِ بزرگ‌تر از $1$ نوشت؛ یعنی بیش از دو شمارنده دارد. مثلاً $24 = 6 \times 4$.

عدد ۱ نه اول است و نه مرکب. اول نیست چون فقط یک شمارنده دارد (خودش)، و مرکب هم نیست چون به ضرب دو عدد بزرگ‌تر از $1$ نوشته نمی‌شود. پس عددهای طبیعی سه دسته می‌شوند: عدد $1$، عددهای اول، و عددهای مرکب.

یک راه شهودی برای دیدنش: اگر $6$ سرباز داشته باشی، می‌توانی آن‌ها را در آرایش‌های $1\times6$، $2\times3$، $3\times2$ و $6\times1$ بچینی. اما $5$ سرباز فقط $1\times5$ و $5\times1$ می‌شوند. عددهایی که فقط دو آرایش مستطیلی دارند، همان عددهای اول‌اند.

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

هر عدد مرکب را می‌توان به ضرب عددهای اول نوشت. روش کار ساده است: عدد را به دو عامل بشکن و این کار را ادامه بده تا همهٔ عامل‌ها اول شوند.

اگر از مسیر دیگری هم شروع کنی ($12 = 3 \times 4$)، باز به همان نتیجه می‌رسی. این همان قضیهٔ اساسی حساب است: هر عدد طبیعی بزرگ‌تر از $1$ فقط یک تجزیهٔ اول دارد. جالب است بدانی همین یکتایی دلیل اصلی است که عدد $1$ را از تعریف اول بیرون گذاشته‌اند؛ اگر $1$ اول بود، می‌شد بی‌نهایت تجزیهٔ متفاوت نوشت.

تلهٔ مهم: نوشتن $12 = 4 \times 3$ تجزیهٔ ناقص است، چون $4$ خودش مرکب است. تا وقتی همهٔ عامل‌ها اول نشده‌اند، کار تمام نیست.

عددهای نسبت به هم اول

اگر ب.م.م دو عدد برابر $1$ باشد، آن دو نسبت به هم اولاند. این مفهوم هیچ ربطی به اول بودنِ خودِ عددها ندارد.

• دو عدد اولِ متفاوت همیشه نسبت به هم اول‌اند: $\gcd(5,7)=1$.
• دو عدد مرکب هم می‌توانند نسبت به هم اول باشند: $8 = 2^3$ و $9 = 3^2$ هیچ عامل مشترکی ندارند.
• ولی $\gcd(4,6)=2$، پس $4$ و $6$ نسبت به هم اول نیستند.
• دو عدد طبیعی متوالی همیشه نسبت به هم اول‌اند، چون اختلافشان $1$ است.

یک نتیجهٔ کاربردی: اگر $\gcd(a,b)=1$ باشد، آنگاه ک.م.م آن‌ها برابر حاصل‌ضربشان است.

همین نکته در هم‌مخرج‌کردن کسرها خیلی وقت‌ها کار را کوتاه می‌کند.

روش غربال — پیدا کردن همهٔ اول‌ها

غربال یعنی عددهای غیراول را حذف کنیم تا فقط اول‌ها بمانند. برای بازهٔ $1$ تا $50$:

۱) عدد $1$ را خط بزن. ۲) $2$ را نگه دار و مضرب‌های مرکبش را خط بزن. ۳) $3$ را نگه دار و مضرب‌هایش را خط بزن. ۴) عددهایی مثل $4$ و $6$ را رها کن — قبلاً به‌عنوان مضربِ عددی کوچک‌تر خط خورده‌اند. ۵) با $5$ و $7$ همین کار را بکن.

وقتی به $11$ می‌رسی، اولین مضربِ خط‌نخورده‌اش $11 \times 11 = 121$ است که از $50$ بزرگ‌تر است، پس کار تمام است.

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

نکتهٔ ظریف: وقتی مضرب‌های عدد اولِ $p$ را خط می‌زنی، کوچک‌ترین مضربِ هنوز خط‌نخورده همیشه $p^2$ است. نام رسمی این روش غربال اراتوستنس است، به یادِ ریاضی‌دان یونانی‌ای که حدود ۲۲۰۰ سال پیش آن را ابداع کرد.

پانزده عدد اولِ کوچک‌تر از ۵۰ اینها هستند:

تشخیص اول بودن یک عدد خاص

برای بررسی عددِ $n$ لازم نیست آن را بر همهٔ عددهای کوچک‌تر تقسیم کنی. فقط دو نکته را رعایت کن:

• فقط بر عددهای اول تقسیم کن. چون هر عدد مرکب خودش از عامل‌های اول ساخته شده؛ اگر $n$ بر $2$ بخش‌پذیر نباشد، بر $4$ و $6$ و $8$ هم نیست.
• تا جایی ادامه بده که $p^2 > n$ شود (یعنی تا $\sqrt{n}$).

مثال: آیا $47$ اول است؟ چون $7^2 = 49 > 47$، کافی است بر $2, 3, 5, 7$ امتحان کنیم. هیچ‌کدام $47$ را بدون باقی‌مانده تقسیم نمی‌کنند، پس $47$ اول است.

مثال دیگر: $143$. چون $\sqrt{143} \approx 11.9$، باید تا $11$ برویم. و $143 \div 11 = 13$ بدون باقی‌مانده، پس $143 = 11 \times 13$ مرکب است.

جدول کوتاهی که وقت زیادی صرفه‌جویی می‌کند: برای عددهای کمتر از $25$ فقط $2,3$؛ کمتر از $49$ فقط $2,3,5$؛ کمتر از $100$ فقط $2,3,5,7$؛ و کمتر از $169$ تا $13$.

چک‌های سریع قبل از تقسیم

قبل از هر تقسیمی، این سه چک را انجام بده تا خیلی از عددها را فوری رد کنی:

• رقم یکان زوج یا صفر است؟ مضرب $2$ است.
• مجموع رقم‌ها بر $3$ بخش‌پذیر است؟ مضرب $3$ است. مثلاً $231$ چون $2+3+1=6$ است، مرکب است.
• رقم یکان $0$ یا $5$ است؟ مضرب $5$ است.

یک ابزار اضافی: بخش‌پذیری بر ۱۱ با تفاضل متناوب رقم‌ها. رقم‌ها را یکی‌درمیان با $+$ و $-$ جمع بزن؛ اگر نتیجه بر $11$ بخش‌پذیر شد (یا صفر شد)، خود عدد هم بخش‌پذیر است. مثلاً برای $143$: $1-4+3=0$.

هر عدد اولِ غیر از $2$ و $5$، رقم یکانش حتماً $1$، $3$، $7$ یا $9$ است — اما دقت کن که این فقط شرط لازم است، نه کافی: $91$ رقم یکانش $1$ است ولی $91 = 7 \times 13$.

نکته‌های طلایی و تله‌ها

• $2$ تنها عدد اولِ زوج است. بقیه همه فردند؛ این استثنا را فراموش نکن.
• اگر مجموع دو عدد اول فرد شد، حتماً یکی از آن‌ها $2$ است (چون جمع دو فرد، زوج می‌شود).
• هر عدد طبیعی بزرگ‌تر از $1$ حداقل یک شمارندهٔ اول دارد.
• هر مضربِ یک عدد (به‌جز خودش) حتماً مرکب است.
• عددهایی مثل $49 = 7^2$ و $51 = 3 \times 17$ ظاهر فریبنده‌ای دارند؛ اول نیستند.
• تقسیم را کامل انجام بده، نه تخمینی.

شمردن شمارنده‌ها بدون فهرست‌کردن — تکنیک محبوب سؤال‌های تیزهوشان: اگر $n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$ باشد، تعداد شمارنده‌های طبیعی $n$ برابر است با:

مثلاً $12 = 2^2 \times 3$ دارای $(2+1)(1+1) = 6$ شمارنده است: $1, 2, 3, 4, 6, 12$. درست درآمد.

چند نکتهٔ جالب

عددهای اول دوقلو دو عدد اول با اختلاف $2$ هستند: $(3,5)$، $(11,13)$، $(41,43)$. اینکه آیا بی‌نهایت جفت دوقلو وجود دارد، هنوز یکی از مسئله‌های حل‌نشدهٔ ریاضی است.

سه‌قلوها فقط یک نمونه دارند: $(3,5,7)$. دلیلش ساده است — در هر سه عدد فردِ متوالی $n, n+2, n+4$ حتماً یکی مضرب $3$ است، و اگر آن عدد از $3$ بزرگ‌تر باشد اول نیست.

حدس گلدباخ (۱۷۴۲) می‌گوید هر عدد زوجِ بزرگ‌تر از $2$ مجموع دو عدد اول است: $10 = 3+7$، $100 = 3+97$. تا عددهای بسیار بزرگ آزمایش شده و درست بوده، ولی هنوز کسی اثباتش نکرده.

و یک واقعیت مهم: عددهای اول بی‌نهایتاند — این را اقلیدس بیش از ۲۳۰۰ سال پیش اثبات کرد. امروز امنیت اینترنت (رمزنگاری) روی همین عددها بنا شده: ضرب دو عدد اولِ بزرگ آسان است، ولی تجزیهٔ حاصل به عامل‌هایش بسیار سخت.

یک نمونهٔ کوتاه

مجموع دو عدد اول برابر $99$ است. حاصل‌ضرب آن دو چند است؟

چون $99$ فرد است، طبق نکتهٔ طلایی یکی از آن دو باید $2$ باشد. پس عدد دیگر $99 - 2 = 97$ است. برای اطمینان، $97$ را بر $2, 3, 5, 7$ چک می‌کنیم (چون $7^2 = 49 < 97 < 121 = 11^2$) و هیچ‌کدام بخش‌پذیر نیست، پس $97$ اول است.

جمع‌بندی

عددهای طبیعی سه دسته‌اند: عدد $1$، عددهای اول (دقیقاً دو شمارنده) و عددهای مرکب. هر عدد مرکب یک تجزیهٔ اولِ یکتا دارد. برای پیدا کردن همهٔ اول‌های یک بازه از غربال استفاده کن و برای بررسی یک عدد خاص، فقط بر عددهای اولِ کوچک‌تر از $\sqrt{n}$ تقسیمش کن. «نسبت به هم اول» یعنی ب.م.م برابر $1$ — و این هیچ ربطی به اول بودنِ خود عددها ندارد.