عدد مرسن چیست؟

اعداد به شکل M_n=2ⁿ-1 که اول باشند, عدد مرسن می گویند.

اولین اعداد مرسن کوچک عبارتند از: 3, 7, 31, 127, 8191, 131071, 2147483647 و ... که متناظر هستند با ... ,89 ,61 ,31 ,19 ,17 ,13 ,7 ,5 ,3 ,2 =n

اعداد مرسن ابتدا به خاطر خواص قابل توجهشان مطالعه می شدند که این بود که هر عدد مرسن با یک عدد کامل رابطه داشت. وِلش یک تاریخچه بزرگ اعداد مرسن را نگه داری کرد.

اعداد به شکل M_n=2ⁿ-1 که اول باشند, عدد مرسن می گویند.

اولین اعداد مرسن کوچک عبارتند از: 3, 7, 31, 127, 8191, 131071, 2147483647 و ... که متناظر هستند با ... ,89 ,61 ,31 ,19 ,17 ,13 ,7 ,5 ,3 ,2 =n

اعداد مرسن ابتدا به خاطر خواص قابل توجهشان مطالعه می شدند که این بود که هر عدد مرسن با یک عدد کامل رابطه داشت. وِلش یک تاریخچه بزرگ اعداد مرسن را نگه داری کرد.

حدس زده شده است که اعداد مرسن نامتناهی هستند.

در نمودار اعداد مرسن M_p با p ≤ ln x, خطی که از بین نقاط می گذرد, بهترین خط تقریبی را با ln x 409/2 به ما می دهد. اگر خط محدود به گذشتن از میان نقاط نمودار نشد, بهترین نمودار, ln x (03/0±50/2) + (31/0±10/1-) هست.

تاریخچه

پیداکردن اعداد مرسن, با اشتباهات در محاسبه, بسیار چالش انگیز است. برای مثال, کشف سال 1963 که 2¹¹²¹³-1 اول است, به وسیله بسته های پستی مخصوص ساخته شده با مُهرِ فرستاده شده از یوبرانا, ایلینیوس اعلام شد.

وُلتمن, یک شبکه تحقیقاتی توزیع شده در اینترنت را برپا کرد که به GIMPS (Great Internet Mersenne Prime Search) معروف است و هر یک از صدها داوطلب آن, از کامپیوترهای شخصی خود برای انجام دادن گوشه ای از تحقیقات استفاده می کنند. در 17 نوامبر 2003, یکی از داوطلبان GIMPS کشف چهلمین عدد مرسن را گزارش داد و این کشف, پس از آن تأیید شد. تقریباً شش ماه پس از آن, کشف چهل و یکمین عدد مرسن توسط یکی از داوطلبان این شبکه اعلام شد. چهل و دومین عدد ناشناخته مرسن نیز در 18 فوریه 2005 اعلام شد و توان آن در 26 فوریه منتشر شد. تلاش های داوطلبان GIMPS, این پروژه محاسباتی توزیع شده را تبدیل به کاشف هشت عدد بزرگ تر اعداد مرسن نمود. در واقعیت, تا فوریه 2005, شرکت کنندگان GIMPS, تمام توان های زیر 9,889,900 را امتحان کرده بودند و دو بار چک کرده بودند و همه توان های پایین تر از 15,130,000 را دست کم یک بار امتحان کرده بودند.

قضیه ها و فرمول ها

قضیه1: اگر M_n اول باشد, n نیز باید خود اول باشد.

اثبات: فرض کنیم به ازای n مرکبی, 2ⁿ-1 اول است؛ در این صورت, می توان n را به صورت ضرب دو عدد غیر یک n = rs نوشت؛ پس:

2ⁿ -1    =     2^rs -1   =    (2^r)^s -1^s    =    (2^r -1)(…)

پس اگر s زوج باشد, طبق اتحاد مزدوج و اگر فرد باشد طبق اتحاد چاق و لاغر (لاگرانژ) به عوامل اول تجزیه می شود و اول نیست؛ پس به تناقض می رسیم و n باید اول باشد.

اعداد مرسن و رابطه با اعداد کامل

واضح است که اعداد مرسن به صورت 2ⁿ-1, در مبنای دو به صورت (100…0-1)₂ است که برابر (11…1)₂ است (تعداد یک ها برابر n است).

تعریف: عدد کامل عددی است که با مجموع مقسوم علیه های خود, به جز خودش, برابر باشد؛ مانند:   6=3+2+1   و      28=14+7+4+2+1

قضیه2: هر عدد کامل به صورت 2^n-1(2ⁿ-1) است که 2ⁿ-1 اول است.

پس یافتن هر عدد مرسن در واقع یافتن یک عدد کامل است و اثبات چندان سختی ندارد.

برای مثال به نمایش چهار عدد نخست کامل در مبنای دو توجه می کنیم:

1+10+11 = 110

1+10+1000+111+1110 = 11100

1+10+100+1000+10000+11111+111110+1111100+11111000 = 111110000

اگر دقت کنید, 11=1-2² , 111=1-2³ , 11111=1-2⁵ , همگی باید اول باشند؛ زیرا در غیر این صورت, خود این عدد تجزیه می شود؛ در نتیجه, تعداد مقسوم علیه های عدد کاملِ آن بیشتر شده و مجموع آن ها از خود عدد بیشتر می شود و دیگر عدد کامل نیست.

پس این ها اعداد مرسن هستند و متعاقباً توان های آن ها اول است.

