假設 為素數。

那麼根據尤拉定理有：

我們取x=3

然後計算

列表如下：（下表每項都是上一項的平方再求餘，因此是可以手算的）

可見：

因此 是合數

有朋友覺得這個方法還是不夠“方便”啊。。。

其實這個問題上還有個“更快”的的方法。

但這個方法不具有任何通用性。

就是用尤拉改進的試除法。

尤拉證明了任何費馬數 的所有因子必然是 形式。

題目給出的數 其實就是第五個費馬數

因此我們只要一路試除：65、129、193、257……65473就可以了。

一共是大約1000多個數字。

但是這題很幸運，只需要計算10次，就能發現4294967297 / 641 = 6700417。

但是這個方法不具備任何的通用性，哪怕是下一個費馬素數

也需要試除2142次。。。

另外盧卡斯後來改進了高斯的方法，可以再少算一半。

但即使是這樣，要證明 是合數也需要試除1000多次。。。。