※ 編輯: kamelot (220.129.125.201), 03/09/2015 18:43:58

---

※ 引述《kamelot ()》之銘言：
: 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質數
來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: 有數學家很愛研究質數的八掛嗎？

簡單的說就是 "密碼學"

軍事訊息的加密與解密~!

比如二次大戰德國自始自終不知"engama""謎"被盟軍破解

以至於所有的偷襲都被盟軍抓包而戰敗

現代社會

信用卡 及金融機構的加密與解密


其原理簡單的說，利用"質數無限多"特性 可製造出無限的RSA金鑰
                   ~~~~~~~~~~~~~~~
                   可利用數論證明

質數相乘容易 但 質數相乘的積就難以被分解

利用此特性製造出RSA金鑰!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.204.150.120
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425822706.A.750.html
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
請分解出 843584654988462188654257 的質數

         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
       光驗證97 X 31= 3007  跟57不合  就知道你亂算


       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    真正的RSA金鑰是以下的長度

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489×
  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917

已被破解
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    不用擔心，質數的製造是輕而易舉的，只需要乘法

    但多一倍的BIT就要數百倍的運算與時間了

※ 編輯: ding2599 (123.204.150.120), 03/08/2015 22:25:51

---

超有用der

兩個很大很大的質數相乘  例如Ｐ和Ｑ質數

Ｐ*Ｑ＝Ｎ

但是要由Ｎ要變成Ｐ和Ｑ 超難der

這就是ＲＳＡ的基本架構

Ｎ可以當PUBLIC KEY

Ｐ和Ｑ可以當PRIVATE KEY

我想送出一封信給ＯＢＯＶ 但全世界只能ＯＢＯＶ可以看到

我就拿ＯＢＯＶ的public key加密

即便我把加密過後的文件放在八卦版

但是也只能ＯＢＯＶ可以解開 因為他有private key

ＯＢＯＶ看到我寄給他的信  就身寸惹惹

因為他念ＥＥ 根本不懂ＣＳ  只能繼續摸類比訊號 放大器

只好跳巢到蘋果摸cpu 調調參數 調調cached大小 跑跑benchmark


※ 引述《kamelot ()》之銘言：
: 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質數
來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: 有數學家很愛研究質數的八掛嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.114.240.4
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425823215.A.D63.html

---

※ 引述《kamelot ()》之銘言：
: 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質數
來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: 有數學家很愛研究質數的八掛嗎？

講一個最基本的
兩個齒輪的齒數互質的話可以確保所以齒面都能平均磨損
不會只磨某幾個特定的尺面，可以增加齒輪壽命並減少誤差

所以你看到所有齒輪都有質數的應用
齒輪在日常生活中的應用有多廣，你說質數重不重要

--
Sent from my Android

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.215.47
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425825156.A.CE5.html

---

※ 引述《kamelot ()》之銘言：
: 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質數
來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: 有數學家很愛研究質數的八掛嗎？

強者我朋友是個智商很高的女孩，小時候爸爸過世。
名校畢業後，在波多黎各的電波天文臺工作。
頂頭有個很78又愛搶功勞的老闆，
沒事就愛打她槍，想砍她的研究計畫。

有一天天文臺收到強烈而異常的電波，
還好我朋友知道質數的重要，
終於解開外星人喜歡希特勒的秘密。

之後的故事太長了，這裡就不說了…(茶)

--
Sent from my Android

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.134.243.50
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425825909.A.1E5.html

---

從質數出發

1849年發展出了"孿生質數猜想" (百年數學懸案)

質數就是:  2,3,5,7 ,11  只能被1或自己整除的數


兩個相差2的數對就是"孿生質數"

(3.5)(11.13)  都是"孿生質數"


"孿生質數猜想"就是要證明有無限個"孿生質數"

至今2015年，過了166年，仍無人能破解"孿生質數猜想"


若有人破解，他的大名一定會被放在高階數論中，被大學生公幹

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.204.150.120
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425826044.A.CF3.html
                            已更正
               已更正

            ~~~~~~~~~~~~~~~~~~~~~~~`
        數學是從基本定義 推演 論證   不是用背的   你都讀死書

                ~~~~~~~~~~~~~~~~~~~~~~~~~`
                 打太快嗎  何必抓著一點猛打

