推 Zawar379: 先存檔 03/10 03:11
噓 netstat: PTT 寫的下啊，就算一篇不夠寫你也可以分兩篇寫。 03/10 03:12
→ arnold3: 寫不下就沒屁用了 換會寫的來 03/10 03:15
噓 PPmYeah: 去跟中華民國總統講 03/10 03:19
噓 r25886xd: 一頁寫不夠可以寫兩頁啊 一篇寫不完可以寫兩篇啊 03/10 03:32
→ supermicro: 樓上，還沒寫完就會被水桶了 03/11 02:11
我剛剛找到比
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-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), 來自: 27.147.9.58
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1425928211.A.D6E.html