عدد اول مرسن
اعداد اول مرسن ، اعداد اولی به فرم formula_1 هستند که به افتخار نام کشیش فرانسوی مارین مرسن ، به این نام خوانده می‌شوند. چرا که مرسن در زمینهٔ اول بودن این نوع اعداد اظهار نظری نادرست اما محرک کرده بود. اولین اعداد مرسن اعداد زیر هستند: ۳، ۷، ۳۱، ۱۲۷، ۸۱۹۱، ۱۳۱۰۷۱، ۲۱۴۷۴۸۳۶۴۷ و … که متناظر هستند با … ،۸۹ ،۶۱ ،۳۱ ،۱۹ ،۱۷ ،۱۳ ،۷ ،۵ ،۳ ،۲ =n
قضیه اول: اگر formula_2 اول باشد، formula_3 نیز باید خود اول باشد.
اثبات: فرض کنیم که حکم نادرست است (برهان خلف). یعنی به ازای formula_3 مرکبی، formula_5 اول است؛ در این صورت می‌توان formula_3 را به صورت ضرب دو عدد غیر یک formula_7 نوشت. پس:
formula_8 پس اگر formula_9 زوج باشد، طبق اتحاد مزدوج و اگر فرد باشد طبق اتحاد چاق و لاغر (لاگرانژ) به عوامل اول تجزیه می‌شود و اول نیست؛ پس به تناقض می‌رسیم و فرض خلف باطل است. پس formula_3 باید اول باشد.
بدیهی است که اعداد مرسن در مبنای دو به صورت formula_11 می‌باشد که برابر formula_12 است (formula_13تا یک).
تعریف: عدد کامل (تام) عددی است که با مجموع مقسوم علیه‌های خود، به جز خودش، برابر باشد. از معروفترین آن‌ها ۶=۳+۲+۱ و ۲۸=۱۴+۷+۴+۲+۱ هستند.
قضیه دوم: هر عدد کامل به صورت formula_14 است که formula_15 اول است.
این‌ها اعداد به شکل formula_15 مرسن هستند و متعاقباً توان‌های آن‌ها (formula_13)اول است. پس با یافتن هر عدد کامل، می‌توان یک عدد مرسن جدید پیدا کرد.
تقسیم آزمایشی اکثراً برای تصدیق مرکب بودن یک عدد مرسن اول پنهان استفاده می‌شود. این آزمایش فوراً نشان می‌دهد که formula_18 به ازای formula_19 مرکب است (به ترتیب با عوامل اول ۲۳، ۴۷، ۱۶۷، ۲۶۳، ۳۵۹، ۳۸۳، ۴۷۹ و ۵۰۳).
یک آزمایش بسیار قدرتمند اولیه برای شناسایی formula_18 آزمایش لوکاس- لمر است.
ابتدا سه قضیه زیر را مطرح می‌کنیم:
می‌دانیم تمام اعداد کامل به صورت حاصل ضرب یک عدد اول مرسن توانی از دو می‌باشند؛ اما در مورد اعداد فرد کامل چه نظریه‌ای وجود دارد؟ اگر این چنین عددی وجود داشته باشد در این صورت، به صورت حاصل ضرب یک مربع کامل در یک عدد اول به توان فرد می‌باشد، این عدد حداقل هشت عامل اول دارد و حداقل بر ۳۷ عدد اول بخش پذیر است (لزومی ندارد که متمایز باشند)؛ این عدد حداقل در مبنای اعشاری ۳۰۰ رقم دارد؛ و یک مقسوم علیه اول بزرگ‌تر از ۱۰۲۰ دارد.
این سؤال معادل با پاسخ دادن به این سؤال است که آیا تعداد نامحدودی عدد کامل زوج است. جواب این است که احتمالاً بله است (زیرا سری هارمونیک واگراست).
نظریه اولر: اگر formula_33 باشد و formula_34 اول باشد، در این صورت formula_32 نیز اول است، اگر و تنها اگر باقی‌مانده تقسیم formula_36 بر formula_32برابر formula_38 باشد.
همچنین اگر formula_34 باشد و formula_32اول باشد، در این صورت عدد مرسن formula_32 مرکب است (این حدس احتمالاً منطقی است از آن جایی که تعداد اعداد اولی که به ازای formula_13 به صورت formula_43 باشد، بی‌نهایت است).
بیتمن، سلفریج و واگستاف حدس زیر را زده‌اند: فرض کنیم formula_13 هر عدد طبیعی فرد باشد؛ در این صورت اگر دو شرط اول -که در زیر آمده‌است- برقرار باشد، گزاره سوم برقرار خواهد بود:
توجه داشته باشید که این حدس چگونه به حدس قبلی وابسته‌است.
این سؤال بیشتر از این که یک حدس باشد، از دسته سؤال‌های جواب داده نشده‌است. به راحتی می‌توان نشان داد که اگر مربع عدد اول formula_13 بر یک عدد مرسن تقسیم شود، در این صورت formula_13 یک عدد اول ویفریچ است و این اعداد کمیاب هستند! فقط دو عدد شناخته شده‌اند که زیر ۴٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰ هستند و هیچ‌کدام از این مربع‌ها بر یک عدد مرسن بخش پذیر نیستند.
اگر دنباله‌ای به این صورت باشد که formula_51 و formula_52 آیا همه این دنباله اول هستند؟ دیکسون کاتالان، در پاسخ این سؤال در سال ۱۸۷۶، به لوکاس اظهار داشت که ۱–۱۲۷^۲ (formula_53)، به این ترتیب اول است. همان‌طور که مشخص است این اعداد در این دنباله بسیار سریع بزرگ می‌شوند:
C0 = ۲ (اول)
C1 = ۳ (اول)
C2 = ۷ (اول)
C3 = ۱۲۷ (اول)
C4 = ۱۷۰۱۴۱۱۸۳۴۶۰۴۶۹۲۳۱۷۳۱۶۸۷۳۰۳۷۱۵۸۸۴۱۰۵۷۳۷ (اول)
51217599719369681879879723386331576246^10 عدد مرکب پیدا شود، طبق نظریه اول، تمام اعداد بعدی مرکب خواهند بود.
در سال ۱۹۶۳ کشف شد که ۱–۱۱۲۱۳^۲ اول است، و این به وسیله بسته‌های پستی مخصوص ساخته شده با مُهرِ فرستاده شده از "یوبرانا، ایلینیوس" اعلام شد. یک شبکه تحقیقاتی توزیع شده در اینترنت توسط "ولتمن" به پا شده‌است که به GIMPS(Great Internet Mersenne Prime Search) معروف است و و داوطلبان بیشمار آن، از کامپیوترهای شخصی خود برای انجام دادن قسمت‌های مختلفی از تحقیقات استفاده می‌کنند. در ۱۷ نوامبر ۲۰۰۳، یکی از داوطلبان GIMPS کشف چهلمین عدد مرسن را گزارش داد و این موضوع، پس از آن تأیید شد. شش ماه پس از آن، کشف چهل و یکمین عدد مرسن توسط یکی از داوطلبان این شبکه به ثبت رسید. عدد بعدی مرسن در این سری نیز در ۱۸ فوریه ۲۰۰۵ اعلام شد. تلاش‌های داوطلبان GIMP، این پروژه محاسباتی توزیع شده را تبدیل به کاشف هشت عدد بزرگ‌تر اعداد مرسن نمود. در واقعیت، تا فوریه همین سال، شرکت کنندگان GIMPS، تمام توان‌های قبل از ۹٬۸۸۹٬۹۰۰ را امتحان کردند و حتی دو بار چک کردند و همه توان‌های پایین‌تر از ۱۵٬۱۳۰٬۰۰۰ را دست کم یک بار امتحان کردند.