恰有1和本身两个自然数为其因数的大于1的整数称为素数,记作p.除2为偶素数外,其余素数都是奇数.
素数具有性质:
1°素数有无限多个.如果不超过自然数n的素数个数记作π(n),则当n≥2时,有 \[ \frac{1}{8} \cdot \frac{n}{{\log n}} \le \pi \left( n \right) \le 12 \cdot \frac{n}{{\log n}} \] 进一步有 \[ \mathop {\lim }\limits_{n \to \infty } \frac{{\pi \left( n \right)}}{{\frac{n}{{\log n}}}} = 1 \] 2°设p为素数,若p|ab,则p|a或p|b. 3°n!中含素数p的方次数等于 \[ \left[ {\frac{n}{p}} \right] + \left[ {\frac{n}{{p^2 }}} \right] + \left[ {\frac{n}{{p^3 }}} \right] + \cdots \] 4°若n≤N为正整数,它不能被不超过√N的所有素数所整除,则n必为素数.这种判别自然数是否为素数的方法称为爱拉托斯散筛法.由此法可建立素数表.
大于1的自然数都可唯一地分解为素数幂的积.设n>1为自然数,则n可唯一地表为\[ n = p_1 ^{a_1 } p_2 ^{a_2 } \cdots p_s ^{a_s } \] \[ a_1 > 0,a_2 > 0, \cdots a_s > 0\left(为自然数\right) \] \[ p_1 < p_2 < \cdots p_s \left( 为素数 \right) \] 这称为n的标准分解式.n所含不同素因数的个数s不超过\[ \frac{{\log n}}{{\log 2}} \] 显然,任意自然数n可表为\( n = 2^k \left( {2m + 1} \right)\left( {k,m为自然数或零} \right) \)
整数 \[ M_p = 2^p - 1\left( p为素数 \right) \] 为素数者称为麦森数.至今仅发现27个,即 \[ p = 2,3,5,7,13,17,19,31,61,89,107,127,\] \[ 521,607, 1279,2203,2281,3217,4253,4423,9689,\] \[ 9941, 11213,19939,21701,23209,44497 \] 是否有无穷个麦森数还未证明.
整数\[ F_n = 2^{2^n } + 1\left( n为自然数 \right) \] 称为费马数.至今只发现5个费马数为素数,即 \[ F_0 = 3,F_1 = 5,F_2 = 17,F_4 = 65537 \]