質數

假設 ${\displaystyle p>1}$  係一個整數。如果 ${\displaystyle p}$  只有 ${\displaystyle 1}$  同埋 ${\displaystyle p}$  係佢嘅因數，咁 ${\displaystyle p}$  就係一個質數。唔係嘅話，${\displaystyle p}$  就係一個合成數。${\displaystyle 0}$  同埋 ${\displaystyle 1}$  就質數、合成數兩者都唔係。

 

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

歐幾理得推論（質數版）

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

證明：

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

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

由上可得推理：

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

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

證明：

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

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

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

存在無限質數。

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

假設${\displaystyle N}$ 係一個質數。

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

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

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

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

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

細過或等於n嘅自然數入面大概有${\displaystyle {\frac {n}{ln(n)}}}$  個質數。

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