X
تبلیغات
شهر ریاضی - اعداد اول

شهر ریاضی

وبلاگی است مفید برای همه ی ریاضی دوستان و آماده برای پاسخگویی به سوالات شما

اعداد اول

مقدّمه:

 

براستى كه دنياي رياضيّات دنياي شـگفتي است.این شـگفتي نه  بر اساس ادّعاي من  بلكه از كار هاي رياضــيدانان ﭙيشـين كه به رمز و رموز اعداد ﭘﻲ بـرده بودند هويداســت. يكى از اين شــگفتي ها رابطه بين اعداد و بعضي از خواصّ جالب ﺁنــهاست.از جملهء این خواصّ ایـن اسـت که بعضی از آنــها به غیـر از خود و عدد 1 بر عددی دیگر قابل قسـمت نیســتند و این برای پیشـینیان جالب توجّه می نمود و در این مورد ســالها صرف تحقیق و مطالعه نمودند تا به چندین فرمول که تعداد اعداد اوّل را بطور تقریبی درمحدوده ی معیّنی مشخّص می نمود دست یافتند.

دامنه ی ایـن اعداد به مـرور زمان وســیع تـر شـد و هـر ســال که  

می گذشت به اعداد اوّل بزرگتری دست می یافتند.

این تحقـیق هــم که درمورد اعداد اوّل اسـت و به خــاطر علاقه ی اینجانب به شناخت آنها صورت گرفته است.

 

                                                   «میثم پرتوی زادهء بنام»

 


 

 

 

 

 

 

 

 

1

فهرست

ﻧﻴﻢ نگاهی به اعداد اوّل و تاریخچه ی آنها.............................3

 

برخی از ویژگیهای اعداد اوّل...........................................5

 

غربالها و روش هایی برای یافتن اعداد اوّل..........................6

 

مسائل حل نشده ی اعداد اوّل...........................................10

 

بزرگترین اعداد اوّل شناخته شده......................................11

 

منابع و مأخذ.......................................................14

 

 

 

 

 

 

 

 

 

 

 

 

 

2

نیم نگاهی به اعداداوّل و تاریخچه ی آنها

 

از همــان اوّل اعداد اوّل و خاصیّت هایشـــان مورد مطالعه ی ریاضــیدانان باستان یونانی قرار داشت،ریاضیدانان مکتب فیثاغورس(Pythagoras)سرگرم مطالعه ی نکـات پوشــیده ی اعداد و خواصّ آنها بودند.آنها ایـده ی اوّل بودن را فهمـیدند و به مطالعه ی اعداد کامل و اعداد متحابّه مشغول شدند.

عدد کامل عددی اسـت که مجموع مقسوم علیه های جزء(مقسوم علیه های یک عدد بجز خودش) آن با خود عدد برابر است.مثال:

D28={1,2,4,7,14,28}          1+2+4+7+14=28

 و دو عدد متحابّه دو عددی هســتند که مجمع مقسوم علیه های صحیح جزء هرکدام با عدد دیگر برابر است.مثال:

D220={1,2,4,5,10,11,20,22,44,55,110,220}     1+2+4+5+10+11+20+22+44+55+110=284

D284={1,2,4,71,142,284}

1+2+4+71+142=220

