欧几里得定理 (Euclid's theorem): 无限素数的证明
质数定义为只能被1和它本身整除的正整数，质数有无穷多个的证明如下：
证明：假设质数有有限个，设它们为p1,p2,p3,...,pn，则它们的乘积N=p1p2p3...pn，由于N是一个正整数，则N+1也是一个正整数，而N+1不能被p1,p2,p3,...,pn整除，因此N+1必定是一个质数，这与假设矛盾，因此质数有无穷多个。
素数有无限个的证明被称为欧几里德定理。 欧几里得定理指出，如果你采用任何有限的素数集，那么你总能找到一个不在该集合中的素数。
为了证明这个定理，我们将使用数学上的反证法。 假设有一个有限的素数集，P = {p1, p2, p3, …, pn}。 我们假设这个集合包含所有素数。
现在，让我们考虑数字 N = p1 * p2 * p3 * … * pn + 1。这个数字大于集合 P 中的任何素数，因为它是集合中所有素数加一的乘积 .
现在，我们将证明 N 是质数或合数。 如果 N 是一个合数，那么它一定能被某个素数 q 整除，其中 q 不在集合 P 中。这意味着 q 是一个不在集合 P 中的素数，这与我们假设集合相矛盾 P 包含所有素数>。
因此，N一定是一个素数，也就是说存在一个不在集合P中的素数。这与我们假设集合P包含所有素数的假设相矛盾，从而证明素数有无穷多个数字。
视频教学: 和娃一起学习成长
(Unsupported https://www.youtube.com/embed/y0rpCeA9rcI)
节选自第563天教娃编程.
油管: