4．素数
一个大于1的正整数p，它除了1和它本身外没有其它因子，就称其为素数。每个整数都可表示为素数的乘积，任何一个大于2的素数加1一定是偶数。一个正整数不是素数，就称为合数。pcZ，有无穷多个。关于素数有无穷个的证明(它是由欧几里得给出的)至今仍然是数学推理的一个典范，是用反证法来证明的。假若只有有限个素数p1、p2、⋯、pn，那么其他任何一个正整数都是合数，于是至少存在一个pi(i＝1、2、⋯、n)能整除它。现在我们构造一个正整数A，使得A＝(p1·p2⋯pn)＋1，这个数是一定存在的，显然A＞Pi，且A/Pi＝p1·p2·⋯pi－1·Pi＋1·⋯pn＋1/pi，即A不能被｛pi，i＝1，2，⋯，n｝中的任何一个整除，因此与假设产生矛盾。
对于素数的无穷性，人们一直想找出一个产生素数的简单算术公式，即使它只能给出部分素数也可以。像费马猜测：形如F(n)＝2𠆢2𠆢n＋1的数是素数，实际上对于n＝1、2、3、4我们有：F(1)＝2𠆢2＋1＝5；F(2)＝2𠆢4＋1＝17；F(3)＝2𠆢8＋1＝257；F(4)＝2𠆢16＋1＝65537全是素数，但在1732年欧拉发现F(5)＝641x6700417是合数，后来又发现了不少＂费马数＂是合数。
另外形如f(n)＝n𠆢2－n＋41，n＝1、2、⋯、40，f(n)是素数，但n＝41时，f(n)＝41𠆢2是合数；又如f(n)＝n𠆢2－79n＋1601，当n从1到79时，都得出素数，但n＝80时就不是素数了。看来求一个仅产生素数的简单表达式的努力一直是徒劳无切的，但是数学家通过研究素数的分布规律找岀了素数定理，即，素数分布的平均状态能用对数函数来描述，An/n～1/lnn，当n趋于无穷大时，其中An表示素数个数，n是自然数。
两个尚未解决的素数问题
i) (哥徳巴赫猜想)任何一个大于2的偶数都能表示为两个素数的合，即2n＝p1＋p2(n＝2，3，4，⋯)如，4＝2＋2，6＝3＋3，8＝5＋3，10＝5＋5，48＝29＋19，100＝97＋3等
ii)素数是经常以p和p＋2的形式成对出现的，如3和5，11和13，29和31等，这种素数对是无穷的。
