Die erste wirklich bedeutende Entdeckung seit Eratosthenes gelang Fermat zu Beginn des 17. Jahrhunderts. Er bewies die Theorie von Albert Giardi, dass jede Primzahl der Form 4n+1 als Summe von zwei Quadraten geschrieben werden kann und war auch in der Lage zu zeigen wie jede Zahl als Summe von vier Quadraten geschrieben werden kann. Auch eine neue Art des Faktorisieren von großen Zahlen geht auf Fermat zurück. Seine berühmteste Entdeckung war aber die, die heute Fermat´s kleiner Satz genannt wird. Darin beweist er, dass wenn p eine Primzahl ist für jede Ganzzahl a gilt a^p=a mod p. Damit hatte er die Hälfte der schon 2000 Jahre alten chinesischen Hypothese bewiesen, nach der n nur dann eine Primzahl ist, wenn 2^n-2 durch n teilbar ist. Fermat´s Satz ist die Basis für viele andere Erkenntnisse in der Zahlentheorie und für die meisten der von modernen Computern genutzten Verfahren zum Prüfen von Primzahlen. Fermat hatte auch Kontakt zu anderen Mathematikern seiner Zeit, so auch zu Mersenne. Der schweizer Mönch widmete sich intensiv der Erforschung von Zahlen der Form 2^n-1, die Primzahlen sind. Dabei fand er heraus, dass Zahlen dieser Form nur dann Primzahlen sind, wenn n eine Primzahl ist. Allerdings gilt das nicht für alle Primzahlen. Daher heißen auch Primzahlen n für die 2^n-1 eine Primzahl ist, Mersennesche Primzahl, geschrieben M_n .Sämtliche Primzahlrekorde der heutigen Zeit sind dieser Form, da es sich leicht überprüfen lässt, ob sie Primzahlen sind. Eine Methode, eine Zahl darauf zu Prüfen, entwickelten und bewiesen die beiden Mathematiker Lucas und Lehmer zusammen, daher wird dieses Verfahren auch Lucas-Lehmer-Test genannt.