$N = p_1 p_2 \cdots p_n + 1 \ge 3 > 1$ であるから、ユークリッドが第9巻命題20で「$EF$ は素数であるか、そうでないかのいずれかである」と場合分けした通り、$N$ には二つの可能性がある。もし $N$ が素数であれば、$q = N$ 自身が $N$ の素因数である（$N \mid N$ だから）。もし $N$ が合成数であれば、ユークリッドは第7巻命題31「いかなる合成数も、ある素数によって測られる」を適用する。

なぜ第7巻命題31が成り立つのだろうか? ユークリッドは無限降下法によってこれを証明している。$N$ が合成数なら、$1 < d_1 < N$ を満たす約数 $d_1$ を持つ。$d_1$ が素数なら証明は終わる。$d_1$ が合成数なら、さらに真に小さい約数 $1 < d_2 < d_1 < N$ を持ち、以下同様となる。ユークリッドが書いているように、「もし素数が見つからないとすれば、数 $A$ を測る数の無限の減少列が存在することになるが、数においてそのようなことは不可能である」。現代の言葉で同値に言い換えれば、$N$ の最小の約数 $q > 1$ は必ず素数でなければならない（そうでなければ、$q$ のより小さい約数も $N$ を割り切ってしまう）。いずれにせよ、$N$ は少なくとも一つの素因数 $q$ を持つ。