※ 編輯: ding2599 (123.204.150.120), 03/08/2015 22:54:25
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~``
        我也是多重積分以前都還是用推導的，之後都跪下來用背的

      已經超越理解範圍 ， 只能死背了
※ 編輯: ding2599 (123.204.150.120), 03/08/2015 23:02:04

---

※ 引述《ding2599 (gfdgdfgd)》之銘言：
: ※ 引述《kamelot ()》之銘言：
: : 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質
數來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: : 有數學家很愛研究質數的八掛嗎？

因為根據算術基本定理，正整數可以被"唯一"地分解成一堆質數

(整數的話則是差正負號而已)

很多時候，我們都偷偷地使用到算術基本定理而沒有察覺

例如計算100的因數的數目，會將其分解成2^2*5^2，再計算3*3=9

回到正題，因為算術基本定理的關係，

我們要研究一個關於正整數命題的時候，"有時候"可以逐步從其質因數擊破，

最後再用這些被擊破的部分(質因數)，回擊原本的整個命題(原正整數)

例如費馬最後定理：

若整數x,y,z,N且N>2 滿足x^N+y^N=z^N　→　xyz=0


若N能整數分解成N=ab，則用指數律左式變成

　　　　　　　　(x^a)^b+(y^a)^b=(z^a)^b

令x^a=X, y^a=Y, z^a=Z，

這邊省略幾個敘述，原命題就等價於

若整數X,Y,Z,b且b>2 滿足X^b+Y^b=Z^b　→　XYZ=0

也就是說，對於費馬問題的正整數N，事實上只需要研究質數p≧3就好(4的另外處理)

反過來說，例如質數3，如果你能證明

　　若整數x,y,z 滿足x^3+y^3=z^3　→　xyz=0

事實上已經證明了

　　若整數x,y,z 滿足x^N+y^N=z^N　→　xyz=0，對於所有Ｎ是３的倍數

如果說一個正整數是小智，那它的質因數是皮卡丘

只要能擊敗皮卡丘，小智就手到擒來

: 簡單的說就是 "密碼學"
: 軍事訊息的加密與解密~!
: 比如二次大戰德國自始自終不知"engama""謎"被盟軍破解
: 以至於所有的偷襲都被盟軍抓包而戰敗
: 現代社會
: 信用卡 及金融機構的加密與解密
: 其原理簡單的說，利用"質數無限多"特性 可製造出無限的RSA金鑰
:                    ~~~~~~~~~~~~~~~
:                    可利用數論證明
: 質數相乘容易 但 質數相乘的積就難以被分解
: 利用此特性製造出RSA金鑰!

據近年英國國安單位解密的情報（還是史諾燈爆料的？？我忘了）

雖然英國國安單位內的人創用"RSA加密演算法" 確實比RSA三個人提出的還要早幾年

(RSA分別取自Ron Rivest，Adi Shamir，Leonard Adleman的字首，

Adleman認為他只是被抓來負責檢驗數學安全性的部分而已，所以說自己要排最後面)

但是RSA簽驗章的演算法 依然是RSA三個人較早創用


在密碼學裡面，不止於RSA，諸多密碼系統也都有對於「質數」的需求

例如說RSA的金鑰由兩個質數PQ構成，

如果今天不小心，P不是質數，RSA演算基本還是能用，

但是暴力搜尋法的複雜度(安全性)至少砍半，少很多，更不用說其他攻擊法

或是橢圓曲線加密的橢圓曲線群的大小，也會要求是質數，

所以說，不管是質數的檢驗，或者是橢圓曲線群的大小，都有一套演算做check

這都能讓我們看見質數的重要

如果想膜拜一下兩質數相乘的金鑰的話，HTTPS開頭的網址，旁邊都會有個鎖的圖案

點進憑證裡面的公開金鑰，沒意外應該都是

另外放到代數學中，也有類似質數的角色，normal gp跟ideal，就撲多說惹

有錯請勿指正，懶得改

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.114.194.148
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425826448.A.3D6.html
最近發不出來很懊惱...
※ 編輯: ma4wanderer (58.114.194.148), 03/08/2015 22:56:18
我是說面對群的處理上

很像正整數之於質數的處理

做qutient之後的qutient gp會給我們一些原本群上的訊息，