پس با یافتن هر عدد کامل, می توان یک عدد مرسن جدید پیدا کرد.

آزمایش لوکاس- لمر

تقسیم آزمایشی اکثراً برای تصدیق مرکب بودن یک عدد مرسن اول پنهان استفاده می شود.

این آزمایش, فوراً نشان می دهد که M_p به ازای p=11,23,83,131,179,191,239,251 مرکب است (به ترتیب با عوامل اول 23, 47, 167, 263, 359, 383, 479 و 503).

یک آزمایش بسیار قدرتمند اولیه برای شناسایی M_p  آزمایش لوکاس- لمر است:

اگر n ≡ 3 به پیمانه 4 و n اول باشد, در این صورت 2n+1 | M_n , اگر 2n+1 اول باشد. همچنین این درست است که عوامل اول 2^p-1  باید شکل 2kp+1 داشته باشند که k یک عدد مثبت طبیعی است و در عین حال شکل 8n+1 یا 8n-1 را داشته باشد (آسپنسکی و هیسلت 1939).

یک عامل اول p از یک عدد مرسن M_q = 2^q-1 (چه اول و چه مرکب), در صورتی عدد ویفریچ اول است که p² | 2^q-1 . بنابراین, یک عدد مرسن نمی تواند عدد ویفریچ اول باشد.

نظریه ها و سؤالات حل نشده اعداد مرسن

آیا عدد کامل فرد وجود دارد؟

ما می دانیم که تمام اعداد کامل, به صورت حاصل ضرب یک عدد اول مرسن  توانی از دو می باشد؛ اما در مورد اعداد فرد کامل چه طور؟

اگر این عدد یکی است, در این صورت, به صورت حاصل ضرب یک مربع کامل در یک عدد اول به توان فرد می باشد, این عدد بر حداقل هشت عدد اول بخش پذیر است و حداقل 37 عامل اول دارد (لزومی ندارد که متمایز باشند)؛ این عدد حداقل در مبنای اعشاری 300 رقم دارد؛ و یک مقسوم علیه اول بزرگ تر از 10²⁰ دارد.

آیا تعداد اعداد مرسن بی نهایت است؟

جواب این است که احتمالاً بله (زیرا سری هارمونیک بی نهایت است).

آیا تعداد اعداد مرسن مرکب بی نهایت است؟

یولر نشان داد که:

نظریه: اگر k>1  باشد و  p = 4k+3  اول باشد, در این صورت 2p+1 نیز اول است, اگر و تنها اگر باقی مانده تقسیم 2^p بر 2p+1 برابر 1 باشد.

همچنین اگر p = 4k+3 باشد و 2p+1 اول باشد, در این صورت عدد مرسن   2^p-1 مرکب است (و به نظر می آید که این حدس منطقی باشد که تعداد اعداد اولی که به ازای p به صورت 2p+1 باشد, بی نهایت باشد).

حدس جدید مرسن

بیتمن, سلفریج و واگستاف, حدس زیر را زده اند:

فرض کنیم p هر عدد طبیعی فرد باشد؛ در این صورت اگر دو شرط اول - که در زیر آمده است- برقرار باشد, گزاره سوم برقرار خواهد بود:

1(     1-/+^k2 = p    یا    3-/+^k4 = p

2(     1-^p2 عدد اول باشد (بدیهی است که عدد مرسن اول است.).

3(     3/(1+^p2) عددی اول است.

توجه داشته باشید که این حدس چگونه به حدس قبلی وابسته است.

این سؤال بیشتر از این که یک حدس باشد (که ما حدس می زنیم درست باشد.), در زمره سؤال های جواب داده نشده است (که ما جواب آن را نمی دانیم.). به راحتی می توان نشان داد که اگر مربع عدد اول p بر یک عدد مرسن تقسیم شود, در این صورت p یک عدد اول ویفریچ است و این اعداد کمیاب هستند! فقط دو عدد شناخته شده اند که زیر 4,000,000,000,000 هستند و هیچ کدام از این مربع ها بر یک عدد مرسن  بخش پذیر نیستند.

اگر دنباله ای به این صورت باشد که A_p = 2^Ap-1-1   و   A₀=2, آیا همه این دنباله اول هستند؟

به قول دیکـسون کاتـالان, در پاسخ این سؤال در سال 1876, به لوکاس اظهـار داشــت که 2¹²⁷-1 (A₄), به این ترتیب اول است.

این اعداد در این دنباله خیلی سریع, بزرگ می شوند:

C0 = 2                (اول)

C1 = 3                (اول)

C2 = 7                (اول)

 C3 = 127            (اول)

C4 = 170141183460469231731687303715884105727        (اول)

C5 > 10^{51217599719369681879879723386331576246}      (آیا این عدد اول است؟)

به نظر می آید احتمال این خیلی کم باشد که A₅ (یا چند عدد بزرگ تر از این دنباله) اول باشد؛ به طوری که به مثال دیگری از «قانون قوی عددهای کوچک» جُوی, شک نمی رود. توجه داشته باشید که اگر یک عدد زوج و مرکب در این دنباله پیدا شود, طبق نظریه اول, تمام اعداد بعدی مرکب خواهند بود. (لاندن کورت نول به من گفت که او از برنامه اش استفاده می کند تا جست و جو کند که A₅, مقسومٌ علیه اول کوچک تر از 10⁵¹ دارد یا نه.)