Мерсенн сандары және жай сандар

Кіріспе

(2^n) - 1 түріндегі жай сан. Математикада Мерсен жай саны – екінің дәрежесінен бір кем жай сан. Яғни, ол n бүтін саны үшін (2^n) - 1 түріндегі жай сан. Олар 17-шы ғасырдың басында оларды зерттеген француз минимит монахы Марин Мерсеннің есімімен аталады. Егер n құрама сан болса, онда 2^n - 1 де құрама сан болады. Сондықтан Мерсен жай сандарының эквивалентті анықтамасы – олар кейбір жай p үшін (2^p) - 1 түріндегі жай сандар. Мерсен жай сандарын беретін n көрсеткіштері: 2, 3, 5, 7, 13, 17, 19, 31, ал нәтижесінде алынған Мерсен жай сандары: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647. (2^n) - 1 түріндегі сандар, жай сан болу талабы болмаса, Мерсен сандары деп аталуы мүмкін. Дегенмен, кейде Мерсен сандары n-нің жай сан болуын қосымша талап ретінде қояды. Жаи көрсеткіші n болатын ең кішкентай құрама Мерсен саны – … Мерсен жай сандары ежелгі заманнан бері кемел сандармен тығыз байланысы болғандықтан зерттелді: Эвклид-Эйлер теоремасы, тіпті кемел сандар мен Мерсен жай сандары арасындағы бір-бірге сәйкестікті көрсетеді. Көптеген ең үлкен белгілі жай сандар Мерсен жай сандары болып табылады, себебі Мерсен сандарының жайлығын тексеру оңайырақ. 2023 жылға қарай 51 Мерсен жай саны белгілі. Ең үлкен белгілі жай сан – 2^82,589,933 - 1, ол Мерсен жай саны. 1997 жылдан бері жаңадан табылған Мерсен жай сандарының барлығы Great Internet Mersenne Prime Search (Үлкен Интернет Мерсен жай іздеуі) жобасы арқылы табылды, бұл – үлестірілген есептеу жобасы. 2020 жылдың желтоқсан айында жобаның маңызды кезеңі өтті, онда 100 миллионнан төменгі барлық көрсеткіштер кем дегенде бір рет тексерілді.

Кемел сандар

Мерсенндік алғашқы сандар Mp толық сандармен тығыз байланысты. Б.з.д. 4 ғасырда Евклид 2^p − 1 саны жай сан болса, онда 2^(p − 1)(2^p − 1) толық сан болатынын дәлелдеді. 18 ғасырда Леонард Эйлер керісінше, барлық жұп толық сандар осы түрде келетінін дәлелдеді. Бұл Евклид-Эйлер теоремасы деп аталады. Тақ толық сандар бар ма, жоқ па, әлі белгісіз.

Мерсен алғашқы сандарын іздеу

