دانلود مقاله اعداد اول

بخشی از مقاله

اعداد اول
* لئوپولد كرونكر رياضيدان آلماني اظهار داشته است كه خداوند اعداد صحيح را آفريد و بشر باقي رياضيات را. *
درباره ي اعداد اول
در بين اعداد طبيعي بزرگتر از يك يعني ...و 4و3و2 اعدادي وجود دارند كه تنها بر يك و خود بخش پذيرند، اين اعداد را اعداد اول مي نامند. اعداد اول مبنايي براي همه ي عددهاي طبيعي است ، به اين معني كه هر عدد طبيعي به صورت حاصل ضرب تواني از اعداد اولي است كه مقسوم عليه هاي اين عددند. به عنوان مثال . نخستين هفت عدد اول متمايز عبارتند از: 2و3و7و11و13و17. اينك اين سؤال پيش مي آيد كه آيا اين رشته از اعداد مختوم است يا اينكه تا بي شمار ادامه دارد

. به عبارت ديگر آيا بزرگترين عدد اول وجود دارد يا نه. جواب اين است كه بزرگترين عدد اول وجود ندارد. اين موضوع از عصر طلائي يونانيان مكشوف بوده و توسط اقليدس در سه قرن قبل از ميلاد به اثبات رسيده است. استدلال وي بي اندازه ساده و مبرهن است و هنوز هم تازگي خود را حفظ كرده. پس از اثبات نامتناهي بودن مجموعه ي اعداد اول سؤالاتي ديگر در مورد اين اعداد مطرح مي شود، كه به بعضي از آنها پاسخ داده شده ، ولي برخي هم همچنان بي جواب باقي مانده اند. در اين جا چند نمونه از اين سؤالات مورد بررسي قرار مي گيرند، و ضمناً برهان اقليدس نيز ارائه خواهد گرديد.

معلوم نيست كه مفهوم اول براي اولين بار در چه زماني طرح شده است و چه مدتي سپري گشته تا از مطالعه در خواص اوليه چنين اعدادي به نامتناهي بودن آن پي برده شود. شايد پس از نخستين ملاحظات تجربي و نيز مطالعه ي عملي در خواص اعدادي چون 2و3و11و17 اين سؤال طبعاً پيش آمده است.

برهان ذيل، براي اثبات نامتناهي بودن رشته ي اعداد اول هنوز هم از ساده ترين برهان ها در اين زمينه است. فرض كنيم كه چنين نباشد در اين صورت ، عدد اولي مانند p وجود دارد كه از هر عدد اول ديگر بزرگتر است. اينك را در نظر مي گيريم اين عدد بر هيچ يك از اعداد ( )بخشپذير نيست .

چون m يك عامل اول دارد و اين عامل در بين اعداد ( )نيست پس عامل اولي به غير از اعداد ياد شده دارد و اين با فرض ما در تناقض است. اين نتيجه ي ظريف و زيباي اقليدسي ، كه ضمناً

برهانش هم بسيار ساده است ، يكي از اولين نمونه ي برهانهاي مشهود رياضي است كه به طريقه ي برهان خلف صورت گرفته است. پس ازبررسي اين حكم سؤالات تازه اي مطرح مي شود، و پاسخ به اين سؤالات منجر به نتايج و ملاحظات ديگري مي گردد. به عنوان مثال ، با بكار بردن مفهوم « فاكتوريل» مي توان متقاعد شد كه همواره يك رشته ي بقدر كافي طولاني از اعداد طبيعي متوالي كه اول نباشد وجود دارد. در واقع به ازاي هر n مفروض مي توان n عدد متوالي ،

با در نظر گرفتن اعداد طبيعي : n!+2,n!+3,n!+4,…,n!+n به دست آورد؛ اين اعداد جملگي مركب اند (غير اول). زيرا اولي بر 2 ودومي 3 و سومي 4 و n امي برn بخش پذير است.
هر گاه موضوع را بيشتر تعقيب كنيم، به شگفتي اين اعداد و خصيصه ي مسائل مربوط به آن پي خواهيم برد، به تدريج مسائل جديد مطرح مي شوند و اين مسائل ، مسائل جديد ديگري را پيش مي آورند كه عموماً پاسخ به بعضي از آنها چندان هم ساده نيست.

از بين مسائل معروف اعداد اول ، مقدماتي ترين آنها مسئله ذيل است: در مورد اعداد طبيعي زوج به امتحان ملاحظه شده است كه قابل نمايش به صورت حاصل جمع دو عدد اول است. « كريستيان گلدباخ» رياضيدان آلماني حالت كلي را حدس زد. يعني به حدس اظهار داشت كه هر عدد طبيعي زوج بزرگتر از 2 قابل نمايش به صورت حاصل جمع دو عدد اول است. ( اين موضوع در گلچين رياضي هم آمده) تا عصر حاضر اين حدس به يقين مبدل نشده است و رياضيدانان موفق به اقامه ي برهان براي آن نشده اند. صحت اين حكم براي اعداد طبيعي زوج كوچكتر از 108 محقق شده است. ( تا سال 1968)

