回覆列表
  • 1 # 手機使用者98573813512

    假設 為素數。

    那麼根據尤拉定理有:

    我們取x=3

    然後計算

    列表如下:(下表每項都是上一項的平方再求餘,因此是可以手算的)

    可見:

    因此 是合數

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

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

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

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

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

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

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

    一共是大約1000多個數字。

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

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

    也需要試除2142次。。。

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

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

  • 中秋節和大豐收的關聯?
  • 方舟手遊獻祭神器給什麼?