اعداد اول مرسن ( به انگلیسی: Mersenne Primes ) ، اعداد اولی به فرم M n = 2 n − 1 هستند که به افتخار نام کشیش فرانسوی مارین مرسن ( به انگلیسی: Marin Mersenne ) ، به این نام خوانده می شوند. چرا که مرسن در زمینهٔ اول بودن این نوع اعداد اظهار نظری نادرست اما محرک کرده بود. اولین اعداد مرسن اعداد زیر هستند: ۳، ۷، ۳۱، ۱۲۷، ۸۱۹۱، ۱۳۱۰۷۱، ۲۱۴۷۴۸۳۶۴۷ و … که متناظر هستند با … ، ۸۹ ، ۶۱ ، ۳۱ ، ۱۹ ، ۱۷ ، ۱۳ ، ۷ ، ۵ ، ۳ ، ۲ =n[ ۱]
قضیه اول: اگر M n اول باشد، n نیز باید خود اول باشد.
اثبات: فرض کنیم که حکم نادرست است ( برهان خلف ) . یعنی به ازای n مرکبی، 2 n − 1 اول است؛ در این صورت می توان n را به صورت ضرب دو عدد غیر یک n = r s نوشت. پس:
2 n − 1 = 2 r s − 1 = ( 2 r ) s − 1 = ( 2 r − 1 ) ( ⋯ ) پس اگر s زوج باشد، طبق اتحاد مزدوج و اگر فرد باشد طبق اتحاد چاق و لاغر ( لاگرانژ ) به عوامل اول تجزیه می شود و اول نیست؛ پس به تناقض می رسیم و فرض خلف باطل است. پس n باید اول باشد.
بدیهی است که اعداد مرسن در مبنای دو به صورت ( ( 100 ⋯ 0 ) − 1 ) 2 می باشد که برابر ( 11 ⋯ 1 ) 2 است ( p تا یک ) .
تعریف: عدد کامل ( تام ) عددی است که با مجموع مقسوم علیه های خود، به جز خودش، برابر باشد. از معروفترین آن ها ۶=۳+۲+۱ و ۲۸=۱۴+۷+۴+۲+۱ هستند.
قضیه دوم: هر عدد کامل به صورت ( 2 p − 1 ) ( 2 p − 1 ) است که 2 p − 1 اول است.
این ها اعداد به شکل 2 p − 1 مرسن هستند و متعاقباً توان های آن ها ( p ) اول است. پس با یافتن هر عدد کامل، می توان یک عدد مرسن جدید پیدا کرد.
تقسیم آزمایشی اکثراً برای تصدیق مرکب بودن یک عدد مرسن اول پنهان استفاده می شود. این آزمایش فوراً نشان می دهد که M p به ازای p = 11 , 23 , 83 , 131 , 179 , 191 , 239 , 251 مرکب است ( به ترتیب با عوامل اول ۲۳، ۴۷، ۱۶۷، ۲۶۳، ۳۵۹، ۳۸۳، ۴۷۹ و ۵۰۳ ) .
یک آزمایش بسیار قدرتمند اولیه برای شناسایی M p آزمایش لوکاس - لمر است.
ابتدا سه قضیه زیر را مطرح می کنیم:
• اگر n ≡ 3 {\displaystyle n\equiv 3} به پیمانه ۴ و n {\displaystyle n} عدد اول باشد، در این صورت 2 n + 1 | M n {\displaystyle 2n+1|Mn} ، اگر 2 n + 1 {\displaystyle 2n+1} اول باشد.
• همچنین این درست است که عوامل اول 2 p − 1 {\displaystyle 2^{p} - 1} باید شکل 2 k p + 1 {\displaystyle 2kp+1} داشته باشند که k {\displaystyle k} یک عدد مثبت طبیعی است و در عین حال شکل 8 n + 1 {\displaystyle 8n+1} یا 8 n − 1 {\displaystyle 8n - 1} را داشته باشد ( آسپنسکی و هیسلت ۱۹۳۹ ) .
• یک عامل اول p {\displaystyle p} از یک عدد مرسن M p = 2 p − 1 {\displaystyle M_{p}=2^{p} - 1} ( چه اول و چه مرکب ) در صورتی عدد ویفریچ اول است که p 2 | 2 p − 1 {\displaystyle p^{2}|2^{p} - 1} . بنابراین یک عدد مرسن نمی تواند عدد ویفریچ اول باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفقضیه اول: اگر M n اول باشد، n نیز باید خود اول باشد.
اثبات: فرض کنیم که حکم نادرست است ( برهان خلف ) . یعنی به ازای n مرکبی، 2 n − 1 اول است؛ در این صورت می توان n را به صورت ضرب دو عدد غیر یک n = r s نوشت. پس:
2 n − 1 = 2 r s − 1 = ( 2 r ) s − 1 = ( 2 r − 1 ) ( ⋯ ) پس اگر s زوج باشد، طبق اتحاد مزدوج و اگر فرد باشد طبق اتحاد چاق و لاغر ( لاگرانژ ) به عوامل اول تجزیه می شود و اول نیست؛ پس به تناقض می رسیم و فرض خلف باطل است. پس n باید اول باشد.
بدیهی است که اعداد مرسن در مبنای دو به صورت ( ( 100 ⋯ 0 ) − 1 ) 2 می باشد که برابر ( 11 ⋯ 1 ) 2 است ( p تا یک ) .
تعریف: عدد کامل ( تام ) عددی است که با مجموع مقسوم علیه های خود، به جز خودش، برابر باشد. از معروفترین آن ها ۶=۳+۲+۱ و ۲۸=۱۴+۷+۴+۲+۱ هستند.
قضیه دوم: هر عدد کامل به صورت ( 2 p − 1 ) ( 2 p − 1 ) است که 2 p − 1 اول است.
این ها اعداد به شکل 2 p − 1 مرسن هستند و متعاقباً توان های آن ها ( p ) اول است. پس با یافتن هر عدد کامل، می توان یک عدد مرسن جدید پیدا کرد.
تقسیم آزمایشی اکثراً برای تصدیق مرکب بودن یک عدد مرسن اول پنهان استفاده می شود. این آزمایش فوراً نشان می دهد که M p به ازای p = 11 , 23 , 83 , 131 , 179 , 191 , 239 , 251 مرکب است ( به ترتیب با عوامل اول ۲۳، ۴۷، ۱۶۷، ۲۶۳، ۳۵۹، ۳۸۳، ۴۷۹ و ۵۰۳ ) .
یک آزمایش بسیار قدرتمند اولیه برای شناسایی M p آزمایش لوکاس - لمر است.
ابتدا سه قضیه زیر را مطرح می کنیم:
• اگر n ≡ 3 {\displaystyle n\equiv 3} به پیمانه ۴ و n {\displaystyle n} عدد اول باشد، در این صورت 2 n + 1 | M n {\displaystyle 2n+1|Mn} ، اگر 2 n + 1 {\displaystyle 2n+1} اول باشد.
• همچنین این درست است که عوامل اول 2 p − 1 {\displaystyle 2^{p} - 1} باید شکل 2 k p + 1 {\displaystyle 2kp+1} داشته باشند که k {\displaystyle k} یک عدد مثبت طبیعی است و در عین حال شکل 8 n + 1 {\displaystyle 8n+1} یا 8 n − 1 {\displaystyle 8n - 1} را داشته باشد ( آسپنسکی و هیسلت ۱۹۳۹ ) .
• یک عامل اول p {\displaystyle p} از یک عدد مرسن M p = 2 p − 1 {\displaystyle M_{p}=2^{p} - 1} ( چه اول و چه مرکب ) در صورتی عدد ویفریچ اول است که p 2 | 2 p − 1 {\displaystyle p^{2}|2^{p} - 1} . بنابراین یک عدد مرسن نمی تواند عدد ویفریچ اول باشد.
wiki: عدد اول مرسن