با بكار بردن ماشينهاي الكتريكي محاسبه ، مي توان آمارهايي فراهم آورد براي نشان دادن اينكه به چند طريق مي توان يك عدد زوج مانند 2n به صورت حاصل جمع دو عدد اول نوشت ، عده ي طرق با بزرگ شدن n بزرگ مي شوند. در حال حاضر رياضيدانان روسي « ايوان ماتويويچ ويورگرادوف» ثابت كرده است كه هر عدد طبيعي فرد بقدر كافي بزرگ ، قابل نمايش به صورت حاصل جمع سه عدد اول است. فرمولي كه بوسيله آن بتوان هر عدد اول بقدر كافي بزرگ را به دست آورد، وجود ندارد. البته عبارت هايي در دست است كه از روي آن مي توان عده اي از اعداد اول را تعيين كرد.

به عنوان مثال فرمول اويلر در دست است كه از روي آن مي توان عده اي از اعداد اول را تعيين كرد. به عنوان مثال فرمول اويلر به ازاي اعداد اول متمايزي به دست مي دهد . همچنين معلوم نيست كه تعدادي نامتناهي از اعداد اول دوقلو ، يعني اعداد اولي كه تفاضل آنها 2 باشد مانند 5و7 ، 11و13، 29و31 و غيره وجود دارد يا نه. اينها نمونه هايي هستند از مسائلي ساده در اعداد اول كه بطور طبيعي مطرح مي شوند و اگر چه صورت ظاهري آنها ساده به نظر مي رسد، اثبات آنها غالباً دشوار است و اين امكان وجود دارد كه با معلومات رياضي عصر ما ثابت نگردند.

اما در مورد حكمي كه اخيراً ذكر شد، اطلاعاتي در دست است. به عنوان مثال، معلوم گشته كه رشته ي اعداد اول به صورت 4k+1 و4k+3 نامتناهي است. به طور كلي ثابت شده كه در تصاعد حسابي ak+b،كه در اين a وb نسبت به هم اولند و k=1,2,3,… يك تعداد نامتناهي عدد اول وجود دارد.

قضایای اعداد اول
اعداد اول اعدادی طبیعی هستند که بر هیچ عددی بجز خودشان و عدد ۱ بخش‌پذیر نباشند. تنها استثنا عدد ۱ است که جزو این اعداد قرار نمی‌گیرد. اگرعددی طبیعی وبزرگ‌تر از ۱ اول نباشد مرکب است.
عدد یکان اعداد اول بزرگ‌تر از ۱۰ فقط ممکن است اعداد ۱، ۳، ۷، ۹ باشد.
اعداد اول جزو یکی از معماهای ریاضی باقیمانده است و هنوز کسی به فرمولی برای آنها به دست نیاورده است.

سری اعداد اول به این صورت شروع می‌شود: ۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹ ...
قضیه ۱: تعداد اعداد اول بی‌نهایت است.
• قضیه ۱: تعداد اعداد اول بی‌نهایت است.
به این اثبات دقت کنیداز برهان خلف استفاده می کنیم:
فرض خلف : اعداد اول متناهی است.
اعداد اول را در هم ضرب می کنیم.
P1,P2,P3,...,Pn
ضرب اعداد از Pi بزرگ‌تراست.










که عدد ۱ جزو اعداد اول نیست پس به تناقض می رسیم و فرض خلف باطل است. اعداد اول نامتناهی هستند.
برهان: حکم را به روشی که منسوب به اقلیدس است اثبات می‌کنیم: فرض کنید تعداد اعداد اول متناهی و تعداد آنها n تا باشد. حال عدد M را که برابر حاصل‌ضرب این اعداد به علاوه ۱ را در نظر بگیرید. این عدد مقسوم‌علیهی غیر از آن n عدد دارد که با فرض در تناقض است.
قضیه ۲ (قضیه اساسی حساب): هر عدد طبیعی بزرگ‌تر از ۱ را به شکل حاصل‌ضرب اعدادی اول نوشت.
قضیه ۳ (قضیه چپیشف):اگر n عددی طبیعی و بزرگ‌تر از ۳ باشد، حتما" بین n و ۲n عدد اولی وجود دارد. قضيه ۴ هر عدد زوج را می‌توان بصورت جمع سه عدد اول نوشت.
قضيه ۵ هر عدد فرد (شامل اعداد اول) را می‌توان به صورت جمع سه عدد اول نوشت (اثبات بر پايه قضيه ۴)

