作者Hatred (●)
看板Gossiping
標題Re: [問卦] 質數到底有什麼用？
時間Tue Mar 10 02:01:29 2015
※ 引述《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-integers
縮網址：
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
→ lolic: 感謝你讓我看到睏 03/10 02:02
→ yu1988: 嗯嗯 03/10 02:02
→ iPhone4sW: 三小XD 03/10 02:02
推 blankhole: 謝謝原PO 晚安zZZZ 03/10 02:05
推 simdavid: ZzZzZz... 03/10 02:07
→ potionx: 多發幾篇可以讓很多人去睡覺！簡稱睡覺文 03/10 02:07
→ xiaoyu: 才想說要不要喝熱牛奶,多謝你這篇晚安文...姑奈! 03/10 02:07
推 interlude99: 我已經睡著五次了還沒看完這篇文 03/10 02:09
推 Fibonaci: 蠻清楚的 不錯 03/10 02:09
推 howard878: 恩恩 說的沒錯 03/10 02:12
推 oaoa0123: 推～醒來再看XD 03/10 02:13
推 ramDisk: 我懂了 03/10 02:13
→ hssz: 跟我想的差不多，不過還沒講到精髓，有空我教你 03/10 02:13
推 xx52002: 要是能寫成有趣的科普文那就好了 XD 03/10 02:14
推 thejackys: 嗯嗯 我也這麼覺得 03/10 02:17
推 edward0811: 質數有這難 03/10 02:17
推 arnold3: 原來2不是質數 長見識了 03/10 02:19
推 krishuang: 有沒有四元數版的？ 03/10 02:26
推 soulbug: Zzzzzzz.... 03/10 02:26
推 allure1: 每個字我都認識 整篇我全部看不懂 03/10 02:28
→ CenaC: 這篇價值581... 03/10 02:29
→ QazBank: 講中文很難嗎? 03/10 02:30
推 krishuang: |r|^2≦ |w|^2 / 2→|r|^2≦ |w|^2 - 1有點跳 03/10 02:35
謝謝，這裡的確是有點跳，因為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
推 enhao: 說中文好嗎 03/10 02:36
※ 編輯: Hatred (140.138.144.134), 03/10/2015 02:41:20
推 waloloo: 用幾何來解釋好想多zzzZzz 03/10 02:42
※ 編輯: Hatred (140.138.144.134), 03/10/2015 02:42:43
推 sadmonkey: 辛苦了用PTT打數學式子... 03/10 02:42
推 krishuang: 感謝補充 03/10 02:45
→ mayjan: 雖然高中就知道不過還是謝謝你 03/10 02:45
→ mayjan: 直覺知道是對的 但要証明就是要落落長 03/10 02:46
推 HwaSIn: 簡單易懂 03/10 02:53
推 bighand: 13579111317192329313741434853596167717379838997 03/10 02:55
推 jpadesky: 你害我精神都來了… 03/10 03:38
→ zeldazefac: 講這麼多 所以質數到底可以在生活上拿來幹嘛 03/10 04:06
→ zeldazefac: 是不是去超市買東西 價格只要是質數都可以半折? 03/10 04:07
推 tsoahans: 長知識推 其實不難懂 03/10 04:08
推 mike54115: 睡醒再看 03/10 04:25
噓 sangi: 能吃嗎？ 03/10 07:22
推 a125567365: 先推 不然別人以為我看不懂 03/10 09:29
推 summerleaves: 快推 不然別人以為我們看不懂 03/10 10:43
推 ymit: 快笑! 不然別人以為我看不懂 03/10 11:51
推 robinyu85: 之前只知道高斯整數但不知道還可以輾轉相除 長知識推 03/11 01:21
推 weRfamily: 謝謝你的分享 讓我認識高斯整數 你說得很好 03/11 02:20
推 Torreschu: 這是好文 03/11 03:40
推 johnny8376: 推～今天剛上到euclidean ring 03/12 21:36