Мерсен алғашқыларын табу үшін жылдам алгоритмдер бар, ал 2023 жылға қарай ең үлкен алты алғашқы сан Мерсен алғашқылары болып табылады. Мерсеннің алғашқы төрт алғашқы саны , , және ежелгі дәуірде белгілі болған. Бесіншісі, , 1461 жылға дейін жасырын түрде табылды; келесі екеуі (M17 және M19) 1588 жылы Пьетро Катальди тапты. Екі ғасырға жуық уақыт өткеннен кейін 1772 жылы Леонард Эйлер M31-нің жай сан екенін растады. Келесі (тарихи емес, сандық ретпен) 1876 жылы Эдуард Лукас тапқан M127, содан кейін 1883 жылы Иван Михеевич Первушин тапқан M61. Тағы екеуі (M89 және M107) ХХ ғасырдың басында, 1911 және 1914 жылдары Р. Э. Пауэрс тапты. Мерсен сандарының жай сандығын тексеру үшін қазіргі кезде ең тиімді әдіс Лукас-Лемер жай сан сынағы болып табылады. Нақтырақ айтқанда, p > 2 үшін, егер Mp Sp - 2-ге бөлінсе, онда және k > 0 үшін ғана, ол жай сан болып табылады. Қолмен есептеу дәуірінде 257-ге дейінгі барлық көрсеткіштер Лукас-Лемер сынағымен сыналды және олардың құрама екені анықталды. Ерекше еңбек еткен Йель физикасының зейнеткер профессоры Хорас Скаддер Улер 157, 167, 193, 199, 227 және 229 көрсеткіштері бойынша есептер жүргізді. Өкінішке орай, зерттеушілер сынақтан өткізген аралықта Мерсендік алғашқы сандар арасындағы ең үлкен белгілі салыстырмалы алшақтық бар: келесі Мерсендік алғашқы көрсеткіш, 521, бұрынғы рекордтық көрсеткіштен төрт есе үлкен болып шықты. Мерсенн алғашқы сандарын іздеу электронды цифрлық компьютердің пайда болуымен революцияланды. Алан Тьюринг оларды 1949 жылы Манчестер Mark 1 компьютерінде іздеді, бірақ Мерсендік жай санның алғашқы табысты анықталуы, M521, осы тәсілмен 1952 жылы 30 қаңтарда сағат 22:00-де АҚШ Ұлттық стандарттар бюросының Калифорния университетінің Сандық талдау институтындағы Батыс автоматты компьютері (SWAC) арқылы, Д. Х. Лемердің басшылығымен, профессор Р. М. Робинсонның компьютерлік іздеу бағдарламасы арқылы қол жеткізілді. Бұл 38 жыл ішінде анықталған алғашқы Мерсендік жай сан болды; келесісі, M607, компьютер екі сағаттан аз уақыттан кейін тапты. Келесі бірнеше айда тағы үш – M1279, M2203 және M2281 – сол бағдарламамен табылды. M4,423 – 1000-нан астам цифрлы алғашқы табылған жай сан, M44,497 – 10 000-нан астам, ал M6,972,593 – миллионнан астам бірінші. Жалпы, Mn-нің ондық бейнелеуіндегі цифрлар саны n × log102 + 1-ге тең, мұнда ⌊x⌋ еден функциясын білдіреді (немесе баламалы түрде ⌊log10Mn⌋ + 1). 2008 жылдың қыркүйегінде UCLA-дағы математиктер Ұлы Интернет Мерсендік алғашқы іздеу (GIMPS) жобасына қатысып, 13 миллионға жуық цифрлы Мерсендік алғашқы табуы үшін Электрондық шекаралар қорынан 100 000 доллар сыйлықтың бір бөлігін жеңіп алды. 2009 жылдың қазан айында расталған бұл сыйлық кем дегенде 10 миллион цифрлы алғашқы танымал жай сан үшін. Бұл дерек Dell OptiPlex 745 құрылғысынан 2008 жылдың 23 тамызында табылған. Бұл UCLA-да ашылған сегізінші Мерсендік жай сан. 2009 жылдың 12 сәуірінде GIMPS серверінің журналында 47-ші Мерсендік жай сан табылған болуы мүмкін деп хабарланды. Бұл табылған жерлер 2009 жылдың 4 маусымында алғаш рет байқалды және бір аптадан кейін расталды. Басты сан 242,643,801 - 1. Бұл Мерсендік жай санның хронологиялық тұрғыдан анықталуының 47-ші түрі болса да, ол сол кездегі ең үлкеннен кіші, ол 45-ші табылған. 2013 жылдың 25 қаңтарында Орталық Миссури университетінің математигі Кертис Купер GIMPS сервер желісі арқылы жүргізілген іздеу нәтижесінде 48-ші Мерсендік жай санды, 257 885 161 - 1 (саны 17 425 170 цифрдан тұрады) тапты. 2016 жылдың 19 қаңтарында Купер GIMPS сервер желісі арқылы жүргізілген іздеу нәтижесінде 49-шы Мерсендік жай санды, 274,207,281 − 1 (22 338 618 цифрлы сан) табуын жариялады. Бұл Купер мен оның командасы соңғы он жылда тапқан төртінші Мерсендік жай сан. 2016 жылдың 2 қыркүйегінде Ұлы Интернет Мерсендік алғашқы іздеу M37,156,667 төменгі барлық сынақтарды тексеруді аяқтады, осылайша оның 45-ші Мерсендік жай сан болып табылатындығын ресми түрде растады. 2018 жылдың 3 қаңтарында Теннесси штатының Германтаун қаласында тұратын 51 жастағы инженер-электрик Джонатан Пейс GIMPS сервер желісі арқылы жүргізілген іздеу нәтижесінде 50-ші Мерсендік жай санды, 277 232 917 - 1 (саны 23 249 425 цифрдан тұрады) тапқаны туралы хабарланды. Бұл табылған жер сол қаладағы бір шіркеудің кеңсесінде орналасқан компьютер арқылы табылған. 2018 жылдың 21 желтоқсанында Ұлы Интернет Мерсенн алғашқы іздеу (GIMPS) ең үлкен белгілі жай санды, 282,589,933 - 1 тауып, 24,862,048 цифрдан тұратындығы туралы хабарланды. Флорида штатының Окала қаласынан Патрик Ларош ұсынған компьютер 2018 жылдың 7 желтоқсанында табылған. 2020 жылдың соңында GIMPS потенциалды Мерсендік жай сандарды жоққа шығару үшін жаңа әдіс қолдана бастады, ол Роберт Гербицтің 2017 жылғы әзірлемесіне негіделген «Ықтимал жай сан» (PRP) тесті, және 2018 жылы Кшиштоф Петржак әзірлеген сынақтарды тез растаудың қарапайым тәсілі. Төмен қателік деңгейі мен дәлелдеудің қарапайыдығына байланысты, бұл Лукас Лемер тестінен әлеуетті жай сандарды жоққа шығару үшін есептеу уақытын шамамен екі есеге азайтты (екі пайдаланушы енді бір-бірінің нәтижесін растау үшін бірдей сынақты орындауға міндетті болмайды), бірақ PRP тестінен өткен көрсеткіштер олардың жай сандығын растау үшін әлі де бір сынақтан өтуді қажет етеді.