قضيه 6-هر عدد فرد را می‌توان به صورت دو برابر يك عدد اول بعلاوه يك عدد اول ديگر نوشت.
خواص اعداد اول:
1- هر عدد اول برابر است با 6n+1 يا 6n-1 كه n يك عدد صحيح است.
2-مجذور هر عدد اول برابر است با 24n+1.
3-تفاضل مجذورهاي دو عدد اول مضربي از 24 است.
4-حاصلضرب هر دو عدد اول بجز 2و3 مضربي از 6 بعلاوه يا منهاي يك است.
توان چهارم هر عدد اول بجز 2و3 مضربي از 240 بعلاوه يك اس

بزرگ‌ترین عدد اول کشف شده برابر دو به توان ‪ ۳۰‬ميليون و ‪ ۴۰۲‬هزار و ‪ ۴۵۷‬منهاي يك است.این عدد یک عدد مرسن است. عدد مرسن عددی است که برابر 2 به توان n منهای یک است.
لازم به ذكر است كه تعداد 3000 عدد اول در سايت مگاسندر [url]www.megasender.org[/url] وجود دارد و افرادي كه مايل به دريافت بيشتر اين اعداد هستند مي توانند با سايت مذكور تماس گرفته و تعداد بيشتري از آنها را بر روي لوح فشرده دريافت نمايند و طراحان اين سايت خودشان اين اعداد را محاسبه نموده اند

روشي براي شكار اعداد اول
کی از اولین و در عین حال درخشانترین کارهای بشر در نظریه اعداد، اثبات اقلیدس از نامتناهی بودن اعداد اول در کتاب اصول است که امروزه می توان آن را در کتاب های درسی دبیرستانی خواند. نمونه ای عالی از زیبایی و سادگی ریاضیات. یونانی ها اعداد اول را می شناختند و از نقش آن ها به عنوان بلوک های سازنده دیگر اعداد آگاه بودند. بعد از این دستاوردهای بزرگ طبیعی ترین سوالی که به ذهن بشر رسید این بود که چه نظمی بر دنباله اعداد اول حاکم است، چگونه می

توان اعداد اول را یافت و چطور می توان اعدادی را که اول نیستند به عوامل اول شان تجزیه کرد. شاید اولین پاسخ به این سوال غربال اراتستن بوده باشد. تا امروز تلاش های زیادی برای یافتن یک فرمول تولید کننده اعداد اول و یا الگویی برای ظهور اعداد اول در میان دیگر اعداد انجام شده است که هر چند کمک های زیادی به گسترش نظریه اعداد کرده اند اما ساختار پیچیده اعداد اول همچنان در مقابل این تلاش ها مقاومت می کند.

جستجو برای الگوهایی از نظم در اعداد اول
یک نمونه ساده: ۳۱-۳۳۱-۳۳۳۱-۳۳۳۳۱-۳۳۳۳۳۱-۳۳۳۳۳۳۱-۳۳۳۳۳۳۳۱ همه اولند اما ۳۳۳۳۳۳۳۳۱ حاصلضرب دو عدد اول ۱۷ و ۱۹۶۰۷۸۴۳ است.

اعداد اول مرسن: اگر p اول باشد اعدادی به شکل ۲p-۱ را عدد مرسن میگوییم. اگر این اعداد اول باشند به آن ها عدد اول مرسن می گوییم. به ازای p برابر ۲ و ۳ و ۵ و ۷ عدد مرسن اول است اما اگر p را ۱۱ بگیریم مرکب است. تا امروز ۳۹ عدد اول مرسن شناخته شده اند که آخرینشان به ازای p=۱۳۴۶۶۹۱۷ به دست می‌آید و ۴۰۵۳۹۴۶ رقم دارد. یعنی بین همه اعداد اول کوچکتر از ۱۳۴۶۶۹۱۷ تنها ۳۹ تا عدد اول مرسن تولید می کنند.

اعداد اول دوقلو: به اعداد اولی که پشت سر هم هستند اعداد اول دوقلو می گوییم مثلا ۳ و ۵ و یا ۱۱ و ۱۳. هیچ کس نمی داند که پراکندگی این اعداد در میان سایر اعداد چگونه است و آیا تعداشان متناهی است یا نه بزگترین جفت شناخته شده ۱-۲۱۶۹۶۹۰×۳۳۲۱۸۹۲۵ و ۱+۲۱۶۹۶۹۰×۳۳۲۱۸۹۲۵ هستند.

برای پیدا کردن اطلاعاتی راجع به جستجوی اعداد اول می توانید به سایت پروژه GIMPS سر بزنید.

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

