تحقیق در مورد بزرگترین عدد اول

بخشی از مقاله

بزرگترین عدد اول

بزرگ ترین عدد اولی که تا کنون کشف شده است، عدد ۱- ۲۳۰۴۰۲۴۵۷ است که ۹۱۵۲۰۵۲ رقم دارد.
عدد اول : هر عدد طبیعی بزرگ تر از یک که فقط بر خودش ویک بخش پذیر باشد،عدد اول نامیده می شود. مثل ۲ ، ۳ ، ۵ ، ۷ ، ...
عدد مرکب : هرعدد طبیعی بزرگ تراز یک که به جز خودش و یک بر عدد طبیعی دیگری نیزبخش پذیر باشد، عددی مرکب نامیده می شود . مثل ۴ ، ۶ ، ۸ ، ۹ ، ...
عدد مرسن :اعداد اولی به شکل ۱- Mn = ۲n که در آن n اول باشد، اعداد اول مرسن نامیده می شوند. مثل اعداد ۳ و۷ که اولین و دومین اعداد اول مرسن هستند.

( ۱- ۲۲ = ۳ و ۱ - ۲۳ = ۷ )
نخستین اعداد اول مرسن عبارت اند از : ۳ ، ۷ ، ۳۱ ، ۱۲۷ ، ۸۱۹۱ ، ۱۳۱۰۷۱ ، ۲۱۴۷۴۸۳۶۴۷ ، ... که به ترتیب با n های اول ۲ ، ۳ ، ۵ ، ۷، ۱۳ ، ۱۷ ، ۱۹ ، ... متناظر هستند.
آقای مونک مارین مرسن فرانسویMonk Marin Mersenne۱۶۴۸-۱۵۸۸) ) که این اعداد را کشف کرد حدوداً ۳۵۰ سال قبل می زیسته است و اکنون ابر رایانه ها به کمک فرمول او سرگرم جستجوی اعداد اول بزرگ هستند.

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

نیز بسیار مهم است. چرا که یکی از کاربردهای اصلی اعداد اول در مسائل امنیت و ایمنی ارتباطات رایانه ای و به ویژه شبکه های مبادلاتی الکترونیک است. فرض کنید شما یک عدد اول بسیار بزرگ داشته باشید و از آن به عنوان یک کد یا یک امضای الکترونیک استفاده کنید و از عدد غول پیکر اول دیگری نیز به عنوان پاسخ امضاء یا تاییدیه استفاده نمایید. به این دلیل ک

ه اعداد اول هیچ توزیع منظمی ندارند بنابراین رمزهایی که بر اساس آن ها ساخته شده باشد به راحتی قابل شکستن نخواهد بود. این انگیزه ی مهمی برای جستجوی اعداد اول بزرگ تر است.بزرگ ترین عدد اول که چهل و سومین عدد مرسن است کشف شد. شبکه رایانه ایGIMPS ( Great Internet Prime Search)عدداول ۱- ۲۳۰۴۰۲۴۵۷ راکه ۹۱۵۲۰۵۲ رقم دارد کشف کرد.

تعریف اعداد اول
عدد طبیعی P>1 را عدد اول می گویند هرگاه تنها مقسوم علیه های مثبت آن 1 و P باشند. به عبارت دیگر یک عدد طبیعی اول است هرگاه جز یک و خودش بر هیچ عدد دیگری بخش پذیر نباشد.
هر عدد طبیعی مخالف یک که اول نباشد مرکب یا تجزیه پذیر می گوییم.

به عنوان مثال اعداد 2و3و5و7 اول و اعداد 12و18و325 مرکب می باشند.
• لازم به ذکر است که عدد یک نه اول و نه مرکب است و تنها عدد اول زوج عدد 2 است.
اگر n عددی مرکب باشد می توان گفت:
• نتیجه: اگر P عددی اول . a و b اعدادی طبیعی باشند، در این صورت:

• قضیه بنیادی حساب:
هر عدد طبیعی بزرگتر از یک را می توان به صورت یکتایی به صورت حاصل ضرب عوامل اول نوشت.
به عبارت دیگر اگر n عددی طبیعی و بزرگتر از 1 باشد:
که در آن ها اعداد اول متمایر می باشند.

این نمایش را تجزیه عدد n به عوامل اول می گوییم.
همچنین اگر n<-1 باشد باز هم می توان n را به صورت یکتایی به صورت حاصل ضرب عوامل اول نوشت:


که در آن ها اعداد اول متمایز می باشند.
• لازم به توضیح است که ممکن است در تجزیه یک عدد طبیعی به عوامل اول، تعدادی از عوامل یکسان باشند. به عنوان مثال:12=2×2×3
تجزیه استاندارد یک عدد:
اگر n>1 عددی طبیعی باشد آنگاه عدد n را می توان به شکل یکتایی به صورت:

