因为 $N = p_1 p_2 \cdots p_n + 1 \ge 3 > 1$,正如欧几里得在第九卷命题20中所区分的那样（“那么 $EF$ 要么是素数,要么不是”）,数 $N$ 有两种情形。如果 $N$ 是素数,那么 $q = N$ 就是 $N$ 的一个素因数（因为 $N \mid N$）。如果 $N$ 是合数,欧几里得便引用第七卷命题31:“任何合数都能被某个素数量尽。”

为什么第七卷命题31成立?欧几里得用无穷递降法给出了证明:如果 $N$ 是合数,它必有一个因数 $d_1$ 满足 $1 < d_1 < N$。若 $d_1$ 是素数,结论已成立;若 $d_1$ 是合数,它又有一个严格更小的因数 $1 < d_2 < d_1 < N$,依此类推。正如欧几里得所写:“如果找不到这样的素数,就会有一串无穷多个数都能度量数 $A$,且后一个比前一个更小,但这在自然数中是不可能的。”用现代语言等价地说,$N$ 的最小因数 $q > 1$ 必定是素数（否则 $q$ 的更小因数也会整除 $N$）。无论哪种情形,$N$ 都至少有一个素因数 $q$。