只是除的越大 遺失的訊息也越多

如果是solvable或者nilpotent那上面的命題，還能用歸納法處理

其實是省略滿多話

如果x^3k+y^3k=z^3k有非零的正整數解

則x1^3+y1^3=z1^3也有

所以若後者沒有 則前者也沒有　　　　　　這樣吧？

我是指得到訊息的觀點來看
ideal的概念確實是從質數那邊來的沒錯

當初要解決費馬問題 高斯原本做了一個證明 用分解不唯一來達成

結果後來發現不見得每個z[t]都是能唯一分解的

kummer就把不唯一分解的那些想放到一個更大的空間上，提出了ideal number，

讓不唯一分解的那些，再次分解，落入唯一分解的裡面

後來忘了誰，把ideal number的想法萃取成現在的ideal

我看neukirch的書寫的啦 希望沒看錯
※ 編輯: ma4wanderer (58.114.194.148), 03/08/2015 23:27:40

---

緊張的時候可以數，比甚麼寫人吃下去，深呼吸都還有用啊。
不過小心別數錯，要不然就打不贏承太郎了。
打贏就可整個重開機了，你說好不好用啊!!



※ 引述《kamelot ()》之銘言：
: 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質數
來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: 有數學家很愛研究質數的八掛嗎？

--


冷靜下來..數質數一向能讓我冷靜....2.3.5..7-11...ok..全家..萊爾富...

可以不要抄襲嗎 還有改成英文的那個混蛋，這原文是日文啊 白爛
                                                    普奇神父

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.169.51.238
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425828098.A.0DA.html
※ 編輯: chunlin05 (1.169.51.238), 03/08/2015 23:22:12

---

太簡單了

先假設 孿生質數 是有限多個

但是 事實上 孿生質數 是無限多個

所以 假設是錯的

是故 孿生質數 是無限多個

不用謝我了

還有  諾貝爾沒有數學獎  不要替我報名

※ 引述《ding2599 (gfdgdfgd)》之銘言：
: 從質數出發
: 1849年發展出了"孿生質數猜想" (百年數學懸案)
: 質數就是:  2,3,5,7 ,11  只能被1或自己整除的數
: 兩個相差2的數對就是"孿生質數"
: (3.5)(11.13)  都是"孿生質數"
: "孿生質數猜想"就是要證明有無限個"孿生質數"
: 至今2015年，過了166年，仍無人能破解"孿生質數猜想"
: 若有人破解，他的大名一定會被放在高階數論中，被大學生公幹

--
      又過12點了 我又有5個扣打發廢文了 爽
        又過12點了 我又有5個扣打發廢文了 爽
          又過12點了 我又有5個扣打發廢文了 爽
            又過12點了 我又有5個扣打發廢文了 爽
              又過12點了 我又有5個扣打發廢文了 爽

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.239.247
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425829221.A.704.html

---

在密碼學裡面，不止於RSA，諸多密碼系統也都有對於「質數」的需求

例如說RSA的金鑰由兩個質數PQ構成，

如果今天不小心，P不是質數，RSA演算基本還是能用，

但是暴力搜尋法的複雜度(安全性)至少砍半，少很多，更不用說其他攻擊法

或是橢圓曲線加密的橢圓曲線群的大小，也會要求是質數，

--

恩~~在很多密碼系統中，所需要的是 group(群)，這個代數架構。

而剛好((Z/pZ)*,*) 剛好是一個group，所以就拿來在密碼系統用。

而group有什麼好處呢？因為group具有封閉性，你任拿其中兩個元素運算，他還會是

在這個group裡。所以我們不用怕會有什麼奇怪的東西跑出來。

然後要讓這個密碼系統難破的的話，我知道是使用所謂的離散對數的難題。


什麼是離散對數呢？ 任給兩個數a,b 求m a^m=b+Qp，用中文來說就是 a的多少次方除以

p餘數才會是b。 而在這通常p是質數，因為質數不可分的性質才會對任意的a都會有解

(ps.其實在這裡的group是要有特定條件的群，只是我忘了是什麼…不好意思，學藝不精)


也因為在密碼系統中，他們所需要的東西是代數架構這種東西，所以只要符合他們條件的

代數架構都可以拿來用。


