質數

質數（粵拼：zat1 sou3），又叫素數（sou3 sou3），係個大過 1 嘅自然數，除咗自己同 1 之外，無其他數可以將佢整除。英文入面叫質數做prime number或者prime。

大過1又唔係質數嘅自然數就叫合成數，合成數都係由大過1嘅自然數相乘而來。例如 5 就係質數，因為要將 5 寫做乘積嘅話，就一定係$1\times 5$ 或者係 $5\times 1$，點都要用返 5 自己。4 就係一個合成數，因為可以將 4 寫做$4=2\times 2$，用兩個細啲嘅數相乘而得到 4。

喺數論入面，質數好重要，因為算術基本定理指出，大過 1 嘅自然數，一係佢已經係質數，一係佢可以寫做一柞質數乘埋，而且呢個寫法唔計次序嘅話係唯一嘅。

質數有無限個，公元前300年左右，歐幾理德（Euclid）證明過呢點。頭三十個質數係2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97、101、103、107、109同埋113。（OEIS數列A000040）

定義

假設 $p>1$ 係一個整數。如果 $p$ 只有 $1$ 同埋 $p$ 係佢嘅因數（factor），咁 $p$ 就係一個質數。唔係嘅話，$p$ 就係一個合成數（composite number）。$0$ 同埋 $1$ 就質數、合成數兩者都唔係。

搵法

愛氏篩搵120以內質數嘅演算法

搵質數最簡單係用愛氏篩（Sieve of Eratosthenes），即係先將第一個質數（即係2）嘅倍數篩走，跟住將下一個質數（即係3）嘅倍數篩走，如此類推。

歐幾理得推論

歐幾理得推論（質數版）

如果$p$係一個質數同埋$p|ab$，咁就一係$p|a$或者$p|b$。

證明：

假設$p$唔可以被$b$整除，即係$p\not |b$。

因為$gcd(b,p)=1$，利用相對質數性質，得出$p|a$。

由上可得推理：

如果$p$係一個質數同埋$p|a_{1}a_{2}\cdots a_{n}$，咁樣$p|a_{k}$，$k$係一個自然數符合$1\leq k\leq n$。

呢個推理指嘅係，如果質數$p$除得盡一個合成數，呢個合成數由$n$個數字乘出嚟，佢嘅因數就叫做$a_{1}a_{2}\cdots a_{n}$，咁樣$p$一定除得盡其中一個因數。

證明：

利用歐幾理得推論，$p|a_{1}$或者$p|a_{2}\cdots a_{n}$。

再利用多一次，得出$p|a_{2}$或者$p|a_{3}a_{4}\cdots a_{n}$。

如此類推，$p|a_{1}$或者$p|a_{2}$或者$\cdots$或者$p|a_{n}$，結果就係一定除得盡其中一個。

歐幾理得證明

存在無限質數。

證明： 假設得$n$咁多個質數，叫$p_{1},p_{2},\cdots ,p_{n}$，而家考慮一個整數$N=p_{1}p_{2}\cdots p_{n}+1$。

假設$N$係一個質數。

因為佢係上面講嘅樣，所以唔止得$n$咁多個質數，令到同第一句有矛盾，所以$N$唔可以係質數。

根據質數分解，$N$一定可以被一啲（即係上面n咁多個其中）質數除得盡，但係根據餘數定理，$N$係唔可能俾上面n個質素除得盡，

即係 ${p_{1}p_{2}\cdots p_{n}+1 \over p_{k}}\ ,\ (k=1,2,3,...,n)$ 一定有 ${1 \over p_{k}}<1$ 唔可以被整除，

所以$N$係一個質數。因為咁令到同第一句有矛盾。

以上兩個情況都出現咗矛盾，即係話假設出錯，質數一定係有無限咁多個。

睇埋

• 商餘
• 質數分解
• 質數定理
• 相對質數