چرا؟ )، همچنین در صورتیکه اعداد اول کوچکتر از عدد مورد نظر شناخته شده باشند، تقسیم کردن به این اعداد کافیست. این روش ها برای اعداد نسبتا کوچک کار می کنند اما وقتی با عددی مثلا ۱۰۰ رقمی طرف باشیم اوضاع فرق می کند. حتی با سریع ترین کامپیوترها هم تقسیم کردن یک عدد ۱۰۰ رقمی به همه اعداد کوچکتر از آن خیلی بیشتر از عمر عالم طول می کشد.

یک محاسبه سرانگشتی
فرض کنید بخواهیم یک عدد ۱۰۰ رقمی را به همه اعداد کوچکتر از خودش تقسیم کنیم. برای این کار باید حدود ۱۰۹۹ تقسیم انجام دهیم اگر کامپیوتر ما بتواند در هر ثانیه ۱۰۰۰ میلیارد یعنی ۱۰۱۲ تقسیم انجام دهد برای انجام کل کار ۱۰۸۷ ثانیه وقت لازم است.
یک سال ۲۴×۳۶۰۰×۳۶۵=۳۱۵۳۶۰۰۰ ثانیه است یعنی حدود ۱۰۸ ثانیه و این یعنی کار ما ۱۰۷۹ سال طول خواهد کشید. عمر عالم دست بالا ۱۵ میلیارد سال تخمین زده می شود. حتی یک دهم یا یک صدم یا یک هزارم این محاسبه هم غیر قابل انجام است.

حوالی قرن هفدهم توجه ریاضیدانان به این نکته جلب شد که شاید راه های ساده تری برای آزمایش اول بودن یا نبودن یک عدد وجود داشته باشد چرا که روش تقسیم مقدار زیادی اطلاعات اضافی ( لیست عوامل اول، وقتی که جواب سوال منفی است ) تولید می کند که برای پاسخ گفتن به این سوال نیازی به آن ها نیست. فرما مدتی بعد نشان داد که این حدس صحیح بوده است. فرما (۱۶۰۱-۱۶۶۵) قضیه ای را ثابت کرد که تا امروز اساس همه روش های آزمایش اول بودن اعداد است و ما آن را با نام قضیه کوچک فرما می شناسیم.

قضیه کوچک فرما: اگر p عددی اول و b عدد دلخواهی باشد که p و b نسبت به هم اول باشند، آن گاه باقیمانده تقسیم بر p و باقیمانده تقسیم b بر p همیشه برابرند.
بنابراین برای اینکه بدانیم عددی مثل a اول است یا نه کافیست عدد دلخواهی مثل b که نسبت به a اول باشد انتخاب کنیم و باقیمانده تقسیم بر a را بیابیم اگر این باقیمانده برابر b نباشد عدد ما اول نیست.

تنها مشکلی که وجود دارد این است که از آنجا که عکس قضیه فرما لزوما درست نیست - یعنی ممکن است بعضی از اعداد مرکب هم این خاصیت را داشته باشند - اگر باقیمانده b باشد نمی توان در مورد اول بودن یا نبودن a اظهارنظری کرد. این مشکل هم ۳۰۰ سال بعد در تابستان ۲۰۰۲ بوسیله سه ریاضیدان هندی به نام‌های Agrawal، Kayal و Saxena حل شد و حالا می توانیم در کسری از ثانیه در مورد اول بودن عددی با ۱۰۰ رقم اظهارنظر کنیم.

اعداد اول اعداد بسيار زيبا و جذابند و در عين حال معماي حيرت انگيز و سرگردان‌كننده اي را در برابر رياضي دانان مطرح ساخته اند. تعريف اين اعداد كاملا ساده است، رفتار آنها در سلسله اعداد و نحوه ظاهر شدنشان در آن كاملابي‌نظم و فاقد قاعده به نظر مي‌آيد و هرچه شمار بيشتري از آنها شكارمي‌شوند، كار شكار عدد بعدي دشوارترمي‌شود طي قرنهاي متمادي رياضي دانان در شرق و غرب عالم به جستجوي راههايي براي دستيابي به اعداد اول برخاسته‌اند و با اين همه بهترين روشهايي كه تا بحال در اين زمينه ابداع شده چنان كند است كه حتي پر سرعت‌ترين

كامپيوتر هاي كنوني نيز نمي‌توانند كمك چنداني در شكار اين اعداد شگفت انگيز كنند. بطوريكه اگر چندين ميليون بار به سرعت كامپيوتر هاي كنوني افزوده شود، تنها چند رقم به شماره ارقام بزرگترين عدد اولي كه تا به حال شناخته شده افزوده مي‌گردد. رياضي دانان در آرزوي دست يافته به روشي هستند كه با استفاده از آن بتوانند با سرعت به يافتن اعداد اول توفيق يابند و يا اگر با عددي هر اندازه پر رقم و بزرگ روبرو شدند بتوانند با سرعت مشخص سازند كه آيا عدد اول است ؟