素数とは自然数（正の整数）であって、自分と1以外には自然数の約数を
持たないものをいう。ただし1は素数からは除外する。
まず2は素数であるから素数は少なくとも1つは存在する。
さて、いま素数が有限個しか存在しないと仮定してみる。
そうしてそれらの有限個の素数のすべての積に1を加えた数を考えると、
それはそれら有限個の素数のどれよりも大きな数になる。すると
それは仮定から素数ではなくて合成数であることが導かれるから、
少なくとも有限個の素数のどれかでは割り切れなければならないが、
実際には作った時の形から、掛け合わせたそれぞれの素数で割った
ときの余りはどれも1になりけっして割り切れないから矛盾が生じる。
この矛盾は素数が有限個しかないと仮定したことによるものである。
よって素数は限りなく存在する。

注：なおこの証明法（ユークリッド原論）は、選ばれた有限個の素数の積に
1を加えたものが、それら選ばれた有限個の素数では割りきれないことだけを
述べているものであり、それが選ばれた以外の新たな素数であることまでは
意味しない（それは選ばれた素数以外の素因数を持っていることだけしか
帰結されない）。

たとえば、新しい素数である場合もあるし、あるいは新しい素数いくつかからなる
合成数である場合のどちらかである。