設

定理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