回覆列表
  • 1 # 使用者9970159714169

    定理1:

    證:由 得到 另外 從而 ,證畢。

    定理2: 是合數

    證: 且易證 是整數且不為 ,從而 整除 ,即 是 的因子。從而 不是素數,證畢。

    本來 定義的式子,即使說它是設出來的,但也會很奇怪它為什麼要這麼設。不少人可以看出來,確實 就是641。如果我們知道了 以及 ,其實湊都能湊出來了。只不過我們是透過因式分解驗證而不是除法驗證而已。另外,只是證明是否是合數倒可以考慮同餘,但是要完全找到這些因子是十分困難的。

    另外 是有定理基礎的,對於 來說,這個定理的數字很恰當:

    引理:若 是費馬數 的素因子,則 形如 。

    ,即 的素因子是一個 。

    此外

    因此,普通地判斷大概需要判斷將近512(實際上是511)個數,不過另外的同時也要判斷 是否為素數,總的判斷量其實在可觀範圍內是少的,不過這隻限於 。

    可以看見,實際上判斷第一個是 ,下一個就是熟悉641了,但它剛好就撞到了,它正是 的素因子。

    不過有些比較有趣的地方:

    另外設 成立。

    可見要想整個式子能夠提取出 ,則 ,即 為偶數。那麼到底什麼的 , 與 能夠使得 這些都成立?

    關於不知道 =641 的前提下:

    此前我想透過哪種花式方法來確切地求出641,比如連分數因式法。但是這個不行,如果你嘗試使用它會出現這樣的情況:

    這意味著

    且得到

    整個 的簡單連分數大概長這個樣子:

    特別地,要利用連分數因式分解需要考慮 的 序列,

    但可發現, ,從而根據 ,並取 為1:

    這個和沒求一個樣,以上說明連分數因式法行不通。事實上連分數是幹不了滿足 的N的。關於連分數因式的修正與改進,我待查詢相關文獻,如果未來不小心看到了的話會補上。

    另外可以透過偽素數的素性檢驗來判斷 是否是素數(如最簡單的費馬小定理或者擴充套件的米勒拉賓)。這個其他答主已經回答了,不過注意需要確切知道 不是Carmichael數。畢竟偽素數素性檢驗演算法並不具備逆命題,且就體現在Carmichael數上。雖然不記前提下可以首先把那些Carmichael數全部找出。

    我另外給出一個比較騷的解法,也許還是需要計算機的。

    波拉德ρ演算法(被算作一個蒙特卡羅演算法):

    在 中隨機選擇一個數 ,不妨取450。記 ,並遞迴定義 即 。

    得到

    則若 ,則 是 的一個因數。

    注: 是指 與 最大公因數。

    ,另外如果你的 選得夠好的話,這個所需步驟會有所變化,總之是步驟有限(有上界)但效率隨機的演算法。對了,這個期望效率是比偽素數的素性檢驗演算法(相比之米勒拉賓素檢法)慢的,甚至是遠比之慢。這個屬於把具有的可能的因數找出的演算法。

    另外傳統上流行這麼一種完整的素數判定(準確說是因數分解)過程:

    小素數範圍(比如10000以內),直接查表判斷。較大數(比如>10000,但長度小於15的),透過波拉德ρ演算法分解。更大的數(比如長度有幾十位甚至幾百位的),透過二次篩法,橢圓曲線或數域篩法。

    參考文獻:

    [1]《Elementary Number Theory and Its Applications》(6th)--Kenneth H.Rosen

  • 中秋節和大豐收的關聯?
  • LOL網友自制世界四大AD選手英雄池圖火了,LWX再被質疑,Uzi的很真實,你有何看法?