Depois dos gregos, pouco aconteceu com o estudo dos números primos até o século XVII. Em 1640, Pierre de Fermat afirmou (sem prova) o pequeno teorema de Fermat (mais tarde provado por Leibniz e Euler). Fermat também conjeturou que todos os números da forma 22n + 1 são primos (eles são chamados números de Fermat) e ele verificou isso até n = 4 (ou 216 + 1). No entanto, o próximo número Fermat 232 + 1 é composto (um de seus fatores primos é 641), como Euler descobriu mais tarde, e, de fato, nenhum número Fermat adicional é conhecido por ser primo. O monge francês Marin Mersenne olhou para os primos da forma 2p - 1, com p um primo. Eles são chamados Mersenne primes em sua homenagem.
Até que ponto Fermat confirmou a validade dos números Fermat?
até n = 4 (ou 216 + 1)