间接证明(反证法)

例子:

证明质数有无穷多个。

证明。假设这个陈述是假的;也就是说，假设有有限个质数。

然后我们可以给质数编号$p_1，p_2，\mathrm{\dots }，p_n$,在那里$p_n$是最大的质数。

考虑数字$问＝p_1\cdot p_2\cdot \mathrm{\dots }\cdot p_n+1$由所有质数相乘然后相加组成$1$。

我们声称$问$是一个素数。它不能被任何素数整除$p_{我}$与$我<n$;这总是会得到余数$1$。如果它能除以一个合数$c$那么它也可以除以某个质因数$c$…但这同样会得到余数$1$。所以唯一的因数是$问$是$1$和本身。

这意味着$问$质数是否大于$p_n$。但是我们假设$p_n$是最大的素数，所以这是个矛盾。

因此，素数有无穷多个。