在小談一下，費馬小定理的證明，那就是因為((Z/pZ)*,*) 是一個group Q.E.D.

這就是group的力量(被歐)



再來補充一下，橢圓曲線群 over Fp 的個數不一定會是質數是就了。

http://en.wikipedia.org/wiki/Counting_points_on_elliptic_curves

wiki裡有簡單的例子可以看一下。


大概就是這樣，如果有錯請多多指教。

--
「台灣 + 中國 = 經濟肯定會成長。我發現了一個非常漂亮的證明，

但 4 年實在太短，沒有足夠的時間容我來證明它。」

                                                  轉自  <廢馬大定理>-民明書坊

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.199.231
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425830329.A.7F5.html
感謝指正 離散對數的問題
有largrange 是euler theorem嗎？

a^(phi(m))= (1 mod m)


感謝指正，自己在看的時候會知道，不過常常寫出來的時候就會忘記加


我知道這個定理(不過忘了名字，教授別罵我)，

但我不清楚這個定理跟費馬小定理之間的關係就是了
感謝指導。

不知道要看什麼書還是paper，才能知道elliptic curve group over finite field

的個數需要被要求是質數？


恩~~那有相關的資訊嗎？還是有什麼kye word 可以拿來google。謝謝

感謝大大的提供。八掛版果然人才濟濟。
※ 編輯: jayfrog (118.160.199.231), 03/09/2015 00:51:42

---

※ 引述《kamelot ()》之銘言：
: 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質數
來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: 有數學家很愛研究質數的八掛嗎？

本魯是鍵盤質數專家、pavone、溫拿、勝利組、E cup、30cm、高富帥、真強者、

本來本魯要睡了，結果看到本版 #1K_QrfY4 一整個醒了，只好上來貼貼文培養睡意。

高斯整數（Gaussian integer）是指形如整數+整數乘以i的東西，其中i是根號-1，
比方說3+4i、5-8i、-3+5i、2、3、i、1+i、1-i等，都是高斯整數。

高斯整數當中的1、-1、i、-i就好比正整數裡面的1，而高斯整數當中無法被自身和
1、-1、i、-i以外的高斯整數整除者，就好比正整數裡面的質數。

舉例來說，(4+i)(5-i)=21+i，所以21+i就不是高斯整數裡的質數－它可以分解嘛！

反之，2+3i就無法分解出自身和1、-1、i、-i以外的高斯整數，所以它是「質數」。

正整數裡面的質數未必是高斯整數裡面的質數，比方說2是個質數，可是把2當作一個
高斯整數時，我們卻可以將之分解為2=(1+i)(1-i)。

任何一個非零的高斯整數w會有許多「倍數」，只要把w乘以任何高斯整數，能乘出來
的東西就算是w的倍數。

請看這張圖：http://tinyurl.com/oh9a5e7 （取自http://tinyurl.com/mo5q3qc ）

這張圖在解釋的是一個高斯整數的倍數有哪些，圖中黃色點w代表任一非零高斯整數
，而其所有倍數就是圖中標出的那些點：這是因為在複數平面上，iw位於以原點為圓
心，轉動w這點90度後所到達之點，然後w和iw各自延伸整數倍並相加後，能得到的點
就是w的倍數們了。

可見w的倍數們構成一堆斜斜的格子點，每四個格子點構成一個正方形，其邊長為|w|
（看上面的圖會比較清楚），其中|w|表示w到原點的距離。現在把隨意一個正方形的
兩條對角線畫出來，這會將該正方形切成四塊，而落在這個正方形內的任何一個複數
都會與正方形的某一個角落距離不超過 |w|/根號2：這是因為正方形的中心到四個角
落的距離也才|w|/根號2而已（注意正方形對角線長為|w|乘以根號2），何況偏離中
心的點還會更靠近某一個角落。

上面的論述告訴我們：對任何一個高斯整數z，必有某一個正方形的某一個角落與z相
距不超過|w|/根號2，我們可以把這件事寫成

                z = wq + r，

其中高斯整數q使得wq是與z最靠近的正方形角落（回憶一下正方形角落們就恰好是w
的倍數們），而r就直接定義成z-wq。現在由於wq是高斯整數、z也是高斯整數，所以
r也必然要是高斯整數。我們現在就把q當作z除以w的商數、r當作z除以w的餘數，由於
wq與z 相距不超過|w|/根號2，因此

                |r| ≦ |w|/根號2，

