---

作者: Hatred (●) 看板: Gossiping
─────────────────────────────────────

※ 引述《kamelot ()》之銘言：
: 有數學家很愛研究質數的八掛嗎？

本魯是鍵盤質數專家、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以外的高斯整數整除者，就好比正整數裡面的質數。



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

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





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

                z = wq + r，



                |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小，做完了）



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

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

以下例子取自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
※ 文章代碼(AID): #1K_T_-by (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425924094.A.97C.html