欧几里得定理

维基百科,自由的百科全书
跳转至: 导航搜索

欧几里得定理数论中的基本定理,定理指出素数无限的。该定理有许多著名的证明。

欧几里得的证明[编辑]

欧几里得在他的著作《几何原本》(Book IX, Proposition 20)[1]提出了以下的证明。

对任何有限素数的集合{p_1, p_2, ..., p_n}。令P = p_1 ... p_nq = P+1。那么q是素数或者不是,二者必居其一:

1. 如果q是素数,那么至少有一个素因子q不在有限素数集{p_1, p_2, ..., p_n}

2. 如果q不是素数,那么存在一个素数因子p整除q,如果p在我们的有限素数集中,p必然整除P(既然P是素数有限集中所有素数的积);但是,已知p整除P+1(P+1 = q),如果p同时整除Pqp必然整除Pq之差 —— (P + 1) - P = 1。但是没有素数能整除1,即有p整除q就不存在p整除P。因此p不在有限集{p_1, p_2, ..., p_n}中。

这证明了:对于任何一个有限素数集,总存在一个素数不在其中。所以素数一定是无限的。

参阅[编辑]

注释和参考资料[编辑]

  1. ^ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.

外部链接[编辑]