ک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه:14
فهرست مطالب
اعداد اول
اعداد اول اعدادی طبیعی هستند که بر هیچ عددی بجز خودشان و عدد ۱ بخشپذیر نباشند. تنها استثنا عدد ۱ است که جزو این اعداد قرار نمی‌گیرد. اگرعددی طبیعی وبزرگ‌تر از ۱ اول نباشد مرکب است.
عدد یکان اعداد اول بزرگ‌تر از ۱۰ فقط ممکن است اعداد ۱، ۳، ۷، ۹ باشد.
اعداد اول جزو یکی از معماهای ریاضی باقیمانده است و هنوز کسی به فرمولی برای آنها به دست نیاورده است.
سری اعداد اول به این صورت شروع میشود: ۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹ ...
قضیه ۱: تعداد اعداد اول بینهایت است.
- قضیه ۱: تعداد اعداد اول بینهایت است.
به این اثبات دقت کنیداز برهان خلف استفاده می کنیم:
فرض خلف : اعداد اول متناهی است.
اعداد اول را در هم ضرب می کنیم.
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 حل شد و حالا می توانیم در کسری از ثانیه در مورد اول بودن عددی با ۱۰۰ رقم اظهارنظر کنیم.
اعداد اول اعداد بسیار زیبا و جذابند و در عین حال معمای حیرت انگیز و سرگردان‌کننده ای را در برابر ریاضی دانان مطرح ساخته اند. تعریف این اعداد کاملا ساده است، رفتار آنها در سلسله اعداد و نحوه ظاهر شدنشان در آن کاملابی‌نظم و فاقد قاعده به نظر می‌آید و هرچه شمار بیشتری از آنها شکارمی‌شوند، کار شکار عدد بعدی دشوارترمی‌شود طی قرنهای متمادی ریاضی دانان در شرق و غرب عالم به جستجوی راههایی برای دستیابی به اعداد اول برخاسته‌اند و با این همه بهترین روشهایی که تا بحال در این زمینه ابداع شده چنان کند است که حتی پر سرعت‌ترین کامپیوتر های کنونی نیز نمی‌توانند کمک چندانی در شکار این اعداد شگفت انگیز کنند. بطوریکه اگر چندین میلیون بار به سرعت کامپیوتر های کنونی افزوده شود، تنها چند رقم به شماره ارقام بزرگترین عدد اولی که تا به حال شناخته شده افزوده می‌گردد. ریاضی دانان در آرزوی دست یافته به روشی هستند که با استفاده از آن بتوانند با سرعت به یافتن اعداد اول توفیق یابند و یا اگر با عددی هر اندازه پر رقم و بزرگ روبرو شدند بتوانند با سرعت مشخص سازند که آیا عدد اول است ؟ یک گروه از ریاضی دانان هندی مدعی شده‌اند که در آستانه دستیابی به همان آزمونی هستند که ریاضی دانان قرنها مشتاقانه در آرزویش بوده اند. مانیندرا اگراوال ,Manindra Agrawalو دانشجویانش نیراج کایالNeeraj Kayalو نیتین سکسنا Nitin Saxenaدر موسسه تکنولوژی کانپور مدعی شده‌اند که در آستانه تکمیل آزمونی هستند که اول بودن یا نبودن هر عدد طبیعی را با سرعت مشخص می‌کند. این آزمون در صورتی که تکمیل شود می‌تواند تبعات و نتایج بسیار گسترده‌ای برای جهان کنونی به بار آورد. جالب به نظر میرسد که بدانید: درحال حاضر بسیاری از معاملات تجاری و نقل و انتقالات مالی و نیز مبادله اطلاعات محرمانه از طریق شبکه های مخابراتی مانند اینترنت و با بهره گیری از رمز کردن پیامها به انجام میرسد. اعداد اول در تنظیم این قبیل رمزها نقشی اساسی بر عهده دارند و از همین رو دستیابی به اعداد اول جدید که دیگران از آن بی‌خبر باشند برای سازندگان این رمزها و نیز مشتریان آنان از اهمیت زیاد برخوردار است. اما اگر روش این محققان هندی تکمیل شود در آن صورت امنیت این قبیل نقل و انتقالات در معرض خطر جدی قرار خواهد گرفت. سابقه قرار گرفتن ریاضی دانان تحت جاذبه اعداد اول به قرنها پیش باز می گردد. در سال ۱۸۰۱کارل گائوس از بزرگترین ریاضی دانان اعلام کرد که مساله تشخیص اعداد اول از اعداد غیر اول یکی از مهمترین مسائل حساب به شمار می‌آید. اعداد اول به یک معنا همان نقشی را در سلسله اعداد بازی می‌کنند که اتمها در ساختار بنای کیهان دارند- این اعداد سنگ بنای ناپیدای دیگر اعداد محسوب میشوند. یکی از عادی‌ترین راههای شناسایی اعداد اول تقسیم آن به دیگر اعداد است. از طرف دیگر با اندکی تامل روشن میشود که اعداد زوج عدد اول نیستند زیرا همگی بر ۲قابل قسمتند. اعدادی که بتوان جذر آنها را به دست آورد نیز اول نیستند. اما این روشها برای شناسایی اعداد اول بزرگ به کلی بی‌فایده‌اند. به عنوان مثال اگر عدد اولی دارای ۱۰۰رقم باشد در آن صورت کل عمر باقیمانده از کیهان بر اساس نظریه های جدید کیهانشناسی نیز برای مشخص کردن اول بودن یا نبودن این عدد با این شیوه های متعارف کفایت نمی‌کند. بنابراین ریاضی دانان به سراغ روشهای دیگر رفته‌اند. مهمترین سوال در مورد همه این روشها آن است که با چه سرعتی می‌توانند یک عدد اول را مشخص کنند و با ازدیاد ارقام عدد اول زمان لازم برای محاسبه چه اندازه طولانی تر می شود. اگر به عنوان مثال زمان محاسبه به توان ثابتی از شمار ارقام عدد ازدیاد یابد در آن صورت این روش روش قابل قبولی به شمار آورده میشود . به این نوع روشها که زمان به صورت توانی در آنها افزوده میشود "روشهای توانی" می‌گویند. روشهای دیگر که زمان در آنها با سرعت بیشتری افزایش می‌یابد روشهای غیرتوانی نام دارند. به عنوان مثال روش تقسیم معمولی یک روش غیرتوانی برای یافتن اعداد اول است. در این روش زمان لازم برای تعیین اول بودن یک عدد با dرقم، برابر با /۱۰d/2این نوع روشها بسیار نامناسبند.
پیچیده گی های اعداد اول
در150 سال اخیر یا بیشتر نظریه اعداد پیشرفتهای زیادی در جهات مختلف داشته.شرح انواع مسائلی که در نظریه اعداد بررسی شده اند در اینجا ممکن نیست.این مبحث بسیار وسیع است و در بعضی قسمتها نیاز به دانستن مطالب عمیقی از ریاضیات پیشرفته (مثل نظریه گالوا و آنالیز در سطح بالا ) دارد. با اینحال مسائل زیادی در نظریه اعداد وجود دارد که به آسانی قابل بیانند . برخی از آنها به اعداد اول مربوط میشوند .
در نوشته ی قبلی اعداد کوچکتر از 500 ذکر شده اند .در 1914 ریاضیدان آمریکایی دی.ان.لمر با منتشر کردن جدول همه اعداد اول کوچکتر از 10 میلیون متوجه شد که فقط 664579 تا عدد اول وجود دارد یعنی حدود6.5 درصد.همچنین دی اچ لمر(پسر
دی.ان.لمر) تعداد اعداد اول کوچکتر از 10 میلیارد را حساب کرد 455052512.حدوداً 4.5 درصد .
بررسی دقیق اعداد اول نشان می دهد که توزیع بسیار نامنظمی دارند . به آسانی ثابت میشود که شکافهای به اندازه ی دلخواه بین آنها وجود دارد. بررسی این اعداد نشان میدهد که اعداد اول متوالی ، نظیر 3و5 یا 101و103 همین طور تکرار میشوند
جفتهایی از اعداد اول که تفاضلشان 2 است اعداد اول دو قلو نامیده میشوند بیش از 1000 جفت از این جفتها زیر 100000 بیش از 8000 جفت زیر 1000000 وجود دارند این مسئله که آیا بینهایت تا از این اعداد وجود دارد یا نه هنوز حل نشده است
اعداد اول
همان طوری که می دانیم اعداد اول پایه و اساس کلیه اعداد در ریاضیات می باشند. بنابر این شناختن این اعداد و جدا کردن آنها از اعداد دیگر از اهمیت ویژه های برخوردار است. از آنجا که تشخیص این اعداد کاری مشکل است و نیاز به صرف وقت فراوان دارد تصمیم گرفتیم که الگوریتمی طراحی کنیم تا به وسیله آن بتوانیم اعداد اول را راحت تر پیدا کنیم.
جستجو برای الگوهایی از نظم در اعداد اول
یک نمونه ساده: ۳۱-۳۳۱-۳۳۳۱-۳۳۳۳۱-۳۳۳۳۳۱-۳۳۳۳۳۳۱-۳۳۳۳۳۳۳۱ همه اولند اما ۳۳۳۳۳۳۳۳۱ حاصلضرب دو عدد اول ۱۷ و ۱۹۶۰۷۸۴۳ است.
اعداد اول مرسن: اگر p اول باشد اعدادی به شکل ۲p-۱ را عدد مرسن میگوییم. اگر این اعداد اول باشند به آن ها عدد اول مرسن می گوییم. به ازای p برابر ۲ و ۳ و ۵ و ۷ عدد مرسن اول است اما اگر p را ۱۱ بگیریم مرکب است. تا امروز ۳۹ عدد اول مرسن شناخته شده اند که آخرینشان به ازای p=۱۳۴۶۶۹۱۷ به دست می‌آید و ۴۰۵۳۹۴۶ رقم دارد. یعنی بین همه اعداد اول کوچکتر از ۱۳۴۶۶۹۱۷ تنها ۳۹ تا عدد اول مرسن تولید می کنند.
اعداد اول دوقلو: به اعداد اولی که پشت سر هم هستند اعداد اول دوقلو می گوییم مثلا ۳ و ۵ و یا ۱۱ و ۱۳. هیچ کس نمی داند که پراکندگی این اعداد در میان سایر اعداد چگونه است و آیا تعداشان متناهی است یا نه بزگترین جفت شناخته شده ۱-۲۱۶۹۶۹۰×۳۳۲۱۸۹۲۵ و ۱+۲۱۶۹۶۹۰×۳۳۲۱۸۹۲۵ هستند.
یک محاسبه سرانگشتی
فرض کنید بخواهیم یک عدد ۱۰۰ رقمی را به همه اعداد کوچکتر از خودش تقسیم کنیم. برای این کار باید حدود ۱۰۹۹ تقسیم انجام دهیم اگر کامپیوتر ما بتواند در هر ثانیه ۱۰۰۰ میلیارد یعنی ۱۰۱۲ تقسیم انجام دهد برای انجام کل کار ۱۰۸۷ ثانیه وقت لازم است.
یک سال ۲۴×۳۶۰۰×۳۶۵=۳۱۵۳۶۰۰۰ ثانیه است یعنی حدود ۱۰۸ ثانیه و این یعنی کار ما ۱۰۷۹ سال طول خواهد کشید. عمر عالم دست بالا ۱۵ میلیارد سال تخمین زده می شود. حتی یک دهم یا یک صدم یا یک هزارم این محاسبه هم غیر قابل انجام است.
تحقیق در مورد اعداد اول