زمانی که قوانیــن اقلیـدس((Euclid(در حدود300  ســال قبل از میلاد) پیدا شــدند  چندین نتیجه ی مهم درباره ی اعداد اوّل اثبات شده است.

در کــتاب نهم «قوانین اقلیـدس»،اقلیـدس اثبات کرد بی نهایت عدد اوّل وجود دارد.

این اثـبات یکی از اوّلین اثبات های مشــهور اســت که در روش برهان خلف برای رسیدن به نتیجه استفاده می شود.اقلیدس همچنین قضیّه ی اساسی حسـاب را که هر عدد طبیعی را می توان بصورت حاصلضرب اعداد اوّل نوشت اثبات کرد.

اقلیدس همچنین نشــان داد که اگر عدد2n-1 عددی اوّل باشدعدد2n-1(2n-1)  عددی کامل است.او توانست نشان دهد که همه ی اعداد زوج کامل بدین صورت میباشند.

البتّه این تمام دانسته های ما درامروز نیســت بلکه امروزه اعداد فرد کاملی نیزپیدا شده اند0 

در حدود 200 ســـال قبل از میلاد اراتوســتن(Eratosthenes) یونانی الگوریتمی     برای حساب کردن اعداد اوّل ابداع نمود که غربال اراتوستن نامیده شد.

ســپس یک لطمه ی دراز در تاریخ اعداد اوّل به وجود آمد که به ســـالهای تاریک  مشهور است.

پیشــرفت مهمّ بعدی بوســیله ی فرما ( (Fermatدرآغــاز قرن هفدهم بوجود آمد.او فرضـیّه آلبرت جرارد  (Albert Girard)را اثــبات کرد.فرضـیّه ی آلبرت جرارد چنین بود:«هـر عدد اوّل بصورت 4n+1  را می توان بصورت مجموع دو مربّــع کامل نوشـت» و او توانسـت نشــان دهد که هر عددی را می توان بصورت حاصل جمع چهار مربّع کامل نوشت.

او روشی جدید برای تجزیه ی اعداد بزرگ کشف کرد برای مثال او نشـان داد که:

3

46061×2027651281=44021

او بیان کرد که اگــرp عددی اوّل باشـــد آنگاه برای هــر عدد اوّل خواهیم داشــت:

                                                                                 (به سنجp  ap≡a(

این قضیّه نیمی از آنچه را که «فرضیّه ی چینی» نامیده می شود، بیان می کند.این قضیّه می گوید:اگرn عددی اوّل باشــــد آنگاه 2n-2 برn بخشـپذیر است.البته عکس ایــن قضیّه غلط اسـت چون 2341-2 بر341 بخش پذیر اسـت و 31×341=11 پس عددی غیر اوّل است.

قضیّه ی کوچک فرما،اســـاس نتایج دیـــگر درمورد تئوری اعداد اسـت و همچنین       پایه ای برای روش امتحـــان کردن اوّل بودن اعداد اســت و هنوز درکامپیوترهای   امروزی کاربرد دارد.

فرما با ســایرریاضیدانان زمان خود مخصوصاً مایک مارین مرسن(Mersenne)

نامه نــگاری می کرد. او در یکی از نامه هایش بـه مرسـن تـخمین زده بود که عدد 2n+1 هنگامی که n توانی از2 اسـت اوّل می باشــد.او این قضیّه را در صورتیکه n=1,2,4,8,16 باشـــد،تأیید کرد.اعدادی بدین صورت اعداد فرما نامیده می شوند.

در کمتر از صد ســـال اویلر((Euler نشان داد که 232+1 بر641 بخشپذیر است و

بنابرین اوّل نیست.

همچنین اعدادی به صورت 2n-1 مورى توجّه ودقّت قرار گرفتند ﭽون براحتى مى توان نشـــان داد كه اگرn اوّل نباشــد2n-1  مرکّب است.اﻴﻥ اعداد را معمولاً  اعداد مرسن می نامند چون آنـــها را اوّﻟﻴﻥ بار مرسن مورد مطالعه قرار داد.البته همه ی

 اعداد بصورت 2n-1 که در آنـــها n اوّل اســت،اوّل نیســـتند.مثلاًً211-1=2047 و

89×2047=23 و مرکّب اسـت. به این موضوع برای اوّلین بار در ســــال 1536 توجّه شد.

برای سـال های بسیار،اعدادی به این شکل،بزرگترین اعداد اوّل شناخته شده بودند. اوّل بودن M19(219-1) در سال 1588 بوسیله ی کاتادلی (Catadli) اثبات شد.این عدد برای200 ســـــال بزرگترین عدد اوّل شناخته شده بود تا اینکه اویلر ثابت کرد M31  نیز اوّل اسـت.او با این کشف رکوری را بر جا گذاشت که تا یک قرن دیـگر شکسته نشد.

بعدها لوکاس نشان داد M127 نیز اوّل اسـت این کشف نزدیک به عصر رایانه های 

الکترونیکی بود.

در ســــال 1952 اوّل بودن اعداد مرسن M521 و M607و M1279و M2203و M2281 توسّط رابینسون اثبات شد و بدین ترتیب عصر الکترونیک آغاز شد.

 

                                   

 

 

 

4

برخی از ویژگی های اعداد اوّل

 

 .1هــــر عدد اوّل (به جز2,3 ) برابر اسـت با 6n±1 که در آن n یک عدد صحيح  است.

2. مجــذور هـــر عدد اوّل (به جز2,3 ) برابر اسـت با 24n+1 در آن n يک عدد صحيح است.

3. تفاضل مجـذورهای دو عدد اوّل (زمانی که هیچ کدام2,3  نیســـتند) مضربی از 24 است.

4. حاصل ضرب هـــر دو عدد(به جز2,3 ) برابر اسـت با 6n±1 که در آن n يک عدد صحيح است.

5. توان چهارم هـر عدد اوّل (به جز2,3,5) بصورت 240n+1 اسـت که در آن n يک عدد صحيح است.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  

5

غربال ها و روش هایی برای یافتن اعداد اوّل

 

غربال اراتوستن:

فرض کنیم کـه بخواهیم اعداد اوّل را در فاصـــله ی عدد 2 تا عدد صحـیح n ، پیدا    کنیم. ابتدا، اعداد صحـیح را از2 تاn  به ردیف می نویسـیم.نخسـتین عدد اوّل برابر است با2، زیر عدد2  و روی همه ی مضارب 2(اعداد زوج) خط می کشــیم.اوّلین عددی که می ماند، 3است. زیر آنرا،به عنوان عدد اوّل خط می کشیم و روی اعداد مضرب3 خط می زنیم. اوّلین عدد باقیمانده5 است (عدد4 ،قبلاً خط خورده اسـت.)

زیر ایـن عدد به عنوان یــک عدد اوّل خـط می کشــیم  و بقـیّه اعداد را 4  در میان

( عددهایی را که مضرب 5 هستند)، خط می زنیم و به همین ترتیب تا آخر.همه ی

اعدادی که روی آنها خط کشیده نشده است اعداد اوّل هستند.  

البتّه این کار را تا عدد معیّنی انجام می دهیم واین عدد معیّن بزرگترین عددی است که از  کوچکتر اســت. مثلاً اگر خواسـتیم اعداد اوّل 2 تا700  را پیدا کنیم جذر عـدد 700 تقریباً برابر اسـت با26/547  و بزرگترین عدد اوّل کوچکتر از ، اسـت. پـس ما باید برای یافتن اعـداد اوّل 2 تا700 ، ایـن کار را تا عـدد23  انجام

می دهیم.

مثال:

        2    3    4    5    6    7    8    9  10

11  12  13  14  15  16  17  18  19  20

21  22  23  24  25  26  27  28  29  30

31  32  33  34  35  36  37  38  39  40

41  42  43  44  45  46  47  48  49  50

ایـن روش غربال کردن تدریجی اعـداد ، در بیش از 2000 سـال پیش به وسـیله ی اراتوستن (سالهای 196-276   پیش از میلاد) ، در نظر گرفته شد.

اراتوستن روی مضارب 2،3،5 وغیره راخط نمی کشید، بلکه انها را با یک چوب کوچک ، سوراخ می کرد مثل ایـن که اعـداد غیر اوّل را ، از سوراخ های غـربال بیرون می کرد و تنها اعداد اوّل را نگه می داشت. تا امروز هم این روش به دست اوردن اعـداد اوّل را غربال اراتوسـتن می نامند. این روش ، همانـطور که مشاهده می شود ، بسـیار دقیق و قابل اعتماد است .

غربالی جدید برای اعداد اوّل

در دو هزار سالی که زمان ما را ، از زمان اراتوسـتن جدا می کـند ، روش « الک کردن» اعداد اوّل، از به کاربردن « غربال » ساده و ابتدایی تا استفاده ازماشینهای  الکترونیکی محاسبه ، تکامل پیدا کرده است .

ولی ، برای نیازهای کوچک ، همیـشه می توان از همان « غربال دسـتی » استفاده   

6

کرد. منتهی این غربال هم به تدریج، پیشرفت کرده و روش جستجوی اعداد اوّل را 

ساده تر کرده است . مثلاً « س . پ . سوندار » دانشجوی ریاضـــی هندی در سال  1944  ، یکی از این « غربالهای » جدید را درست کرده است .

 4     7    10    13    16    …

 7    12   17    22    27    …

10   17   24    31    38    …

13   22   31    40    49    …

16   27   38    49    60    …

…………………………..  

این « غربال» از بی نهایت تصاعد حسابی نامحدود درست شده است،که جملهً اوّل آنها ، به ترتیب جمله های تصاعد اوّل است :

4,7,10,13,16,19,22,…

قدرنسبت این تصاعدها ، به ترتیب اعداد فرد متوالی اند که از 3 شروع شده باشد :

 

اگر عددی مثل N در این جدول وجود داشته باشـد ، بدون تردید ، عدد  غیر

اوّل است و اگر عدد N ، در این جدول وجود نداشته باشد  عددی اوّل است.

مثلاً عدد 6 در جدول نیست پس 13 عددی اوّل است 10 در جدول وجود دارد پـس

21 اوّل نیست .

غربال جدید دیگری

میدانیم که عدد فرد N ،در تقسیم بر 6 ، باقیمانده ای مسـاوی 1 ،3 یا 5 دارد . اگـر

باقیمانده ی تقسیم عدد فرد N بر 6 مسـاوی 3 باشـد، عددی غیر اوّل اسـت و بر 3 

بخشپذیر است و این به معنای آن است که اعداد اوّل را باید بین آنهایی که بصورت

 هستند، جستجو کرد (در تقسیم بر6 ،باقیمانده 5 ،معادل است با باقیمانده -1)

میروسلاو سااوکوپ ( از پراگ ) ، مهندس ارتباطات ،بر اساس این وضع در سال

1954 ، این جدول « غربال » را تشکیل داده است :

 

                                                      6n+1 غیر اوّل است

                                                       


   

 6n-1غیر اوّل است                             

7

سطری که در وسط جدول قرار گرفته اسـت، نقشی ندارد این خط تنها جدول را به دو قسمت بالا و پایین تقسیم می کند . وقتی که عدد n  در قسمت پایین جدول وجود نداشته باشد، 6n-1 عددی است اول. همچنین، عدد 6n+1  وقتی اوّل است که عدد

n در قسمت بالای جدول وجود نداشته باشد.

مثلاً، عدد  n=13 در قسمـت بالای جدول نیسـت ، بنا بر این 1+13× 6 یعنی  79 

عددی است اوّل، درقسمت پایین جدول n=13 وجود دارد ، بنا بر این 13-1 ×6 ،

یعنی 77 عددی غیراوّل است.عدد 149 ، عددی اوّل است، زیرا داریم:

25-1 ×149=6 ،ولی عدد n=25 در قسمت پایین جدول پیدا نمی شود.

راه دیگری برای پیدا کردن عددهای اوّل

عـدد  1وn عـدد اوّل اوّلیّه را در نظر می گـیریم . همه ی این عـددها را به  ترتیب

دلخواهی ، به دو گروه تقسیم می کنیم. عددهای هر گروه را درهم ضرب می کنیم.

به این ترتیب  ، دو حاصل ضرب به دســت می آید . اگر مجموع  یا تفاضل این دو

حاصل ضرب ( که آنرا N می نامیم ) از مجذور(n+1 ) امین عدد اوّل ،  کوچکتر

باشد، در این صورت ،N عددی است اوّل.

مثلاً ، عدد 1 و چهار عدد اوّل اوّلیّه را درنظر می گیریم :1 ،2 ،3 ،5 و7. پنجمین

عـدد اوّل مسـاوی 11 می باشـد ، که مجذور آن 121  اسـت . یعنی با این  روش ،

می توانیم عددهای اوّل کوچکتر از 121  را معین کنیم .

عددهای انتخابی را به دو گروه تقسـیم می کنیم : 2،3،5،7  (گروه اوّل) ، 1 (گروه

دوّم )،عدد 7-1 ×5×3×2 ، یعنی 209 ،از121 بزرگتر است، بنا بر این نمی توان فهمید که آیا این عدد اوّل اسـت یا غیر اوّل. در واقع ، در جدول عددهای اوّل ، این عدد وجود ندارد.

عددهای انتخابی را به نحو دیگری به دوگروه تقسیم می کنیم:1،3،5،7(گروه اوّل)

2(گروه دوّم). دو عدد را تشکیل می دهیم :

هر کدام از این دو عدد از121 کوچکترند ، بنا بر این هر دوی آنها ، عددهایی اوّل

هستند. در واقع ، اگر اینها ،اوّل نباشند، باید قابل تجزیه به عاملهای اوّل باشند،ولی

از طرز تشکیل این عددها معلوم است که هیچ کدام از آنها بر 2،3،5 یا7 بخشـپذیر

نیستند . روشن اسـت که این عددها ، برعدد اوّل بعد از آنها ، یعنی 11 هم بخشپذیر نیست.

در واقع ، اگر   یا  بر   11 بخش پذیر باشـد ، چون هر کدام از آنها از 121

کوچکترند ، باید خارج قسمت از11 کوچکتر شـود و بنا بر این نمیتواند عامل اوّلی 

به جز 2،3،5 یا 7 داشته باشد. در حالیکه قبلاً گفتیم که هیچکدام از این چهار عدد،

عامل  یا  نیستند.

اگر در گروه اوّل،عددهای1،5 و7 و در گروه دوّم،عددهای2و3 را قرار می دادیم،

میتوانستیم دو عدد اوّل دیگر بدست آوریم :

8

و یا، با تغییر عددهای گروهها :

روشن اســت که می توان هر عامل گروه اوّل  یا گروه دوّم را با توان دلخواهی در نظر گرفت. تنها شرطی که برای اوّل بودن مجموع  یا  تفاضل حاصلضرب وجود

دارد، همانست که از مجذور عدد اوّل (n+1) ام کوچکتر باشند :

به این ترتیب ،مثلاً تنها با استفاده از سه عدد 1،2و3 ،می توان همه ی عددهای اوّل کوچکتر از 25 را به دست آورد.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

9

مسائل حل نشده ی اعداد اوّل

 

.1 آیا تمام اعـداد زوج بزرگتر از2  را می توان بصورت مجموع دو عدد اوّل  نوشت؟

2. آیا بی نهایت عدد اوّل به شکل  وجود دارد؟

3. آیا همیشه یک عدد اوّل بین  و  وجود دارد؟

4. آیا نامحدود عدد اوّل فرما وجود دارد ؟ به راســتی آیا هیچ عدد اوّل فرما بعد از

چهارمین عدد فرما وجود دارد؟

5. آیا بی نهایت تصاعـد بلند ریاضی از اعداد اوّل متوالی  وجود دارد؟  مثلاً 269،

263،257،251 که به طول 4 عدد اسـت . بزرگترین مثال شـناخته شده به طول 7

عدد است .

6.     برای   اوّل اســت . آیا بی نهایت عـدد اوّل به این شکل

وجود دارد ؟ همین سئوال برای   که برای   اوّل اسـت ،

مطرح می شود.

7. آیا بی نهایت عدد اوّل به شکل 1+#n وجود دارد ؟ (بطوریکه #n  حاصلضرب

همه ی اعداد اوّل کوچکتر یا مساوی n است .)

8. آیا بی نهایت عدد اوّل به شکل -1#n  وجود دارد؟

9. آیا بی نهایت عدد اوّل به شکل n!+1  وجود دارد؟

10. آیا بی نهایت عدد اوّل به شکل n!-1  وجود دارد؟

11. اگر p اوّل باشد، آیا 2p-1 همیشـــه مربع آزاد است؟( به این معنی که بر مربع یک عدد اوّل بخش پذیر نیست)

12. آیا دنباله ی فیبوناچی شامل بی نهایت عدد اوّل است؟

 

 

 

 

 

 

 

 

 

 

 

 

 

10

بزرگترین اعداد اوّل شناخته شده

 

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

 

ردیف

عدد اوّل

تعداد ارقام

سال کشف

1

  232582657-1

9808358

2006

2

230402457-1

9152052

2005

3

225964951-1

7816230

2005

4

224036583-1

7235733

2004

5

220996011-1

6320430

2003

6

213466917-1

4053946

2001

7

29167433+1×27653

2759677

2005

8

27830457+1×2843302

2357207

2004

9

26972593-1

2098960

1999

10

25054502+1×5359

1521561

2003

 

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

 

ردیف

اعداد اوّل

تعداد ارقام

سال کشف

1

2171960±1×100314512544015

51780

2006

2

2171960±1×16869987339975

51779

2005

3

2169690±1×33218925

51090

2002

4

2114689±1×60194061

34533

2002

5

2107520±1×1765199373

32376

2002

 

 

 

 

 

 

 

 

 

 

11

بزرگترین اعداد اوّل مرسن:

 

ردیف

عدد اوّل

تعداد ارقام

سال کشف

1

M32582657

9808358

2006

2

M30402457

9152052

2005

3

M25964951

7816230

2005

4

M24036583

7235733

2004

5

M20996011

6320430

2003

6

13466917 M

4053946

2001

7

M6972593

2098960

1999

8

M3021377

909526

1998

9

M2976221

895932

1997

10

M1398269

420921

1996

 

بزرگترین اعداد اوّل فاکتوریلی:

 

ردیف

عدد اوّل

تعداد ارقام

سال کشف

1

34790!-1

142891

2002

2

26951!+1

107707

2002

3

21480!-1

83727

2001

4

6917!-1

23560

1998

5

6380!+1

21507

1998

6

3610!-1

11277

1993

7

3507!-1

10912

1992

8

1963!-1

5614

1992

9

1477!+1

4042

1984

10

974!-1

2490

1992

 

 

 

 

 

 

 

 

12

بزگترین اعداد اوّل«primorial» (بصورت n#±1):

 

ردیف

عدد اوّل

تعداد ارقام

سال کشف

1

392113#+1

169966

2001

2

366439#+1

158936

2001

3

145823#+1

63142

2000

4

42209#+1

18241

1999

5

24029#+1

10387

1993

6

23801#+1

10273

1993

7

18523#+1

8002

1989

8

15877# -1

6845

1992

9

13649#+1

5862

1987

10

13033# -1

5610

1992

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

13

منابع و مأخذ

 

 .1کتاب اندیشه ریاضی  تألیف بوریس آناستاسویچ کوردمسکی و ترجمه پرویز شهریاری

 .2سایتهای اینترنتی :

www-groups.dcs.st-and.ac.uk

prime.utm.edu

fa.wikipedia.org /wiki

 

 

 

 

 

 

 

 

 

 

+ نوشته شده در  دوشنبه 5 اسفند1387ساعت 17:45  توسط Meysam  |