質數及其相關研究.pptVIP

質數及其相關研究 台大數學系 黃上恩 2009.07.07 PART I: 質數 質數的個數 質數的分佈 質數…到底是？ 『不可分解的數』 質因數分解！ 所有大於1的正整數都可以被分解成許多質數的乘積。 1 不是質數！ 質因數分解的方法是唯一的 前幾個質數？ 　test 下一個是多少？ 第100個質數是多少？ 第10000個質數是多少？ 第1 0000 0000 0000 0000 0000個呢？ 個、十、百、千、萬、億、兆、京、？ 質數有無窮多個！ 歐幾里得 Euclid (BC 330 – BC 275) 質數有無窮多個！ 假設質數沒有無窮多個… 因為是有限多個， 所以可以把它們全部寫出來… 所有正整數都是這些質數的乘積！ 質數有無窮多個！ 現在我們考慮它們的乘積加上1 你發現了什麼？ 不被任何剛才列出的所有質數整除！ 質數有無窮多個！ 矛盾在哪？ 質數有無窮多個！ 假設質數沒有無窮多個… 矛盾導因於錯誤的假設。 因此質數有無窮多個，證畢。 質數成長曲線 定義不超過 的質數個數為 質數數量估計 高斯Gauss (1777 – 1855) Legendre (1752 – 1833) 質數定理(1896) 在 很大的時候： 在這裡指的是自然對數函數。 曲線比對 質數定理 柴比雪夫 Chebyshev (1821 – 1894) 質數定理 黎曼 Riemann (1826 – 1866) 質數定理 Jacques Salomon Hadamard(1865 – 1963) Charles Jean de la Vallée-Poussin(1866 – 1962) 質數定理 Paul Erd?s (1913 – 1996) Atle Selberg (1917 – 2007) PART II: 一些特別的質數 費波那契數 費馬數 梅森數 Fibonacci Number 費波那契數 費波那契數 費波那契數 費波那契數 費波那契數 歸納結果！ 如果正整數 整除正整數 ，那麼 整除 。 它是對的！ 但…為什麼它是對的？ 同餘符號 兩個整數 除以 的餘數相同： 例如： 同餘符號的性質 Ex: 兩邊可以一起作加法。 Ex: 兩邊可以一起同乘一個整數。 來證明吧！ 數學歸納法！ 先固定一個正整數 ，證明： 換句話說， 除以 的餘數為 0 一些觀察 一些觀察 一些觀察 有沒有發現什麼？ 一些觀察 找出關鍵性的規律！ 快要得到它了！ 依此類推，可得以下結論： 如果我們令 會發生什麼事情？ 沒錯！ 因此 ！ 那麼，下一步呢？ 試著把 代入別的值吧！(數學歸納法！) 只差一步了！ 當 的時候， 假設 的時候， 那麼當 的時候， 由數學歸納法，得證。 現在已經證明了 不是質數 若 ，則 對於所有的 ，若 是合數，則 結論(費氏質數) 如果一個質數出現在費氏數列的第 項那麼 或質數。 Fermat Number Fermat Number 費馬猜想 所有的費馬數都是質數。 歐拉 Leonhard Euler(1707 – 1783) 不是質數！ 到目前為止… 我們知道 都是合數！ 被完全質因數分解的只有 ！ 沒有人能證明還有沒有其他的費馬質數！ 沒有人能證明費馬合數是否有無窮多個！ 退而求其次 如果 是質數的話… 如果 不是質數的話… 它就可以被因數分解！ 還記得這個嗎？ 當指數部分是奇數的時候，可以被分解！ 例如： 奇數因子 任何正整數 都可以表示成 2 的次方乘以一個奇數。即： 如果 的話， 不是質數！ 所以… 若 是質數，那麼必有 它就會是一個費馬質數！ 關於費馬質數… 高斯在西元 1796 年證明了正十七邊形可以被尺規作圖畫出。 事實上，可以被尺規作圖的正奇多邊形若且唯若其邊數的質因數僅包含