故
                   2       2
                |r|  ≦ |w| / 2，

因而
                   2       2
                |r|  ≦ |w|  - 1

這告訴我們的是z除以w後，餘數r比除數w來得「小」，只是這個「小」不是值小，而
是r的絕對值平方比w的少1以上。

這不就是我們熟知的「餘數永遠比除數小」嗎？原來在高斯整數上也能實現此事！

這件事的好處是我們從此以後可以對高斯整數做歐幾里得輾轉相除法。回憶一下在正
整數的世界怎麼找36和15的最大公因數：

                36 = 15 ╳ 2 + 6 （餘數6比除數15小）
                15 = 6 ╳ 2 + 3 （餘數3比除數6小）
                6 = 3 ╳ 2 + 0 （餘數0比除數3小，做完了）

我們從上面的輾轉相除法知道36與15的最大公因數為3，但為什麼輾轉相除法總是會在
有限多步內停下來呢？是因為每次餘數都比上一次小（第一式的6<15，第二式的3<6，
第三式0<3），所以餘數遲早歸零！歸零就做完了！

原來，輾轉相除法最終會停的關鍵，就在於餘數越來越小，而餘數越來越小又是肇因
於每次除法都有「餘數比除數小」的性質。

既然我們在高斯整數上重現了「餘數比除數『小』」這項美好的性質，我們就可以保
證高斯整數的輾轉相除法也會停了！

以下例子取自http://math.stackexchange.com/questions/82350/gcd-of-gaussian-inte
gers
縮網址：http://tinyurl.com/mhmrmfp

把18-i和11+7i拿來輾轉相除：

        18-i = (11+7i)(1-i) + 3i （餘數3i比除數11+7i「小」，因為前者絕對值
                                   平方為9，後者為170，而9<170）

        11+7i = 3i (2-4i) + (-1+i) （餘數-1+i比除數3i「小」，因為前者絕對
                                     值平方為2，後者為9，而2<9）

        3i = (-1+i)(1-i) + i （餘數i比除數-1+i「小」，因為前者絕對值為1，
                               後者為2，而1<2）

        -1+i = i (1+i) + 0 （餘數0比除數i「小」，因為前者絕對值為0，後者為
                             1，而0<1，現在餘數歸零，就做完了）

經過輾轉相除，我們發現18-i和11+7i的最大公因數為i，因為高斯整數的i扮演正整數
中1的腳色，所以知道18-i和11+7i「互質」。

簡言之，能夠讓餘數總是比除數「小」，就可以保證輾轉相除法會停，然後就可以快
樂地找最大公因數了。

以上內容查Euclidean ring都有。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.138.144.134
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425924094.A.97C.html

謝謝，這裡的確是有點跳，因為w不為0，所以

|r|^2 ≦ |w|^2 / 2會導致|r|^2 < |w|^2，然後又因為r和w是高斯整數，所以|r|^2和
|w|^2都是整數，因此|r|^2 < |w|^2會導致|r|^2 ≦ |w|^2 - 1

※ 編輯: Hatred (140.138.144.134), 03/10/2015 02:41:20
※ 編輯: Hatred (140.138.144.134), 03/10/2015 02:42:43

---

我剛剛找到比

2的57885161次方-1

還要大的質數

只是ptt寫不下 我也還沒找到像這樣簡單的表示方式

怎麼辦?

