زنگ تفریح شماره83
طي قرنهاي متمادي رياضي دانان در شرق و غرب عالم به جستجوي راههايي براي دستيابي به اعداد اول برخاستهاند و با اين همه بهترين روشهايي كه تا بحال در اين زمينه ابداع شده چنان كند است كه حتي پر سرعتترين كامپيوتر هاي كنوني نيز نميتوانند كمك چنداني در شكار اين اعداد شگفت انگيز كنند.
اعداد اول بر طبق تعريف اعدادي هستند كه تنها به ۱و بر خودشان تقسيم پذيرند. به عنوان نمونه اعداد ۲،۳،۵،۷،۱۱،۱۳،۱۷،۱۹اعد اد اول كمتر از 20 در سلسله اعداد طبيعي هستند. اما هرچه در اين سلسله پيش تر برويم اعداد اول ناياب تر ميشوند.
بطوريكه اگر چندين ميليون بار به سرعت كامپيوتر هاي كنوني افزوده شود، تنها چند رقم به شماره ارقام بزرگترين عدد اولي كه تا به حال شناخته شده افزوده ميگردد.
رياضي دانان در آرزوي دست يافته به روشي هستند كه با استفاده از آن بتوانند با سرعت به يافتن اعداد اول توفيق يابند و يا اگر با عددي هر اندازه پر رقم و بزرگ روبرو شدند بتوانند با سرعت مشخص سازند كه آيا عدد اول است؟ اما يافتن چنين روشي به فسفر مغز نياز دارد و نه سرعت كامپيوتر! اما يك گروه از رياضي دانان هندي مدعي شدهاند كه در آستانه دستيابي به همان آزموني هستند كه رياضي دانان قرنها مشتاقانه در آرزويش بوده اند.
«مانيندرا اگراوال» (Manindra Agrawal) و دانشجويانش «نيراج كايال» (Neeraj Kaya) و «نيتين سكسنا» (Nitin Saxena) در موسسه تكنولوژي «كانپور» مدعي شدهاند كه در آستانه تكميل آزموني هستند كه اول بودن يا نبودن هر عدد طبيعي را با سرعت مشخص ميكند. اين آزمون در صورتي كه تكميل شود ميتواند تبعات و نتايج بسيار گستردهاي براي جهان كنوني به بار آورد.
درحال حاضر بسياري از معاملات تجاري و نقل و انتقالات مالي و نيز مبادله اطلاعات محرمانه از طريق شبكه هاي مخابراتي مانند اينترنت و با بهره گيري از رمز كردن پيامها به انجام ميرسد.
اعداد اول در تنظيم اين قبيل رمزها نقشي اساسي بر عهده دارند و از همين رو دستيابي به اعداد اول جديد كه ديگران از آن بيخبر باشند براي سازندگان اين رمزها و نيز مشتريان آنان از اهميت زياد برخوردار است.
اما اگر روش اين محققان هندي تكميل شود در آن صورت امنيت اين قبيل نقل و انتقالات در معرض خطر جدي قرار خواهد گرفت.
سابقه قرار گرفتن رياضي دانان تحت جاذبه اعداد اول به قرنها پيش باز مي گردد. در سال ۱۸۰۱ «كارل گائوس» از بزرگترين رياضي دانان اعلام كرد كه مساله تشخيص اعداد اول از اعداد غير اول يكي از مهمترين مسائل حساب به شمار ميآيد.
تلاشها برای اثبات
بعدا «وینوگرادوف» ریاضیدان روس با استفاده از روشهای هاردی ، لیتلوود و همکار هندی برجسته آنها «رامانوجان» در نظریه تحلیلی اعداد ، موفق شد تعداد عددهای اول مورد لزوم را از 300000 به 4 کاهش دهد. این نتیجه به تعداد مطلوب در انگاره گلدباخ بسیار نزدیکتر است ولی تفاوت عمدهای بین حکم «اشنیرلمان» و حکم «وینوگرادوف» وجود دارد که شاید مهمتر از اختلاف میان 300000 و 4 باشد. قضیه وینوگرادوف فقط به ازای همه اعداد صحیح «به اندازه کافی بزرگ» ثابت شده است؛ به بیان دقیقتر، او ثابت کرد عدد صحیح N ای وجود دارد به طوری که هر عدد صحیح n>N را میتوان به شکل مجموع حداکثر 4 عدد اول نشان داد. اثبات «وینوگرادوف» راهی برای براورد کردن N به ما نشان نمیدهد، و بر خلاف اثبات «اشنیرلمان»، اساساً غیرمستقیم و غیرسازنده است. در حقیقت، چیزی که وینوگرادوف ثابت کرد این است که فرض نامتناهی بودن تعداد عددهای صحیحی که قابل تجزیه به حداکثر 4 عدد اول نیستند، به نتیجه نامعقولی میانجامد. در اینجا با نمونه خوبی از تفاوت عمیق میان دو نوع اثبات، مستقیم و غیرمستقیم، رو به روییم.
در سال 1956 «باروتسکین» با نشان دادن اینکه عدد exp(exp(16/038))=n در قضیه «وینوگرادف» کافیست گام دیگری در این راه نهاد.
در 1919 «ویگوبرون» رویکرد متفاوتی با عنوان روش غربال مطرح کرد که تعمیمی از غربال اراتستن است. او ثابت کرد هر عدد صحیح زوجی که به قدر کافی بزرگ باشد ، مجموع دو عدد است که هر کدام از آنها حاصلضرب حداکثر 9 عدد اول هستند.
در 1937 «ریچی» ثابت کرد هر عدد زوجی که به قدر کافی بزرگ باشد مجموع دو عدد است که یکی حاصل ضرب حداکثر دو عدد اول و دیگری حاصلضرب حداکثر 366 عدد اول است. کُن با بهرهگیری از ایدههای ترکیبیاتی بوخشتاب ثابت کرد هر عدد زوج بقدر کافی بزرگ مجموع دو عدد است که هر یک حاصلضرب حداکثر چهار عدد اول است.
در 1957 ، «ونگ یوان» با فرض درست بودن صورت تعمیم یافته فرضیه ریمان ثابت کرد هر عدد صحیح زوج بقدر کافی بزرگ ،مجموع یک عدد اول و حاصلضرب حداکثر سه عدد اول است.
در 1948 «آلفرد» بدون استفاده از صورت تعمیم یافته فرضیه ریمان ثابت کرد که هر عدد زوج بقدر کافی بزرگ مجموع یک عدد اول و حاصلضرب حداکثر c عدد اول است. cعددی ثابت و مجهول است.
در 1961 «باربن» نشان داد که c=9 برای این منظور کفایت میکند.
در 1962 ، «پان چنگ دونگ» این مقدار را به c=5 کاهش داد. مدت کوتاهی پس از آن «باربن و پان» ، مستقل از هم ،آن را به c=4 کاهش دادند.
در 1965 «بوخشتاب» این قضیه را به ازای c=3 کاهش داد.
در 1966 ، «چن جینگ ران» روش غربال را بهتر کرد و قضیه را به ازای c=2 ثابت کرد. یعنی هر عدد صحیح زوجی که به قدر کافی بزرگ باشد ، مجموع یک عدد اول و حاصلضرب حداکثر دو عدد اول است.
اعداد اول به يك معنا همان نقشي را در سلسله اعداد بازي ميكنند كه اتمها در ساختار بناي كيهان دارند. اين اعداد سنگ بناي ناپيداي ديگر اعداد محسوب ميشوند.
يكي از عاديترين راههاي شناسايي اعداد اول تقسيم آن به ديگر اعداد است.
از طرف ديگر با اندكي تامل روشن ميشود كه اعداد زوج عدد اول نيستند زيرا همگي بر ۲قابل قسمتند.
اعدادي كه بتوان جذر آنها را به دست آورد نيز اول نيستند. اما اين روشها براي شناسايي اعداد اول بزرگ به كلي بيفايدهاند. به عنوان مثال اگر عدد اولي داراي ۱۰۰رقم باشد در آن صورت كل عمر باقيمانده از كيهان بر اساس نظريه هاي جديد كيهانشناسي نيز براي مشخص كردن اول بودن يا نبودن اين عدد با اين شيوه هاي متعارف كفايت نميكند.
بنابراين رياضي دانان به سراغ روشهاي ديگر رفتهاند. مهمترين سوال در مورد همه اين روشها آن است كه با چه سرعتي ميتوانند يك عدد اول را مشخص كنند و با ازدياد ارقام عدد اول زمان لازم براي محاسبه چه اندازه طولاني تر مي شود. اگر به عنوان مثال زمان محاسبه به توان ثابتي از شمار ارقام عدد ازدياد يابد در آن صورت اين روش روش قابل قبولي به شمار آورده ميشود .
به اين نوع روشها كه زمان به صورت تواني در آنها افزوده ميشود "روشهاي تواني" ميگويند. روشهاي ديگر كه زمان در آنها با سرعت بيشتري افزايش مييابد روشهاي غيرتواني نام دارند.
به عنوان مثال روش تقسيم معمولي يك روش غيرتواني براي يافتن اعداد اول است.
در سال ۱۹۵۶منطقدان برجسته آلماني «كورت گودل» اين پرسش را مطرح ساخت كه آيا ميتوان اين نوع روشهاي تقسيم را بهبود بخشيد. تلاش خود او نهايتا به كشف شماري از روشهاي عملي براي يافتن اعدادي به بزرگي ۱۰۰رقم يا بيشتر منجر شد. همه اين روشها احتمالاتي هستند و بنابراين در مواردي پاسخ غلط به دست ميدهند هرچند كه اين موارد بسيار نادرند.
در اینجا 500 عدد اول را که تا به حال از همین روشهای معمولی پیدا شده را برای شما گذاشته ایم:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211,223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331,337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449,457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571,577,587,593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677,683,691, 701, 709,719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853,857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953,967, 971, 977, 983,991,997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217,1223,1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319,1321,1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,1453,1459,1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571,1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949,1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017,2027, 2029, 2039, 2053, 2063,2069,2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137,2141, 2143, 2153, 2161, 2179,2203,2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269,2273,2281, 2287, 2293, 2297, 2309, 2311,2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,2381,2383, 2389, 2393, 2399, 2411, 2417,2423,2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557,2579,2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689,2693,2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797,2801,2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,2927,2939,2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217,3221,3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343,3347,3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469,3491,3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571.