عدد اول مرسن

بدیهی است که اعداد مرسن در مبنای دو به صورت ${\displaystyle ((100\cdots 0)-1)_{2}}$ می‌باشد که برابر ${\displaystyle (11\cdots 1)_{2}}$ است (${\displaystyle p}$تا یک).

تعریف: عدد کامل (تام) عددی است که با مجموع مقسوم علیه‌های خود، به جز خودش، برابر باشد. از معروفترین آن‌ها ۶=۳+۲+۱ و ۲۸=۱۴+۷+۴+۲+۱ هستند.

قضیه دوم: هر عدد کامل به صورت ${\displaystyle (2^{p}-1)(2^{p-1})}$ است که ${\displaystyle 2^{p}-1}$ اول است.

این‌ها اعداد به شکل ${\displaystyle 2^{p}-1}$ مرسن هستند و متعاقباً توان‌های آن‌ها (${\displaystyle p}$)اول است. پس با یافتن هر عدد کامل، می‌توان یک عدد مرسن جدید پیدا کرد.

تقسیم آزمایشی اکثراً برای تصدیق مرکب بودن یک عدد مرسن اول پنهان استفاده می‌شود. این آزمایش فوراً نشان می‌دهد که ${\displaystyle M_{p}}$ به ازای ${\displaystyle p=11,23,83,131,179,191,239,251}$ مرکب است (به ترتیب با عوامل اول ۲۳، ۴۷، ۱۶۷، ۲۶۳، ۳۵۹، ۳۸۳، ۴۷۹ و ۵۰۳).

یک آزمایش بسیار قدرتمند اولیه برای شناسایی ${\displaystyle M_{p}}$ آزمایش لوکاس- لمر است.

ابتدا سه قضیه زیر را مطرح می‌کنیم:

1. اگر ${\displaystyle n\equiv 3}$ به پیمانه ۴ و ${\displaystyle n}$ عدد اول باشد، در این صورت ${\displaystyle 2n+1|Mn}$، اگر ${\displaystyle 2n+1}$ اول باشد.
2. همچنین این درست است که عوامل اول ${\displaystyle 2^{p}-1}$ باید شکل ${\displaystyle 2kp+1}$ داشته باشند که ${\displaystyle k}$ یک عدد مثبت طبیعی است و در عین حال شکل ${\displaystyle 8n+1}$ یا ${\displaystyle 8n-1}$ را داشته باشد (آسپنسکی و هیسلت ۱۹۳۹).
3. یک عامل اول ${\displaystyle p}$ از یک عدد مرسن ${\displaystyle M_{p}=2^{p}-1}$ (چه اول و چه مرکب) در صورتی عدد ویفریچ اول است که ${\displaystyle p^{2}|2^{p}-1}$ . بنابراین یک عدد مرسن نمی‌تواند عدد ویفریچ اول باشد.

می‌دانیم تمام اعداد کامل به صورت حاصل ضرب یک عدد اول مرسن توانی از دو می‌باشند؛ اما در مورد اعداد فرد کامل چه نظریه‌ای وجود دارد؟ اگر این چنین عددی وجود داشته باشد در این صورت، به صورت حاصل ضرب یک مربع کامل در یک عدد اول به توان فرد می‌باشد، این عدد حداقل هشت عامل اول دارد و حداقل بر ۳۷ عدد اول بخش پذیر است (لزومی ندارد که متمایز باشند)؛ این عدد حداقل در مبنای اعشاری ۳۰۰ رقم دارد؛ و یک مقسوم علیه اول بزرگ‌تر از ۱۰۲۰ دارد.

این سؤال معادل با پاسخ دادن به این سؤال است که آیا تعداد نامحدودی عدد کامل زوج است. جواب این است که احتمالاً بله است (زیرا سری هارمونیک واگراست).

نظریه اولر: اگر ${\displaystyle k>1}$ باشد و ${\displaystyle p=4k+3}$ اول باشد، در این صورت ${\displaystyle p^{2}|2^{p}-1}$ نیز اول است، اگر و تنها اگر باقی‌مانده تقسیم ${\displaystyle 2p}$ بر ${\displaystyle p^{2}|2^{p}-1}$برابر ${\displaystyle 1}$ باشد.

همچنین اگر ${\displaystyle p=4k+3}$ باشد و ${\displaystyle p^{2}|2^{p}-1}$اول باشد، در این صورت عدد مرسن ${\displaystyle p^{2}|2^{p}-1}$ مرکب است (این حدس احتمالاً منطقی است از آن جایی که تعداد اعداد اولی که به ازای ${\displaystyle p}$ به صورت ${\displaystyle 2p+1}$ باشد، بی‌نهایت است).

بیتمن، سلفریج و واگستاف حدس زیر را زده‌اند: فرض کنیم ${\displaystyle p}$ هر عدد طبیعی فرد باشد؛ در این صورت اگر دو شرط اول -که در زیر آمده‌است- برقرار باشد، گزاره سوم برقرار خواهد بود:

1. ${\displaystyle p=2^{k}+/-1}$،${\displaystyle p=4^{k}+/-3}$
2. ${\displaystyle p=2^{k}-1}$ عدد اول باشد (بدیهی است که عدد مرسن اول است).
3. ${\displaystyle {\frac {2^{p}+1}{3}}}$ عددی اول است.

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

این سؤال بیشتر از این که یک حدس باشد، از دسته سؤال‌های جواب داده نشده‌است. به راحتی می‌توان نشان داد که اگر مربع عدد اول ${\displaystyle p}$ بر یک عدد مرسن تقسیم شود، در این صورت ${\displaystyle p}$ یک عدد اول ویفریچ است و این اعداد کمیاب هستند! فقط دو عدد شناخته شده‌اند که زیر ۴٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰ هستند و هیچ‌کدام از این مربع‌ها بر یک عدد مرسن بخش پذیر نیستند.

اعداد مرسن بهمراه سال

اگر دنباله‌ای به این صورت باشد که ${\displaystyle A_{p}=2^{A_{p}}-1}$ و ${\displaystyle A_{0}=2}$ آیا همه این دنباله اول هستند؟ دیکسون کاتالان، در پاسخ این سؤال در سال ۱۸۷۶، به لوکاس اظهار داشت که ۱–۱۲۷^۲ (${\displaystyle A_{4}}$)، به این ترتیب اول است. همان‌طور که مشخص است این اعداد در این دنباله بسیار سریع بزرگ می‌شوند:

C0 = ۲ (اول)

C1 = ۳ (اول)

C2 = ۷ (اول)

C3 = ۱۲۷ (اول)

C4 = ۱۷۰۱۴۱۱۸۳۴۶۰۴۶۹۲۳۱۷۳۱۶۸۷۳۰۳۷۱۵۸۸۴۱۰۵۷۳۷ (اول)

51217599719369681879879723386331576246^10 <C5 (سؤال:آیا این عدد اول است؟)

به نظر می‌آید احتمال این موضوع خیلی کم باشد که A5 (یا چند عدد بزرگ‌تر از این دنباله) اول باشد. بدون شک این مثال دیگری از «قانون قوی عددهای کوچک» Guy، است. دقت کنید که اگر در این دنباله یک عدد مرکب پیدا شود، طبق نظریه اول، تمام اعداد بعدی مرکب خواهند بود.