※ 引述《Hatred (●)》之銘言：
: ※ 引述《kamelot ()》之銘言：
: : 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質
數來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: : 有數學家很愛研究質數的八掛嗎？
: 本魯是鍵盤質數專家、pavone、溫拿、勝利組、E cup、30cm、高富帥、真強者、
: 本來本魯要睡了，結果看到本版 #1K_QrfY4 一整個醒了，只好上來貼貼文培養睡意。
: 高斯整數（Gaussian integer）是指形如整數+整數乘以i的東西，其中i是根號-1，
: 比方說3+4i、5-8i、-3+5i、2、3、i、1+i、1-i等，都是高斯整數。
: 高斯整數當中的1、-1、i、-i就好比正整數裡面的1，而高斯整數當中無法被自身和
: 1、-1、i、-i以外的高斯整數整除者，就好比正整數裡面的質數。
: 舉例來說，(4+i)(5-i)=21+i，所以21+i就不是高斯整數裡的質數－它可以分解嘛！
: 反之，2+3i就無法分解出自身和1、-1、i、-i以外的高斯整數，所以它是「質數」。
: 正整數裡面的質數未必是高斯整數裡面的質數，比方說2是個質數，可是把2當作一個
: 高斯整數時，我們卻可以將之分解為2=(1+i)(1-i)。
: 任何一個非零的高斯整數w會有許多「倍數」，只要把w乘以任何高斯整數，能乘出來
: 的東西就算是w的倍數。
: 請看這張圖：http://tinyurl.com/oh9a5e7 （取自http://tinyurl.com/mo5q3qc ）
: 這張圖在解釋的是一個高斯整數的倍數有哪些，圖中黃色點w代表任一非零高斯整數
: ，而其所有倍數就是圖中標出的那些點：這是因為在複數平面上，iw位於以原點為圓
: 心，轉動w這點90度後所到達之點，然後w和iw各自延伸整數倍並相加後，能得到的點
: 就是w的倍數們了。
: 可見w的倍數們構成一堆斜斜的格子點，每四個格子點構成一個正方形，其邊長為|w|
: （看上面的圖會比較清楚），其中|w|表示w到原點的距離。現在把隨意一個正方形的
: 兩條對角線畫出來，這會將該正方形切成四塊，而落在這個正方形內的任何一個複數
: 都會與正方形的某一個角落距離不超過 |w|/根號2：這是因為正方形的中心到四個角
: 落的距離也才|w|/根號2而已（注意正方形對角線長為|w|乘以根號2），何況偏離中
: 心的點還會更靠近某一個角落。
: 上面的論述告訴我們：對任何一個高斯整數z，必有某一個正方形的某一個角落與z相
: 距不超過|w|/根號2，我們可以把這件事寫成
:                 z = wq + r，
: 其中高斯整數q使得wq是與z最靠近的正方形角落（回憶一下正方形角落們就恰好是w
: 的倍數們），而r就直接定義成z-wq。現在由於wq是高斯整數、z也是高斯整數，所以
: r也必然要是高斯整數。我們現在就把q當作z除以w的商數、r當作z除以w的餘數，由於
: wq與z 相距不超過|w|/根號2，因此
:                 |r| ≦ |w|/根號2，
: 故
:                    2       2
:                 |r|  ≦ |w| / 2，
: 因而
:                    2       2
:                 |r|  ≦ |w|  - 1
: 這告訴我們的是z除以w後，餘數r比除數w來得「小」，只是這個「小」不是值小，而
: 是r的絕對值平方比w的少1以上。
: 這不就是我們熟知的「餘數永遠比除數小」嗎？原來在高斯整數上也能實現此事！
: 這件事的好處是我們從此以後可以對高斯整數做歐幾里得輾轉相除法。回憶一下在正
: 整數的世界怎麼找36和15的最大公因數：
:                 36 = 15 ╳ 2 + 6 （餘數6比除數15小）
:                 15 = 6 ╳ 2 + 3 （餘數3比除數6小）
:                 6 = 3 ╳ 2 + 0 （餘數0比除數3小，做完了）
: 我們從上面的輾轉相除法知道36與15的最大公因數為3，但為什麼輾轉相除法總是會在
: 有限多步內停下來呢？是因為每次餘數都比上一次小（第一式的6<15，第二式的3<6，
: 第三式0<3），所以餘數遲早歸零！歸零就做完了！
: 原來，輾轉相除法最終會停的關鍵，就在於餘數越來越小，而餘數越來越小又是肇因
: 於每次除法都有「餘數比除數小」的性質。
: 既然我們在高斯整數上重現了「餘數比除數『小』」這項美好的性質，我們就可以保
: 證高斯整數的輾轉相除法也會停了！
: 以下例子取自http://math.stackexchange.com/questions/82350/gcd-of-gaussian-in
tegers
: 縮網址：http://tinyurl.com/mhmrmfp
: 把18-i和11+7i拿來輾轉相除：
:         18-i = (11+7i)(1-i) + 3i （餘數3i比除數11+7i「小」，因為前者絕對值
:                                    平方為9，後者為170，而9<170）
:         11+7i = 3i (2-4i) + (-1+i) （餘數-1+i比除數3i「小」，因為前者絕對
:                                      值平方為2，後者為9，而2<9）
:         3i = (-1+i)(1-i) + i （餘數i比除數-1+i「小」，因為前者絕對值為1，
:                                後者為2，而1<2）
:         -1+i = i (1+i) + 0 （餘數0比除數i「小」，因為前者絕對值為0，後者為
:                              1，而0<1，現在餘數歸零，就做完了）
: 經過輾轉相除，我們發現18-i和11+7i的最大公因數為i，因為高斯整數的i扮演正整數
: 中1的腳色，所以知道18-i和11+7i「互質」。
: 簡言之，能夠讓餘數總是比除數「小」，就可以保證輾轉相除法會停，然後就可以快
: 樂地找最大公因數了。
: 以上內容查Euclidean ring都有。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.147.9.58
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425928211.A.D6E.html

