素数が無数に存在することの証明
『原論』第9巻命題20で、素数が無数に存在することが示されている。その証明は、次の通りである。
a, b, ..., k を任意に与えられた素数のリストとする。その最小公倍数 P ≔ a × b × ⋯ × k に 1 を加えた数 P + 1 は、素数であるか、合成数のいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能だからである。任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。
この証明は、しばしば次のような背理法の形で表現される。
素数の個数が有限と仮定し、p1, ... pn が素数の全てとする。その積 P = p1 × ⋯ × pn に 1 を加えた数 P + 1 は、p1, ..., pn のいずれでも割り切れないので、素数でなければならない。