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

بزرگترین عدد اول
بزرگ ترین عدد اولی که تا کنون کشف شده است، عدد ۱- ۲۳۰۴۰۲۴۵۷ است که ۹۱۵۲۰۵۲ رقم دارد.
عدد اول : هر عدد طبیعی بزرگ تر از یک که فقط بر خودش ویک بخش پذیر باشد،عدد اول نامیده می شود. مثل ۲ ، ۳ ، ۵ ، ۷ ، …
عدد مرکب : هرعدد طبیعی بزرگ تراز یک که به جز خودش و یک بر عدد طبیعی دیگری نیزبخش پذیر باشد، عددی مرکب نامیده می شود . مثل ۴ ، ۶ ، ۸ ، ۹ ، …
عدد مرسن :اعداد اولی به شکل ۱- 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 را به صورت یکتایی به صورت حاصل ضرب عوامل اول نوشت:

که در آن ها اعداد اول متمایز می باشند.
* توجه: اگر n=1 باشد آنگاه که در ان P هر عدد اولی است.
* لازم به توضیح است که ممکن است در تجزیه یک عدد طبیعی به عوامل اول، تعدادی از عوامل یکسان باشند. به عنوان مثال: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
مشخص نیست
ناشناس
2
3

1
مشخص نیست
ناشناس
3
5

2
مشخص نیست
ناشناس
4
7

3
مشخص نیست
ناشناس
5
13

4
1456
ناشناس
6
17

6
1588
Cataldi
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، عدد حاصل اول.

32