---

: 舉例來說，(4+i)(5-i)=21+i，所以21+i就不是高斯整數裡的質數－它可以分解嘛！
: 反之，2+3i就無法分解出自身和1、-1、i、-i以外的高斯整數，所以它是「質數」。
: 正整數裡面的質數未必是高斯整數裡面的質數，比方說2是個質數，可是把2當作一個
: 高斯整數時，我們卻可以將之分解為2=(1+i)(1-i)。



這裡說一下所謂的質數跟不可分解在其實是不一樣的事。

所謂的質數是指  if p|ab then p|a or p|b

a|b 的意思就是 a 整除 b

所以用中文來說就是 如果p可以整除兩數相乘的積(ab)，那p要嘛可以整除a

要嘛可以整除b

如果可以做這件事的 p 我們才會稱為質數。

那所謂的不可分解

if a is not an unit and  a=bc then b=u or c=u  u:unit

所謂的unit 如果一個數u 存在另一個數v 使得 uv=1，那我們就說u 是一個unit

所以為什麼上面的例子會是 1 -1 i -i 的原因，因為這四個字是高斯整數裡唯四的unit

簡單來說 就是如果一個數a=bc時，如果b或c一定是unit,那我們就會說a是不可分解的。


上面那個不可分解是不是很像我們小時候學的質數概念呢？

那是因為在整數系裡，質數跟不可分解是等價的


那一個性質比較強呢？

答案是質數：

Suppose p is a prime and  p=ab => p|a or p|b   W.L.O.G.  p|a

then  a=pc so, p=pbc => bc=1, so b,c are units.

(注：W.L.O.G. 這個字在數學證明還蠻常看到的，他的意思是不失一般性。什麼叫

不失一般性呢？以上面的例子說，p要嘛整除a, 要嘛整除b。而且不論選那一個對我們

的證明影響不大，所以我們就可以不失一般性的假設p一定會整除a)


為了避免大家看不懂，簡單來說就是 質數一定不可分解


那會不會有不可分解的數 不是質數呢？

當然會有

我們先考慮 Z(√-5) 在這裡所有的數 都可以會寫成 a+b (√-5)  a,b :Z

可以把這想說是很像復數的寫法，但是i變成(√-5)

而且 a b 都要是會整數。


那在這個數系裡， 3 很明顯就是不可分解的。

但是 3不是質數 因為 3|9 這個沒問題，但是 9=(2+(√-5))(2-(√-5))

而3不會整除其中一個數， 所以從質數的定義上來說， 3在這個數系裡 不會是個質數



希望大家好眠啊

--
「台灣 + 中國 = 經濟肯定會成長。我發現了一個非常漂亮的證明，

但 4 年實在太短，沒有足夠的時間容我來證明它。」

                                                  轉自  <廢馬大定理>-民明書坊

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.199.231
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425928799.A.ACB.html
※ 編輯: jayfrog (118.160.199.231), 03/10/2015 03:22:28
謝謝krishuang大的指教
※ 編輯: jayfrog (118.160.199.231), 03/10/2015 03:43:38

---

※ 引述《kamelot ()》之銘言：
: 以前數學課大家都學過質數，就是只能被1和本身整除的數字，還要背幾個基本的質數
來考試用。理論上來說質數有無限多個，但是到底有什麼用？頂多是為了找出更多質數。
: 有數學家很愛研究質數的八掛嗎？

      小時候數學課我就想打瞌睡,這個問題國中的數學老師教質數的時候就講一堆我完全

