初等數(shù)論--整除--判斷一個數(shù)是否是素數(shù)

博主是初學初等數(shù)論（整除+同余+原根），本意是想整理一些較難理解的定理、算法，加深記憶也方便日后查找；如果有錯，歡迎指正。
我整理成一個系列：初等數(shù)論，方便檢索。

$設n是一個正整數(shù)，如果對于所有素數(shù)p\le \sqrt{n},都有p?n,則n一定是素數(shù)。$
$證明：$
$$\begin{gathered} 反證法：假設n是一個合數(shù)，它的最小正因數(shù)為k，則k\mid n, \\ 我們現(xiàn)在只需要證明k是素數(shù)且k\le \sqrt{n},那么我們就找到了一個素數(shù)k不滿足定理的條件。 \end{gathered}$$

• $k是素數(shù)：因為我們已經(jīng)假設了k是最小正因數(shù)，如果k是合數(shù)，那么有q\mid k,又k\mid n,所以q\mid n,那么k就不是最小正因數(shù)了，q成了最小正因數(shù)，與假設矛盾。$
• $$\begin{gathered} k\le \sqrt{n}：我們可以將n表示成n=kd,0<k\le d<n, \\ 因為k乘比自己大的數(shù)等于n，那么k乘自己應該小于等于n， \\ 即k^2\le n\to k\le \sqrt{n} \end{gathered}$$

$綜上，證明結(jié)束$

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的初等数论--整除--判断一个数是否是素数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。