※ 引述《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都有。