聽不懂的話也一點沒有興趣,後來大學學數論,上學期用的是著名數學家Montgomery的經典,

一堆奇奇怪怪的定理就真的非常非常疑惑了,當時問老師也是整天安慰我們學這些跟密碼

有關,這些東西都實在是台灣數學界自爽的藉口,因為在台灣都實在是太難商業化了

加上我們純數學的人根本不碰電腦啊,雖然現代電腦是數學家von Neuman發明的

當時年輕傻傻以為用粉筆就可以證明一切的定理靠數學吃飯,甚至我們以不碰電腦為榮!!!

    大學時代實在搞不懂這些數學家為什麼要研究數論,後來下學期就更慘不忍睹,老師教

Caltech教授Apostol的數論裡面的質數定理,其實這個人的高微教科書比他的數論還有名

裡面用到很多複變函數的Residue積分,當時我們只有學複變的微分而已(慘),然後後來全班

幾乎都在鴨子聽雷,考試寫名字就過了(我沒去寫),數論和複變很多東西都是畢業離開學校

自己自修學會的

     有一次我看到香港中學生恆隆數學的銀牌得主,真的震撼住了,也被嚴重刺激到了

這個香港中學生只是做一件事情,就是把當時Selberg和Paul Erdos(艾狄虛)的證明寫乾淨

談不上什麼創新,但是這個難度也是非常非常高的

On the Prime Number Theorem

https://hlma.math.cuhk.edu.hk/2006winners-c.php

可能99%鄉民都不知道,用初等數學證明質數定理,這是費爾茲獎等級的工作

費爾茲獎跟諾貝爾物理獎最大差別是   費爾茲獎工作太難幾乎沒有什麼數學系的教授會

諾貝爾物理獎很多是大學的時候物理系的學生認真都能輕易學會的東西

       八卦是當時數學頑童Paul Erdos覺得只是好玩不想發表還是太懶還怎樣,

結果Selberg偷偷丟數學期刊,結果Atle Selberg拿了第二屆費爾茲獎

http://en.wikipedia.org/wiki/Atle_Selberg

      後來感觸就很深了,整天巴望著只想拿諾貝爾獎和費爾茲獎的國家,連一個科學教育

都做不好,大學數學教育都做的很差的國家真的是悲劇

          鄉民可能不知道質數跟量子力學統計力學都有很大的關係,不過物理人好像

不太研究這些東西,因為這些都太難做研究了,質數在物理的奧秘這是數學家Montgomery

Selberg和物理學家Freeman Dyson交流的時候發現的

http://www.changhai.org/articles/science/mathematics/riemann_hypothesis/11.php
#s18

      這些東西都不是台灣人能玩的,因為我們就是一個不腳踏實地做學問還有數學教育

也做得很差的國家,整天只會靠北什麼時候會出諾貝爾獎和費爾茲獎得主

想走學術和科學基本條件就是   下輩子記得投胎不要當台灣人











--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.49.104
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425931390.A.E17.html
※ 編輯: Schwinger (1.162.49.104), 03/10/2015 04:10:46

---

質數有一個有趣的例子 就是著名的十七年蟬跟十三年蟬

這種蟬會在土壤裡蹲十七/十三年才出來繁殖一次

17跟13都是質數 並不是巧合

而是為了躲避天敵而演化出極端的例子


質數的生命週期可以避免和天敵有太多時間並存

天敵一旦有穩定的食物就會擴張族群

所以這種蟬每隔十幾年才衝出來一次

數量遠超過天敵可以消化的 吃不完

一部分蟬就可以平安的繁殖 生產

天敵只能久久飽餐一頓 就不會擴張而危害物種的存續


比如說一種天敵生命週期是5年 而蟬有17年跟15年兩種

他們跟天敵的生命週期最小公倍數是85年跟15年

也就是17年蟬每隔85年才會遇到這種天敵一次

而15年蟬每次繁殖都會遇到 相較之下17年就安全許多

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.147.9.58
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1426003992.A.86F.html
※ 編輯: terievv 時間: 2015-03-11 00:20:35