Öklid'in asal sayı teoremi, sonsuz sayıda asal sayı olduğunu ifade eder. Öklid, bu teoremi Elementler adlı kitabında, olmayana ergi yöntemiyle ispatlamıştır. İspatın bir kısmı şu şekildedir: Sonlu bir asal sayı listesi alınır ve bu asal sayılara p1, p2, ..., pn denir. Bu asal sayıların çarpımının bir fazlası olan P + 1 sayısı tanımlanır. P + 1 sayısı ya asaldır ya da asal değildir. Eğer P + 1 asal ise, listede olmayan yeni bir asal sayı bulunur. Eğer P + 1 asal değilse, en az bir asal sayı (p) bu sayıyı böler. Ancak, p asalı hem P'yi hem de P + 1'i bölerse, aynı zamanda bu iki sayının farkını da bölmek zorundadır. Fark, 1'den büyük hiçbir asal sayının bölemeyeceği 1 sayısıdır. Bu çelişki, p asalının listede olamayacağı ve dolayısıyla yeni bir asal sayının mevcut olduğu anlamına gelir. Bu ispat, her sonlu asal sayı listesinin dışında yeni bir asal sayı bulunabileceğini ve dolayısıyla asal sayıların sonsuz olduğunu gösterir.