که در آن ها اعداد اول متمایز و اعداد طبیعی اند.
این روش نمایش و تجزیه عدد را تجزیه متعارف، استاندارد، یا کانونیک عدد n می گویند.
• توجه: بزرگترین توان که: را به صورت می دهند.
به عنوان مثال تجزیه استاندارد 12 به عوامل اول به صورت مقابل است:
این جدول شامل عامل‌های / مقسوم علیه‌های اول برای اعداد 1 تا 1000 می باشد. توجه: تابع اضافی (a0(n = حاصل جمع علمل‌های اول عدد n می باشد. هرگاه n عامل اول باشد بصورت ضخیم نوشته شده است.
همچنین رجوع شود به: جدول مقسوم علیه‌ها، عامل‌های اول و غیر-اول برای اعدا 1 تا 1000.
n عامل‌های
اول a0(n) n عامل‌های
اول a0(n) n عامل‌های
اول a0(n)
1 1 1 335 5•67 72 669 3•223 226
2 2 2 336 24•3•7 18 670 2•5•67 74
3 3 3 337 337 337 671 11•61 72
4 22 4 338 2•132 28 672 25•3•7 20
5 5 5 339 3•113 116 673 673 673
6 2•3 5 340 22•5•17 26 674 2•337 339
7 7 7 341 11•31 42 675 33•52 19

8 23 6 342 2•32•19 27 676 22•132 30
9 32 6 343 73 21 677 677 677
10 2•5 7 344 23•43 49 678 2•3•113 118
11 11 11 345 3•5•23 31 679 7•97 104

12 22•3 7 346 2•173 175 680 23•5•17 28
13 13 13 347 347 347 681

3•227 230
14 2•7 9 348 22•3•29 36 682 2•11•31 44
15 3•5 8 349 349 349 683 683 683

16 24 8 350 2•52•7 19 684 22•32•19 29
17 17 17 351 33•13 22 685 5•137 142
18 2•32 8 352 25•11 21 686 2•73 23
19 19 19 353 353 353 687 3•229 232
20 22•5 9 354 2•3•59 64 688 24•43 51
21 3•7 10 355 5•71 76 689 13•53 66
22 2•11 13 356 22•89 93 690

2•3•5•23 33
23 23 23 357 3•7•17 27 691 691 691

24 23•3 9 358 2•179 181 692 22•173 177
25 52 10 359 359 359 693 32•7•11 24

26 2•13 15 360 23•32•5 17 694 2•347 349
27 33 9 361 192 38 695 5•139 144

28 22•7 11 362 2•181 183 696 23•3•29 38
29 29 29 363 3•112 25 697 17•41 58
30 2•3•5 10 364 22•7•13 24 698 2•349 351

31 31 31 365 5•73 78 699 3•233 236
32 25 10 366 2•3•61 66 700 22•52•7 21

33 3•11 14 367 367 367 701 701 701
34 2•17 19 368 24•23 31 702 2•33•13 24
35 5•7 12 369 32•41 47 703 19•37 56
36 22•32 10 370 2•5•37 44 704 26•11 23
37 37 37 371 7•53 60 705 3•5•47 55
38 2•19 21 372 22•3•31 38 706 2•353 355
39 3•13 16 373 373 373 707 7•101 108
40 23•5 11 374 2•11•17 30 708 22•3•59 66
41 41 41 375 3•53 18 709 709 709
42 2•3•7 12 376 23•47 53 710 2•5•71 78
43 43 43 377 13•29 42 711 32•79 85
44 22•11 15 378 2•33•7 18 712 23•89 95
45 32•5 11 379 379 379 713 23•31 54
46 2•23 25 380 22•5•19 28 714 2•3•7•17 29
47 47 47 381 3•127 130 715 5•11•13 29

قضیه اعداد اول
در جستجو برای یافتن قانون حاکم بر توزیع عددهای اول، گام مهم و اساسی زمانی برداشته شد که ریاضیدانان از تلاش بی‌ثمر برای یافتن فرمول ریاضی ساده‌ای که همه اعداد اول یا تعداد دقیق عددهای اول در میان عدد صحیح نخست را به دس

ت دهد دست برداشتند، و به جای آن در جستجوی اطلاعات درباره متوسط توزیع عددهای اول در میان عددهای صحیح برآمدند.
فرض کنید به ازای هر عدد صحیح تعداد عددهای اول در میان اعداد صحیح 1، 2، 3، ...، را با نمایش دهیم. اگر زیر اعداد اول در دنباله مرکب از چند عدد صحیح نخست خط بکشیم، می‌توانیم چند مقدار اولیه را محاسبه کنیم:

حال اگر دنباله دلخواهی از مقادیر را در نظر بگیریم که به طور نامحدود افزایش یابد، مثلاً
آنگاه مقادیر متناظر :
نیز به طور نامحدود (هر چند با سرعت کمتر) افزایش می‌یابند. از آنجا که می‌دانیم بینهایت عدد اول وجود دارد، مقادیر هم دیر یا زود از هر عدد متناهی تجاوز خواهند کرد. «چگالی» عددهای اول در میان عدد صحیح نخست با نسبت مشخص می‌شود و با استفاده از یک جدول اعداد اول، مقادیر را می‌توان به طور تجربی به ازای مقادیر نسبتاً بزرگ محاسبه کرد.

0/168
0/078498
0/050847478
.......... ...
می‌توان گفت که درایه آخر جدول بیانگر احتمال آن است که عدد صحیحی که به تصادف از میان عدد صحیح نخست انتخاب شده، اول باشد زیرا انتخاب ممکن وجود دارد که از آنها اول‌اند.
توزیع عددهای اول در میان اعداد صحیح فوق‌العاده بی‌نظم است. ولی این بی‌نظمی «در مقیاس کوچک»، از میان می‌رود به شرط اینکه توجه خود را به متوسط توزیع عددهای اول که با نسبت مشخص می‌شود معطوف کنیم. کشف قانون ساده‌ای که رفتار این نسبت از آن تبعیت می‌کند یکی از برجسته‌ترین اکتشافات در تمام ریاضیات است. گاوس از بررسی تجربی جدولهای اعداد اول دریافت که نسبت تقریباً برابر است و این تقریب با افزایش ظاهراً بهتر می‌شود. میزان خوبی تقریب با نسبت مشخص می‌شود که مقدارهایش به ازای =1000، =1000000 و =1000000000 در جدول زیر نشان داده شده‌اند.




1/59 0/145 0/168
1/084 0/072382 0/78498
1/053 0/048254942 0/050847478
... ... ... ...
گاوس براساس این گونه شواهد تجربی ح

دس زد که نسبت «به طور مجانبی» برابر با است. منظور از این گفته آن است که اگر دنباله‌ای از مقادیر را که مرتباً بزرگ و بزرگتر می‌شوند، مثلاً همان دنباله

را در نظر بگیریم، آنگاه نسبت به ، یعنی عدد

که به ازای همین مقادیر متوالی محاسبه شود، به 1 نزدیک و نزدیکتر خواهد شد، و اختلاف این نسبت با 1 می‌توان با محدود کردن به م

قادیر به اندازه کافی بزرگ، به قدر دلخواه کوچک کرد. این مطلب به صورت نمادین با علامت ~ بیان می‌شود:
به این معنی است که وقتی افزایش می‌یابد، به 1 میل می‌کند.
با توجه به اینکه همیشه عددی صحیح است ولی چنین نیست، روشن می‌شود که چرا نمی‌توان علامت معمولی تساوی، =، را به جای ~ قرار داد.
این موضوع که چگونگی توزیع میانگین اعداد اول را می‌توان به وسیله تابع لگاریتمی توصیف کرد، کشف بسیار جالبی است زیرا شگفت‌آور است که دو مفهوم ریاضی که این قدر نامرتبط به نظر می‌رسند، در واقع چنین ارتباط نزدیکی با هم دارند.
اگر چه فهم صورت حدس گاوس آسان است، اثبات ریاضی دقیق آن بسیار دور از حدود امکانات علوم ریاضی در زمان گاوس بود. برای اثبات این قضیه، که فقط با ابتدایی‌ترین مفاهیم سروکار دارد، استفاده از قویترین روشهای ریاضیات نوین لازم است. تقریباً صدسال طول کشید تا آنالیز به درجه‌ای تکامل یافت که آدامار (1896) در پاریس و دلاواله پوسن در لوون (1896) توانستند اثبات کاملی از قضیه اعداد اول به دست دهند. من گولت و لاندوا صورتهای ساده شده و اصلاح شده مهمی از استدلال را عرضه کردند. مدتها قبل از آدامار، تحقیق پیشگامانه خطوط استراتژیک اقدام برای حل مساله مشخص گشته بود. نوربرت وینر ریاضیدان آمریکایی توانست این اثبات را اصلاح کند تا از به کار بردن عددهای مختلط در مرحله مهمی از استدلال اجتناب شود. با این حال، اثبات قضیه اعداد اول هنوز هم، حتی برای دانشجوی پیشرفته، آسان نیست. در سال 1949 پل اردوش ، استاد مسلم اپباع‌های ابتدایی ، و سلبرگ توانستند این قضیه را با تکنیک‌های ابتدایی نظریه اعداد و بدون استفاده از تکنیک‌های تحلیلی اثبات نمایند.
فرمول های اعداد اول

مساله‌ی توزیع اعداد اول در اعداد صحیح همیشه در بین ریاضی‌دانان مورد بحث و پژوهش قرار داشته و دارد. از جمله‌ی مسائل در این موضوع پیدا کردن فرمول حسابی برای یافتن اعداد می‌باشد. یعنی فرمول‌هایی که فقط عدد اول تولید کنند، هر چند همه آنها به دست ندهند. از جمله فرمول‌های قدیمی و معروف در این زمینه منسوب به مرسن است. به اعداد به شکل اعداد مرسن گویند. مثال‌های ساده‌ای نشانگر اینند که این فرمول ممکن است عدد اول تولید نکند. مثلا . جدول زیر لیست اعداد اول کشف شده می‌باشد:
# n (M(n تعداد رقم‌های (M(n تاریخ کشف کاشف
1 2
1 مشخص نیست ناشناس
1 مشخص نیست ناشناس
3 5
2 مشخص نیست ناشناس
4 7
3 مشخص نیست ناشناس
5 13
4 1456 ناشناس
6 17
7 19
6 1588 Cataldi
8 31
10 1772 Euler
9 61
19 1883 Pervushin

10 89
27 1911 Powers
11 107
33 1914 Powers
12 127
39 1876 Lucas
13 521

157 January 30, 1952 Robinson
14 607
183 January 30, 1952 Robinson
15 1,279
386 June 25, 1952 Robinson

16 2,203
664 October 7, 1952 Robinson

17 2,281
687 October 9, 1952 Robinson
18 3,217
969 September 8, 1957 Riesel
19 4,253
1,281 November 3, 1961 Hurwitz
20 4,423
1,332 November 3, 1961 Hurwitz
21 9,689

2,917 May 11, 1963 Gillies
22 9,941
2,993 May 16, 1963 Gillies
23 11,213
3,376 June 2, 1963 Gillies
24 19,937
6,002 March 4, 1971 Tuckerman
25 21,701
6,533 October 30, 1978 Noll & Nickel
26 23,209
6,987 February 9, 1979 Noll
27 44,497
13,395 April 8, 1979 Nelson & Slowinski
28 86,243
25,962 September 25, 1982 Slowinski
29 110,503
33,265 January 28, 1988 Colquitt & Welsh
30 132,049

39,751 September 20, 1983 Slowinski
31 216,091
65,050 September 6, 1985 Slowinski
32 756,839
227,832 February 19, 1992 Slowinski & Gage
33 859,433

258,716 January 10, 1994 Slowinski & Gage
34 1,257,787

378,632 September 3, 1996 Slowinski & Gage
35 1,398,269
420,921 November 13, 1996 GIMPS / Joel Armengaud
36 2,976,221
895,932 August 24, 1997 GIMPS / Gordon Spence
37 3,021,377
909,526 January 27, 1998 GIMPS / Roland Clarkson
38 6,972,593
2,098,960 June 1, 1999 GIMPS / Nayan Hajratwala
39 13,466,917
4,053,946 November 14, 2001 GIMPS / Michael Cameron
40 20,996,011
6,320,430 November 17, 2003 GIMPS / Michael Shafer
41 24,036,583

7,235,733 May 15, 2004 GIMPS / Josh Findley
42 25,964,951
7,816,230 February 18, 2005 GIMPS / Martin Nowak

فرما این حدس مشهور را (که حکمی قطعی نبود) مطرح کرد که همه عددهای به شکل اول‌اند. در واقع به ازای n=1,2,3,4 داریم




که همه اول‌اند. اما اویلر در سال 1732 تجزیه را کشف کرد. پس (F(5 اعداد اول نیست. بعداً اول نبودن تعداد دیگری از این «عددهای فرما» هم معلوم شد؛ به دلیل دشواری اجتناب‌ناپذیر محاسبه مستقیم، روشهای عمیقتری برای تحقیق در هر مورد لازم است. تا کنون، اول بودن (F(n به ازای هیچ مقدار n>4 ثابت نشده است.
فرمول ساده و جالب توجه دیگری که عددهای اول بسیاری تولید می‌کند، فرمول

است به ازای(n=1,2,3,…,40، f(n اول است؛ به ازای n=41، داریم که اول نیست. عبارت
به ازای همه nها تا n=79 اعداد اول را به دست می‌دهد اما به ازای n=80، عدد حاصل اول.