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 のいずれでも割り切れないので、素数でなければならない。し