素数が無数に存在することの証明(そすうがむすうにそんざいすることのしょうめい)は、古くは紀元前3世紀頃のユークリッドの『原論』に記され、その後も多くの証明が与えられている。素数が無数に存在することは、しばしばユークリッドの定理(ユークリッドのていり、英: Euclid's theorem)と呼ばれる。 ユークリッド[編集] 『原論』第9巻命題20[1]で、素数が無数に存在することが示されている。その証明は、次の通りである[2]。 a, b, …, k を任意に与えられた素数のリストとする。その最小公倍数 P ≔ a × b × ⋯ × k に 1 を加えた数 P + 1 は、素数であるか、合成数のいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は