素?cái)?shù)就是大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。素?cái)?shù)又稱質(zhì)數(shù)，有無限個(gè)。該數(shù)除了1和它本身以外不再有其他的因數(shù)；否則稱為合數(shù)。整數(shù)1只能被它本身整除，所以不是素?cái)?shù)。素?cái)?shù)除了能表示為它自己和1的乘積以外，不能表示為任何其它兩個(gè)整數(shù)的乘積。

如果為合數(shù)，因?yàn)槿魏我粋€(gè)合數(shù)都可以分解為幾個(gè)素?cái)?shù)的積；而N和N+1的最大公約數(shù)是1，所以該合數(shù)分解得到的素因數(shù)肯定不在假設(shè)的素?cái)?shù)集合中。因此無論該數(shù)是素?cái)?shù)還是合數(shù)，都意味著在假設(shè)的有限個(gè)素?cái)?shù)之外還存在著其他素?cái)?shù)。所以原先的假設(shè)不成立。也就是說，素?cái)?shù)有無窮多個(gè)。

盡管整個(gè)素?cái)?shù)是無窮的，仍然有人會(huì)問“100，000以下有多少個(gè)素?cái)?shù)？”，“一個(gè)隨機(jī)的100位數(shù)多大可能是素?cái)?shù)？”。素?cái)?shù)定理可以回答此問題。

一個(gè)偶數(shù)可以寫成兩個(gè)合數(shù)之和，其中每一個(gè)合數(shù)都最多只有9個(gè)質(zhì)因數(shù)。一個(gè)偶數(shù)必定可以寫成一個(gè)質(zhì)數(shù)加上一個(gè)合成數(shù)，其中合數(shù)的因子個(gè)數(shù)有上界。一個(gè)偶數(shù)必定可以寫成一個(gè)質(zhì)數(shù)加上一個(gè)最多由5個(gè)因子所組成的合成數(shù)。