Im mittelalterlichen Europa betrachteten die Italiener die 6 als eine Zahl, die zur Göttin der Liebe Venus gehörte, und sahen sie als Symbol für eine glückliche Ehe an. Die 6 wurde auch als vollkommene Zahl bezeichnet. Tatsächlich wurde die vollkommene Zahl bei ihrer Einführung in China auch als „perfekte Zahl“ übersetzt. Eine natürliche Zahl, deren alle Teiler (selbst die 1 nicht mitgezählt) addiert genau der Wert dieser Zahl ergeben, wird vollkommene Zahl genannt. Es ist nicht schwer zu erkennen, dass die 6 drei Teiler hat: 1, 2 und 3, und 1 + 2 + 3 = 6, also ist die 6 eine vollkommene Zahl und das kleinste Mitglied der Familie der vollkommenen Zahlen. Die 28 hat außer sich selbst fünf Teiler: 1, 2, 4, 7 und 14, also ist sie die zweite vollkommene Zahl: 1 + 2 + 4 + 7 + 14 = 28. Alle bisher bekannten vollkommenen Zahlen sind gerade Zahlen, nicht eine davon ist ungerade. Trotzdem konnte bisher nicht bewiesen werden, dass es keine ungeraden vollkommenen Zahlen gibt, und dieses Problem ist bis heute eine ungelöste Schwierigkeit in der Zahlentheorie.
Bereits vor über 500 Jahren beschäftigte sich Pythagoras mit vollkommenen Zahlen. Später erwähnte Euklid in seinem Werk „Die Elemente“ in Kapitel 9 die vollkommenen Zahlen und stellte fest: Wenn 2^n - 1 eine Primzahl ist, dann ist 2^{n-1}(2^n - 1) eine vollkommene Zahl. Im 17. Jahrhundert berechnete der französische Mönch Marin Mersenne viel über 2^n - 1 und machte einige Behauptungen (einige davon waren falsch). Zu Ehren seiner Leistungen nannten spätere Mathematiker Zahlen der Form 2^n - 1 „Mersenne-Zahlen“ und bezeichneten sie mit Mn.
Es lässt sich leicht beweisen, dass, wenn eine Mersenne-Zahl 2^n - 1 eine Primzahl ist, dann muss n eine Primzahl sein. Umgekehrt scheint eine Mersenne-Zahl, wenn n eine Primzahl ist, ebenfalls eine Primzahl zu sein, z. B.: M3 = 7, M5 = 31, M7 = 127. Überraschenderweise trifft diese Regel jedoch nicht mehr zu, wenn die nächste Mersenne-Zahl M11 = 2^11 - 1 = 2047 = 23 × 89 auftaucht! Aufgrund der vielen besonderen Eigenschaften und interessanten Anekdoten der Mersenne-Primzahlen haben sie seit Jahrhunderten viele Mathematiker fasziniert. Bis zum 18. Jahrhundert wurden jedoch nur acht Mersenne-Primzahlen entdeckt, nämlich M2, M3, M5, M7, M13, M17, M19 und M31. Von diesen war die letzte M31, die der Mathematiker Euler unter Blindheit mit Gedächtnisrechnen bewies und damit die größte bekannte Primzahl der damaligen Zeit war. Euler bewies auch den umgekehrten Satz von Euklids Theorem über vollkommene Zahlen, nämlich dass jede gerade vollkommene Zahl die Form 2^{n-1}(2^n - 1) hat, wobei 2^n - 1 eine Primzahl ist. Damit wurden vollkommene Zahlen vollständig zu einem „Nebenprodukt“ der Mersenne-Primzahlen. In den folgenden mehr als 100 Jahren wurden nur vier weitere Mersenne-Primzahlen entdeckt – M61, M89, M107 und M127. Unter anderem führte der Mathematiker Lucas 1876 einen wichtigen Satz ein, um zu bestimmen, ob Mp eine Primzahl ist, den sogenannten Lucas-Theorem, der ein mächtiges Werkzeug für die Suche nach Mersenne-Primzahlen darstellte. In der „Ära der Papier-und-Bleistift-Rechenmaschinen“ war die Suche nach Mersenne-Primzahlen sehr mühsam, und es wurden nur 12 Mersenne-Primzahlen gefunden.
Die Einführung von Computern beschleunigte die Suche nach Mersenne-Primzahlen erheblich. Im Jahr 1952 programmierten die Mathematiker Robinson und andere die von dem amerikanischen Mathematiker Lamm verbesserte Lucas-Methode auf einem SWAC-Computer und fanden fünf neue Mersenne-Primzahlen: M521, M607, M1279, M2203 und M2281. 1963 wurde die 23. Mersenne-Primzahl M11213 mit einem Großrechner gefunden, und die amerikanische Rundfunkanstalt unterbrach ihre reguläre Programmierung, um diese wichtige Nachricht sofort zu senden. Alle Lehrer und Studenten des Mathematik-Departments der University of Illinois fühlten sich sehr stolz, dieses Ergebnis mit der ganzen Welt zu teilen, und stempelten alle Briefe aus dem Department mit „2^11213 - 1 i“.Eine Briefmarke mit der Aufschrift „prime“ (2^11213 - 1 ist eine Primzahl). Besonders erwähnenswert ist, dass zwei junge amerikanische Gymnasiasten, Noel und Nicolas, nach dreijähriger Arbeit an einem Rechenprogramm im Oktober 1978 die 25. Mersenne-Primzahl M21701 auf einem Cyber174-Computer entdeckten. Zu diesem Zeitpunkt berichteten alle großen Nachrichtenagenturen (einschließlich der chinesischen Nachrichtenagentur Xinhua) und wissenschaftlichen Zeitschriften weltweit darüber, und die „New York Times“ widmete dieser Nachricht eine Schlagzeile auf der Titelseite.
Das Aufkommen der neuen Technologie des Grid Computing hat die Suche nach Mersenne-Primzahlen weiter vorangetrieben. Anfang 1996 entwickelte der amerikanische Mathematiker und Programmierer Wolfram ein Programm zur Berechnung von Mersenne-Primzahlen und stellte es auf einer Webseite zur kostenlosen Nutzung durch Mathematiker und Interessierte zur Verfügung. Dies war das weltbekannte Projekt „GIMPS“ (Great Internet Mersenne Prime Search). Das Projekt nutzt Grid Computing, um die Rechenkapazität vieler normaler Computer zu nutzen und so die Leistung eines Supercomputers zu erreichen. Derzeit können fast 150.000 Menschen aus mehr als 150 Ländern und Regionen am internationalen Kooperationsprojekt GIMPS teilnehmen, indem sie ein kostenloses Programm von der GIMPS-Homepage herunterladen. Bislang wurden 14 neue Mersenne-Primzahlen im Rahmen von GIMPS gefunden. Am 23. August 2008 entdeckte der Computerwissenschaftler Smith von der University of California, Los Angeles, die 45. Mersenne-Primzahl M43112609. Am 6. September 2008 fand der Elektronikingenieur Elvino Nikolich die 46. Mersenne-Primzahl M37156667. Am 12. April 2009 fand der Norweger Strindmo die zwischen diesen beiden Zahlen liegende Mersenne-Primzahl M42643801. Am 25. Januar 2013 entdeckte das Forschungsteam um den Mathematikprofessor Curtis Cooper von der University of Central Missouri die bisher größte bekannte Mersenne-Primzahl M57885161, die aus mehr als 17 Millionen Ziffern besteht, womit die Gesamtzahl der bekannten Mersenne-Primzahlen auf 48 anstieg. Außer der ersten enden alle Mersenne-Primzahlen auf 1 oder 7. Interessanterweise enden die meisten der 48 Mersenne-Primzahlen auf 1.
Warum ist die Suche nach Mersenne-Primzahlen so beliebt? Von der griechischen Antike bis zum 17. Jahrhundert schien die Bedeutung der Suche nach Mersenne-Primzahlen nur darin zu bestehen, vollkommene Zahlen zu finden. Aber seit Mersenne seine berühmte Behauptung aufgestellt hatte, insbesondere seit Eulers Beweis für den umgekehrten Satz des Satzes von Euclid über vollkommene gerade Zahlen, waren vollkommene Zahlen nur ein „Nebenprodukt“ der Mersenne-Primzahlen. Die Suche nach Mersenne-Primzahlen ist der effektivste Weg, die größte bekannte Primzahl zu finden. Seit Eulers Beweis, dass M31 die größte bekannte Primzahl war, haben Mersenne-Primzahlen fast alle Meisterschaften im Finden der größten bekannten Primzahl gewonnen. Die Suche nach Mersenne-Primzahlen ist auch ein wirksames Mittel, um die Rechengeschwindigkeit und andere Funktionen von Computern zu testen. So wurde beispielsweise die 34. Mersenne-Primzahl M1257787 im September 1996 von der Firma Cray während des Tests der Geschwindigkeit ihres neuesten Supercomputers gefunden. Die Entdeckung von Mersenne-Primzahlen erfordert nicht nur Hochleistungscomputer, sondern auch Theorie und Methoden zur Primzahlidentifikation und Wertberechnung sowie ausgeklügelte Programmiertechniken. Daher fördert sie auch die Erforschung der „Königin der Mathematik“ – der Zahlentheorie – und trägt zur Entwicklung der Computer Mathematik und Programmiertechniken bei.
Mersenne-Primzahlen haben auch praktische Anwendungen. Heutzutage werden große Primzahlen im Bereich der modernen Kryptographie eingesetzt, deren Prinzip darin besteht, dass es sehr schwierig ist, eine große Zahl in mehrere Primfaktoren zu zerlegen, aber es ist viel einfacher, mehrere Primfaktoren zu multiplizieren. Bei dieser Art der Kryptographie werden große Primzahlen benötigt, und je größer die Primzahl, desto unwahrscheinlicher ist es, dass der Code geknackt wird.