Fast algorithms for finding Mersenne primes are available, and as of 2023, the six largest known prime numbers are Mersenne primes. The first four Mersenne primes , , and were known in antiquity. The fifth, , was discovered anonymously before 1461; the next two (M17 and M19) were found by Pietro Cataldi in 1588. After nearly two centuries, M31 was verified to be prime by Leonhard Euler in 1772. The next (in historical, not numerical order) was M127, found by Édouard Lucas in 1876, then M61 by Ivan Mikheevich Pervushin in 1883. Two more (M89 and M107) were found early in the 20th century, by R. E. Powers in 1911 and 1914, respectively. The most efficient method presently known for testing the primality of Mersenne numbers is the Lucas–Lehmer primality test. Specifically, it can be shown that for prime p > 2, is prime if and only if Mp divides Sp − 2, where and for k > 0. During the era of manual calculation, all the exponents up to and including 257 were tested with the Lucas–Lehmer test and found to be composite. A notable contribution was made by retired Yale physics professor Horace Scudder Uhler, who did the calculations for exponents 157, 167, 193, 199, 227, and 229. Unfortunately for those investigators, the interval they were testing contains the largest known relative gap between Mersenne primes: the next Mersenne prime exponent, 521, would turn out to be more than four times as large as the previous record of 127. The search for Mersenne primes was revolutionized by the introduction of the electronic digital computer. Alan Turing searched for them on the Manchester Mark 1 in 1949, but the first successful identification of a Mersenne prime, M521, by this means was achieved at 10:00 pm on January 30, 1952, using the U. S. National Bureau of Standards Western Automatic Computer (SWAC) at the Institute for Numerical Analysis at the University of California, Los Angeles, under the direction of D. H. Lehmer, with a computer search program written and run by Prof. R. M. Robinson. It was the first Mersenne prime to be identified in thirty eight years; the next one, M607, was found by the computer a little less than two hours later. Three more — M1279, M2203, and M2281 — were found by the same program in the next several months. M4,423 was the first prime discovered with more than 1000 digits, M44,497 was the first with more than 10,000, and M6,972,593 was the first with more than a million. In general, the number of digits in the decimal representation of Mn equals ⌊n × log102⌋ + 1, where ⌊x⌋ denotes the floor function (or equivalently ⌊log10Mn⌋ + 1). In September 2008, mathematicians at UCLA participating in the Great Internet Mersenne Prime Search (GIMPS) won part of a $100,000 prize from the Electronic Frontier Foundation for their discovery of a very nearly 13 million digit Mersenne prime. The prize, finally confirmed in October 2009, is for the first known prime with at least 10 million digits. The prime was found on a Dell OptiPlex 745 on August 23, 2008. This was the eighth Mersenne prime discovered at UCLA. On April 12, 2009, a GIMPS server log reported that a 47th Mersenne prime had possibly been found. The find was first noticed on June 4, 2009, and verified a week later. The prime is 242,643,801 − 1. Although it is chronologically the 47th Mersenne prime to be discovered, it is smaller than the largest known at the time, which was the 45th to be discovered. On January 25, 2013, Curtis Cooper, a mathematician at the University of Central Missouri, discovered a 48th Mersenne prime, 257,885,161 − 1 (a number with 17,425,170 digits), as a result of a search executed by a GIMPS server network. On January 19, 2016, Cooper published his discovery of a 49th Mersenne prime, 274,207,281 − 1 (a number with 22,338,618 digits), as a result of a search executed by a GIMPS server network. This was the fourth Mersenne prime discovered by Cooper and his team in the past ten years. On September 2, 2016, the Great Internet Mersenne Prime Search finished verifying all tests below M37,156,667, thus officially confirming its position as the 45th Mersenne prime. On January 3, 2018, it was announced that Jonathan Pace, a 51 year old electrical engineer living in Germantown, Tennessee, had found a 50th Mersenne prime, 277,232,917 − 1 (a number with 23,249,425 digits), as a result of a search executed by a GIMPS server network. The discovery was made by a computer in the offices of a church in the same town. On December 21, 2018, it was announced that The Great Internet Mersenne Prime Search (GIMPS) discovered the largest known prime number, 282,589,933 − 1, having 24,862,048 digits. A computer volunteered by Patrick Laroche from Ocala, Florida made the find on December 7, 2018. In late 2020, GIMPS began using a new technique to rule out potential Mersenne primes called the Probable prime (PRP) test, based on development from Robert Gerbicz in 2017, and a simple way to verify tests developed by Krzysztof Pietrzak in 2018. Due to the low error rate and ease of proof, this nearly halved the computing time to rule out potential primes over the Lucas Lehmer test (as two users would no longer have to perform the same test to confirm the other's result), although exponents passing the PRP test still require one to confirm their primality.

Мерсен сандары туралы теоремалар

Егер a және p – натурал сандар болса және a^(p) − 1 жай сан болса, онда a = 2 немесе p = 2. Дәлелдеме: a ≡ 1 (mod a − 1) болғандықтан, a^(p) ≡ 1 (mod a − 1), демек a^(p) − 1 ≡ 0 (mod a − 1). Осылайша, a − 1 – a^(p) − 1 санының бөлгіші. Бірақ a^(p) − 1 жай сан болғандықтан, a − 1 = 1 немесе a − 1 = a^(p) − 1. Егер a − 1 = 1 болса, онда a = 2. Егер a − 1 = a^(p) − 1 болса, онда a = a^(p), демек a^(p-1) = 1. Бұл a = 1 дегенді білдіреді, бірақ 1 жай сан емес. Егер 2^(p) − 1 жай сан болса, онда p жай сан. Дәлелдеме: p – жай сан емес деп есептейік, яғни p = ab түрінде жазылуы мүмкін, мұнда a және b > 1. Онда 2^(p) − 1 = 2^(ab) − 1 = (2^a)^b − 1. Бұл сан (2^a − 1) санымен бөлінеді, сондықтан 2^(p) − 1 жай сан емес. Демек, егер 2^(p) − 1 жай сан болса, онда p жай сан. Егер p – тақ жай сан болса, онда 2^(p) − 1-ді бөлетін әрбір жай сан q, 1 + 2p-нің еселігі болуы керек. Бұл 2^(p) − 1 жай сан болған жағдайда да орындалады. Мысалы, 3 – жай сан, ал 7 = 2^3 − 1 де жай сан. Құрама мысал: 31 = 2^5 − 1, мұнда 31 = 1 * 31. Дәлелдеме: Ферманың кіші теоремасы бойынша, q – 2^(q−1) − 1 санының бөлгіші. Q – 2^(p) − 1 санының бөлгіші болғандықтан, барлық оң бүтін сандар үшін c, q сонымен қатар 2^(pc) − 1 санының бөлгіші болып табылады. P – жай сан және q – 2^1 − 1 санының бөлгіші емес болғандықтан, p – q санының бөлгіші болатын ең кіші оң бүтін сан x. Нәтижесінде, барлық оң бүтін x үшін q – 2^(x) − 1 санының бөлгіші, егер және тек p – x санының бөлгіші болса. Сондықтан, q – 2^(q−1) − 1 санының бөлгіші болғандықтан, p – q − 1 санының бөлгіші, демек q ≡ 1 (mod p). Сонымен қатар, q – 2^(p) − 1 санының бөлгіші болғандықтан, ол тақ, демек q – тақ. Сондықтан, q ≡ 1 (mod 2p). Бұл факт Евклид теоремасының дәлеліне әкеледі, ол жай сандардың шексіздігін растайды: әрбір тақ жай p үшін, 2^(p) − 1-ді бөлетін барлық жай сандар p-ден үлкен; сондықтан әрқашан белгілі бір жай сандан үлкен жай сандар болады. Осыдан шығатыны, әрбір p > 2 үшін, кем дегенде бір 2kp+1 түріндегі жай сан Mp-ден кем немесе оған тең, кейбір k бүтін саны үшін бар. Егер p – тақ жай сан болса, онда 2^(p) − 1-ді бөлетін әрбір жай сан q, ±1 (mod 8) сәйкестігін қанағаттандырады. Дәлелдеме: 2^(p+1) ≡ 2 (mod q), демек 2 – 2 mod q түбірі. Квадраттық өзаралық заң бойынша, 2 санының квадрат түбірі бар әрбір жай модуль ±1 (mod 8) сәйкестігін қанағаттандырады. Мерсен жай саны Виферих жай саны бола алмайды. Дәлелдеме: Егер Мерсен жай саны болса, онда 2^(p−1) ≡ 1 (mod p^(2)) сәйкестігі орындалмайды. Ферманың кіші теоремасы бойынша, 2^(p−1) ≡ 1 (mod p). Сондықтан, 2^(p−1) = 1 + kp түрінде жазуға болады, мұнда k – бүтін сан. Егер берілген сәйкестік орындалса, онда kp ≡ 0 (mod p^(2)), демек k ≡ 0 (mod p). Сондықтан k = mp түрінде жазылуы мүмкін, мұнда m – бүтін сан. Осыдан λ ≥ p^(2) деген қорытынды шығады. Бұл p − 1 ≥ m(p^(2) − 1) дегенге әкеледі, бұл m ≥ 2 болғандықтан мүмкін емес. Егер m және n – натурал сандар болса, онда m және n өзара жай сандар болады, егер және тек қана 2^m − 1 және 2^n − 1 өзара жай сандар болса. Нәтижесінде, жай сан ең көп дегенде бір жай көрсеткішті Мерсен санымен бөлінеді. Яғни, зиянды Мерсен сандары жиыны жұптық тең. Егер p және 2p + 1 екеуі де жай сан болса (яғни p – Софи Жермен жай саны), ал p ≡ 3 (mod 4) болса, онда 2p + 1 саны 2^(p) − 1 санының бөлгіші болады. Мысалы: 11 және 23 екеуі де жай сан, және 23 | (2^11 − 1), демек 23 саны 211 − 1 санының бөлгіші. Дәлелдеме: q = 2p + 1 болсын. Ферманың кіші теоремасы бойынша, 2^(2p) ≡ 1 (mod q), демек 2^p ≡ 1 (mod q) немесе 2^p ≡ −1 (mod q). Егер соңғысы дұрыс болса, онда −2 – q модулі бойынша квадраттық қалдық. Алайда, p ≡ 3 (mod 4) болғандықтан, q ≡ 7 (mod 8) және демек 2 – q модулі бойынша квадраттық қалдық. Сонымен қатар, q ≡ 3 (mod 4) болғандықтан, −1 – q модулі бойынша квадраттық қалдық емес, сондықтан −2 – қалдық пен қалдық емес өнімі және демек ол қалдық емес, бұл қарама-қайшылық. Демек, бұрынғы сәйкестік орындалуы керек және 2p + 1 саны Mp-ді бөледі. Жай көрсеткішті Мерсен сандарының барлық құрама бөлгіштері 2-ге негізделген мықты псевдопримдер болып табылады. 1-ден басқа Мерсен саны толық қуат бола алмайды. Яғни, және Михайлеску теоремасына сәйкес, m, n және k – m > 1 және k > 1 бүтін сандар болатын теңдеудің шешімдері жоқ.

If a and p are natural numbers such that a^(p) − 1 is prime, then or Proof: a ≡ 1 ([[Modular arithmetic. Then a^(p) ≡ 1 (mod a − 1), so a^(p) − 1 ≡ 0 (mod a − 1). Thus However, a^(p) − 1 is prime, so or In the former case, , hence (which is a contradiction, as neither −1 nor 0 is prime) or In the latter case, or If , however, which is not prime. Therefore, If 2^(p) − 1 is prime, then p is prime. Proof: Suppose that p is composite, hence can be written with a and b > 1. Then 2^(p) − 1 so 2^(p) − 1 is composite. By contraposition, if 2^(p) − 1 is prime then p is prime. If p is an odd prime, then every prime q that divides 2^(p) − 1 must be 1 plus a multiple of 2p. This holds even when 2^(p) − 1 is prime. For example, is prime, and A composite example is , where and Proof: By Fermat's little theorem, q is a factor of 2^(q−1) − 1. Since q is a factor of 2^(p) − 1, for all positive integers c, q is also a factor of 2^(pc) − 1. Since p is prime and q is not a factor of 21 − 1, p is also the smallest positive integer x such that q is a factor of 2^(x) − 1. As a result, for all positive integers x, q is a factor of 2^(x) − 1 if and only if p is a factor of x. Therefore, since q is a factor of 2^(q−1) − 1, p is a factor of q − 1 so q ≡ 1 (mod p). Furthermore, since q is a factor of 2^(p) − 1, which is odd, q is odd. Therefore, q ≡ 1 (mod 2p). This fact leads to a proof of Euclid's theorem, which asserts the infinitude of primes, distinct from the proof written by Euclid: for every odd prime p, all primes dividing 2^(p) − 1 are larger than p; thus there are always larger primes than any particular prime. It follows from this fact that for every prime p > 2, there is at least one prime of the form 2kp+1 less than or equal to Mp, for some integer k.
If p is an odd prime, then every prime q that divides 2^(p) − 1 is congruent to ±1 (mod 8). Proof: 2^(p+1) ≡ 2 (mod q), so is a square root of 2 mod q. By quadratic reciprocity, every prime modulus in which the number 2 has a square root is congruent to ±1 (mod 8). A Mersenne prime cannot be a Wieferich prime. Proof: We show if is a Mersenne prime, then the congruence 2^(p−1) ≡ 1 (mod p^(2)) does not hold. By Fermat's little theorem, Therefore, one can write If the given congruence is satisfied, then , therefore ≡ −λ mod (2^(m) − 1). Hence , and therefore λ ≥ 2^(m) − 1. This leads to p − 1 ≥ m(2^(m) − 1), which is impossible since m ≥ 2. If m and n are natural numbers then m and n are coprime if and only if 2^(m) − 1 and 2^(n) − 1 are coprime. Consequently, a prime number divides at most one prime exponent Mersenne number. That is, the set of pernicious Mersenne numbers is pairwise coprime. If p and 2p + 1 are both prime (meaning that p is a Sophie Germain prime), and p is congruent to 3 (mod 4), then 2p + 1 divides 2^(p) − 1. Example: 11 and 23 are both prime, and , so 23 divides 211 − 1. Proof: Let q be 2p + 1. By Fermat's little theorem, 2^(2p) ≡ 1 (mod q), so either 2^(p) ≡ 1 (mod q) or 2^(p) ≡ −1 (mod q). Supposing latter true, then , so −2 would be a quadratic residue mod q. However, since p is congruent to 3 (mod 4), q is congruent to 7 (mod 8) and therefore 2 is a quadratic residue mod q. Also since q is congruent to 3 (mod 4), −1 is a quadratic nonresidue mod q, so −2 is the product of a residue and a nonresidue and hence it is a nonresidue, which is a contradiction. Hence, the former congruence must be true and 2p + 1 divides Mp. All composite divisors of prime exponent Mersenne numbers are strong pseudoprimes to the base 2. With the exception of 1, a Mersenne number cannot be a perfect power. That is, and in accordance with Mihăilescu's theorem, the equation has no solutions where m, n, and k are integers with m > 1 and k > 1.

Құрама Мерсен сандарының факторлануы

Мерсенн жай сандары жай сандар болғандықтан, тек 1-ге және өзіне ғана бөлінеді. Дегенмен, барлық Мерсенн сандары Мерсенн жай сандары емес. Мерсенн сандары арнайы сандық өріс ілгіш алгоритмі үшін өте жақсы сынақ жағдайлары болып табылады, сондықтан көбінесе осы алгоритммен факторланған ең үлкен сан – Мерсенн саны болып табылады. 2019 жылдан бастап, бірнеше санды бірден факторлауға мүмкіндік беретін арнайы сандық өріс ілгіш алгоритмінің түрімен факторланған рекорд иегері болып табылады. Қосымша ақпарат алу үшін бүтін сандарды факторлау туралы жазбаларға қараңыз. Арнайы сандық өріс ілгіш алгоритмі бірден көп үлкен көбейткіштері бар сандарды факторлауға мүмкіндік береді. Егер санда тек бір ғана өте үлкен көбейткіші болса, онда басқа алгоритмдер алдымен кіші көбейткіштерді тауып, содан кейін кофактордың жайлығын тексеру арқылы үлкен сандарды факторлай алады. 2022 жылғы мәліметтер бойынша, ең үлкен толық факторланған сан (ықтимал жай көбейткіштерімен) – , мұнда q – 3,829,294 таңбалы ықтимал жай сан. Оны "Funky Waddle" никнеймімен GIMPS қатысушысы тапқан. 2022 жылғы мәліметтер бойынша, M1277 Мерсенн саны – белгілі көбейткіштері жоқ ең кішкентай құрама Мерсенн саны; оның 268-ден төмен жай көбейткіштері жоқ, ал 1065-тен төмен көбейткіштері болуы өте ұтымсыз (~2216). Төмендегі кестеде алғашқы 20 құрама Мерсенн сандарының факторлық бөліністері көрсетілген:
pMpФакторлауыMp11204723 × 8923838860747 × 178,48129536870911233 × 1,103 × 2,08937137438953471223 × 616,318,17741219902325555113,367 × 164,511,353438796093022207431 × 9,719 × 2,099,863471407374883553272,351 × 4,513 × 13,264,5295390071992547409916,361 × 69,431 × 20,394,40159576460752303423487179,951 × 3,203,431,780,337 (13 таңба)67147573952589676412927193,707,721 × 761,838,257,287 (12 таңба)712361183241434822606847228,479 × 48,544,121 × 212,885,833739444732965739290427391439 × 2,298,041 × 9,361,973,132,609 (13 таңба)796044629098073145873530872,687 × 202,029,703 × 1,113,491,139,767 (13 таңба)83967140655691033397649407167 × 57,912,614,113,275,649,087,721 (23 таңба)9715845632502818708790067111,447 × 13,842,607,235,828,485,645,766,393 (26 таңба)1012535301200459934064107517,432,339,208,719 (13 таңба) × 341,117,531,003,194,129 (18 таңба)1031014120480189736256430072,550,183,799 × 3,976,656,429,941,438,590,393 (22 таңба)109649037107316312041152511745,988,807 × 870,035,986,098,720,987,332,873 (24 таңба)1131038459371709926584401913,391 × 23,279 × 65,993 × 1,868,569 × 1,066,818,132,868,207 (16 таңба)131272225893536454145691647263 × 10,350,794,431,055,162,386,718,619,237,468,234,569 (38 таңба)

Since they are prime numbers, Mersenne primes are divisible only by 1 and themselves. However, not all Mersenne numbers are Mersenne primes. Mersenne numbers are very good test cases for the special number field sieve algorithm, so often the largest number factorized with this algorithm has been a Mersenne number. as of 2019, is the record holder, having been factored with a variant of the special number field sieve that allows the factorization of several numbers at once. See integer factorization records for links to more information. The special number field sieve can factorize numbers with more than one large factor. If a number has only one very large factor then other algorithms can factorize larger numbers by first finding small factors and then running a primality test on the cofactor. as of 2022, the largest completely factored number (with probable prime factors allowed) is , where q is a 3,829,294 digit probable prime. It was discovered by a GIMPS participant with nickname "Funky Waddle". as of 2022, the Mersenne number M1277 is the smallest composite Mersenne number with no known factors; it has no prime factors below 268, and is very unlikely to have any factors below 1065 (~2216). The table below shows factorizations for the first 20 composite Mersenne numbers
pMpFactorization of Mp11204723 × 8923838860747 × 178,48129536870911233 × 1,103 × 2,08937137438953471223 × 616,318,17741219902325555113,367 × 164,511,353438796093022207431 × 9,719 × 2,099,863471407374883553272,351 × 4,513 × 13,264,5295390071992547409916,361 × 69,431 × 20,394,40159576460752303423487179,951 × 3,203,431,780,337 (13 digits)67147573952589676412927193,707,721 × 761,838,257,287 (12 digits)712361183241434822606847228,479 × 48,544,121 × 212,885,833739444732965739290427391439 × 2,298,041 × 9,361,973,132,609 (13 digits)796044629098073145873530872,687 × 202,029,703 × 1,113,491,139,767 (13 digits)83967140655691 033397649407167 × 57,912,614,113,275,649,087,721 (23 digits)97158456325028 18708790067111,447 × 13,842,607,235,828,485,645,766,393 (26 digits)101253530120045 9934064107517,432,339,208,719 (13 digits) × 341,117,531,003,194,129 (18 digits)103101412048018 9736256430072,550,183,799 × 3,976,656,429,941,438,590,393 (22 digits)109649037107316 312041152511745,988,807 × 870,035,986,098,720,987,332,873 (24 digits)113103845937170 9926584401913,391 × 23,279 × 65,993 × 1,868,569 × 1,066,818,132,868,207 (16 digits)131272225893536 454145691647263 × 10,350,794,431,055,162,386,718,619,237,468,234,569 (38 digits)

Алғашқы 500 Мерсенн санының көбейткіштерінің санын мына жерде табуға болады.

Табиғаттағы және басқа жерлердегі Мерсен сандары

Математикалық мәселеде Ханой мұнарасы, n дискілі мұнараны шешу үшін Mn қадам қажет, егер қателер жасалмаса. Бидай және шахмат тақтасы мәселесіндегі бүкіл шахмат тақтасындағы күріш дәндерінің саны M64-ке тең. 8191 нөмірі бар астероид, Марин Мерсеннің құрметіне 8191 Мерсен деп аталған, себебі 8191 – Мерсеннің жай саны (3 Юнона, 7 Ирис, 31 Эвфросина және 127 Иоганна 19 ғасырда ашылып, аталған). Геометрияда, примитивті және оның жұп қабырғасы 2-нің дәрежесі (≥ 4) болатын бүтін санды тікбұрышты үшбұрыш, оның ішкі радиусы әрқашан Мерсен саны болатындай бірегей тікбұрышты үшбұрыс жасайды. Мысалы, егер жұп қабырғасы 2^(n + 1) болса, онда ол примитивті болғандықтан, тақ қабырғасы 4^(n) – 1, гипотенузасы 4^(n) + 1, ал ішкі радиусы 2^(n) – 1 болуымен шектеледі.

Мерсенннің Фермат алғашқы сандары

Мерсенн-Фермат саны p жай сан, r – натурал сан ретінде анықталады және MF(p, r) деп жазылуы мүмкін. Егер r = 2 болса, ол Мерсенн саны болады. Егер r = 3 болса, ол Фермат саны болады. r > 1 болғандағы белгілі жалғыз Мерсенн-Фермат жай сандары: MF(2, 2), MF(2, 3), MF(2, 4), MF(2, 5), MF(3, 2), MF(3, 3), MF(7, 2) және MF(59, 2). Шындығында, , мұндағы Φ – циклотомдық полином.

Жалпылау

Ең қарапайым жалпыланған Мерсендік алғашқы сандар f(2^n) түріндегі алғашқы сандар болып табылады, мұнда f(x) – кіші бүтін сан коэффициенттері бар төмен дәрежелі полином. Мысал ретінде 2^64 − 2^32 + 1, бұл жағдайда ; тағы бір мысал ретінде 2^192 − 2^64 − 1, бұл жағдайда ; 2^n − 1 түріндегі алғашқы сандарды b^n − 1 түріндегі алғашқы сандарға жалпылауға тырысу да табиғи. Алайда (жоғарыдағы теоремаларды да қараңыз), b^n − 1 әрқашан b − 1 арқылы бөлінеді, сондықтан соңғысы бірлікке тең болмаса, біріншісі алғашқы сан емес. Бұл b-ді бүтін санның орнына алгебралық бүтін сан болуға рұқсат ету арқылы түзетуге болады:

Күрделі сандар

Бүкіл сандар сақинасында (нақты сандар бойынша), егер b - 1 бірлік болса, онда b 2 немесе 0 болады. Бірақ 2^(n) − 1 – бұл әдеттегі Мерсенн жай сандары, ал 0^(n) − 1 формуласы қызықты ештеңе бермейді (өйткені ол барлық n > 0 үшін әрқашан -1 болады). Сондықтан, нақты сандардың орнына кешенді сандардағы "бүтін сандар" сақинасын қарастыруға болады, мысалы, Гаусс бүтін сандары және Эйзенштейн бүтін сандары.