عددهای اول تمام نمی‌شوند
در درس «غربال اراتستن» عددهای اول تا ۱۰۰ را پیدا کردیم: ۲۵ عدد بودند. میان ۱ و ۱۰ چهار عدد اول هست، اما میان ۹۱ و ۱۰۰ فقط یکی: ۹۷. هر چه جلوتر می‌رویم، عددهای اول کمیاب‌تر می‌شوند. پس شاید جایی در دوردست دیگر عدد اولی نباشد. آیا عدد اولِ آخری وجود دارد؟
با امتحان کردن نمی‌شود به این پرسش جواب داد، چون عددها تا بی‌نهایت ادامه دارند. یک اثبات لازم است.
از روی فهرست، عددی بسازیم
حدود ۲٬۳۰۰ سال پیش، اقلیدس، ریاضی‌دان یونانی، کتابی در ریاضی نوشت به نام اصول. این استدلال در آن کتاب آمده است. اول با عددهای کوچک دنبالش کنیم.
فرض کنید کسی می‌گوید: «تنها عددهای اول ۲ و ۳ و ۵ هستند.» همه را در هم ضرب کنید و بعد ۱ اضافه کنید:
- ۲ × ۳ × ۵ = ۳۰
- ۳۰ + ۱ = ۳۱
حالا ۳۱ را بر هر کدام از عددهای اول فهرست تقسیم کنید:
- ۳۱ ÷ ۲ = ۱۵، باقی‌مانده ۱
- ۳۱ ÷ ۳ = ۱۰، باقی‌مانده ۱
- ۳۱ ÷ ۵ = ۶، باقی‌مانده ۱
چرا باقی‌مانده همیشه ۱ است؟ چون ۳۰ مضرب ۲ است، مضرب ۳ است و مضرب ۵ هم هست. پس ۳۱ یکی بیشتر از مضربی از هر کدام از آن‌هاست و آن ۱ هر بار اضافه می‌ماند. هیچ‌کدام از عددهای اول فهرست ۳۱ را نمی‌شمارد.
در هر حال، عدد اولی تازه
در درس «نمودار درختی» دیدیم که هر عدد بزرگ‌تر از ۱ یا خودش اول است، یا می‌شود آن را به عددهای اول شکست. پس ۳۱ یا خودش عددی اول است، یا از عددهای اول ساخته شده است. اما هیچ‌کدام از این عددهای اول نمی‌تواند در فهرست باشد، چون هیچ عدد اولی از فهرست ۳۱ را نمی‌شمارد.
این‌جا ۳۱ عددی اول است و در فهرست نیست. گاهی عدد تازه اول نیست. فهرست ۲، ۳، ۵، ۷، ۱۱، ۱۳ را در نظر بگیرید:
- ۲ × ۳ × ۵ × ۷ × ۱۱ × ۱۳ = ۳۰٬۰۳۰ و ۳۰٬۰۳۰ + ۱ = ۳۰٬۰۳۱
- ۳۰٬۰۳۱ = ۵۹ × ۵۰۹، و ۵۹ و ۵۰۹ هر دو عدد اول‌اند
۵۹ و ۵۰۹ هم در فهرست نیستند. در هر حال، فهرست یک عدد اول را کم داشت.
هیچ فهرستی کامل نیست
حالا اثبات. وانمود کنید عدد اولِ آخری وجود دارد، یعنی همه‌ی عددهای اول در یک فهرست جا می‌شوند. همه‌ی عددهای فهرست را در هم ضرب کنید و ۱ اضافه کنید. همان‌طور که دیدیم، این عدد یک عدد اول با خودش می‌آورد که در فهرست نیست. اما فهرست قرار بود همه‌ی عددهای اول را داشته باشد. این ناممکن است، پس وانمود کردنمان نادرست بود: عدد اولِ آخری وجود ندارد.
به این شیوه‌ی اثبات - وانمود کنیم که عکسش درست است و دنبالش برویم تا به چیزی ناممکن برسیم - برهان خلف می‌گویند (proof by contradiction). در دوره‌ی «منطق، سطح ۲» درسی با همین نام هست که با آن نشان می‌دهد بزرگ‌ترین عدد وجود ندارد.
اقلیدس همه‌ی عددهای اول را پیدا نکرد و تا ابد هم امتحان نکرد. استدلال او برای هر فهرستی، هر قدر هم بلند، درست است؛ پس همه را یک‌جا در بر می‌گیرد.
در خانه امتحان کنید
- از فهرست ۲ و ۳ شروع کنید. در هم ضرب کنید و ۱ اضافه کنید. عدد تازه اول است؟
- همین کار را با ۲، ۳، ۵ و ۷ بکنید. امتحان کنید که عدد تازه بر هر کدام از آن‌ها تقسیم شود، باقی‌مانده ۱ می‌دهد.
جواب‌ها: ۱. ۲ × ۳ + ۱ = ۷، که اول است. ۲. ۲ × ۳ × ۵ × ۷ + ۱ = ۲۱۱، که آن هم اول است؛ ۲۱۱ ÷ ۷ = ۳۰، باقی‌مانده ۱.
واژه‌های این درس
- برهان خلف (proof by contradiction) - ثابت کردن چیزی با این‌که وانمود کنیم عکسش درست است و به چیزی ناممکن برسیم
ایده‌ی اصلی
همه‌ی عددهای اول یک فهرست را در هم ضرب کنید و ۱ اضافه کنید: عدد تازه بر هر کدام از آن‌ها تقسیم شود، باقی‌مانده ۱ می‌دهد، پس عدد اولی با خودش می‌آورد که در فهرست نیست. هیچ فهرستی نمی‌تواند همه‌ی عددهای اول را داشته باشد، پس عددهای اول هرگز تمام نمی‌شوند.