这一节,从中国剩余定理讲起。
《孙子算经》之“物不知数”是这样说的:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
元代秦九韶的解答则是:三人同行七十稀,五树梅花廿一支,七子团圆正半月,除百零五便得知。
这歌诀隐含一种算法。 本文就以此为引子陈述一种新的“数”——有限域的元素。
固定一个正整数 6. 通过对它做除法,可以把所有整数分成 6 类:
被6 整除的数 {...-12,-6,0,6,12,18,...}、 除6余1的数 {...,-11,-5,1,7,13,19,...}、除6余2的数{...,-10,-4,2,8,14,20,...}、...、 除6余5的数{...,-13,-7,-1,5,11,17,...}。
倘若将这6个类分别记为 [0],[1],[2],[3],[4],[5], 称为 “模6的同余类”。 这些类之间可以进行运算:比如,从 [4] 里取一个数 10,再从 [5] 里取一个数 17,把它们相加,10+17=27,它落在类 [3] 里,这样,我们定义 [4]+[5]=[3]。如果在 [4],[5] 两个类 里取另外的代表,比如取 [4]里的-2, [5]里的 11, 相加得 -2+11=9, 还是落在 [3] 里。很容易证明,无论怎么选这两个代表,加起来都落在 [3] 里。所以我们现在定义的 [4]+[5]=[3] 这种运算是合理的。
同样的实验表明,减法和乘法也可以类似地定义:比如,[1]-[2]=[5], [2]× [3]=[0]. 这说明模6的同余类之间是可以做运算的!
不止如此,这些运算还具有跟普通运算相似的性质:
比如,[0]+[3]=[3], [0]+[4]=[4],零的同余类在加法中没有效果;
[0]× [1]=[0], [0]× [3]=[0],零的同余类乘上别的同余类都得 [0];
[1]×[2]=[2]; [1]×[3]=[3], 表明 1 的同余类在乘法中没有效果(换句话说,[1]是乘法的单位元)。
有了乘法单位元,就可以试图定义“倒数”(严格地说,“倒类”):
比如,[5] ×[5]=[1], 就定义 [5]-1=[5].
可惜,不是 每个同余类都有 “倒数”,[2] 就没有倒数,这是因为 [2]×[0]=[0], [2]×[1]=[2], [2]×[3]=[0], [2] × [4]=[2], [2]×[5]=[4], 都不等于 [1].
哪些同余类有倒数呢?答案是:那些与模数互素的同余类有倒数。比如,模数为6的时候,[1] 和 [5] 有倒数,因为它们与 6 互素。 (互素的意思是,最大公约数为 1。在这种情况下可以应用欧几里得的《几何原本》中记载的 “辗转相除法” 来求同余类的倒数。)
显然,同余类的性质跟模数有关。前面举的例子都是以6为模数,即考虑除6的同余类。严格的记号必须将这个关联反映出来。 我们应该记上述例子中的同余类为 [4]6, 括号中是余数,下标是模数(除数)。
现在来尝试研究一下《孙子算经》的“物不知数”问题。3,5,7的最小公倍数是105. 如果找到一个解 x, 则 x+105 还是一个解,因为它们在除以 3, 5, 7 时“同余”,如果 x 满足 “物不知数” 的条件,x+105 也必然满足。用这篇文章里介绍的数学语言,我们说 “物不知数” 问题的解是一个 “模数为105的同余类”。 现在我们只需要求得此同余类中任何一个数即可。
我们把 “物不知数” 的条件列出:[x]3 = [2]3, [x]5 = [3]5, [x]7= [2]7.
求解的办法实际上是 “拆分”。也就是说,我们先来求三个数 a, b, c, 分别满足较简单的条件:
[a]3 = [1]3, [a]5 = [0]5, [a]7 = [0]7.
[b]3 = [0]3, [b]5 = [1]5, [b]7 = [0]7
[c]3 = [0]3, [c]5 = [0]5, [c]7 = [1]7
如果能简单地求得这三个数 a, b, c, 那么我们容易看到,x = 2a+3b+2c 即为原 ”物不知数“ 问题的一个解。这是因为我们刚刚介绍过的同余类四则运算律。验证如下:
[x]3 = [2a+3b+2c]3 = 2 [a]3 + 3 [b]3 + 2 [c]3 = 2 [1]3 = [2]3,
[x]5 = [2a+3b+2c]5 = 2 [a]5 + 3 [b]5 + 2 [c]5 = 3 [1]5 = [3]5,
[x]7 = [2a+3b+2c]7 = 2 [a]7 + 3 [b]7 + 2 [c]7 = 2 [1]7 = [2]7,
那么,问题就归结为求解 a, b, c 三个数. 先看 a. 它满足的条件是,同时被 5, 7 整除,被 3 除余 1。 由于 5, 7 互素,所以 a 必须被 5 × 7 = 35 整除。很容易找到 35 的倍数中被 3 除余 1 的数:a=70. 这个求 a 的过程就是秦九韶的所谓 “三人同行七十稀”。
同理可得 b=21, 即秦九韶所谓 “五树梅花廿一支”,以及 c=15, “七子团圆正半月”。所以我们得到了 “物不知数” 问题的一个解:
2a+3b+2c = 2 × 70+3 × 21 + 2 × 15 = 233.
之前已经提到,加上或者减去 3, 5, 7 的公倍数 105,仍然还是一个解。所以我们得到绝对值最小的解:233-105 × 2 = 23. 此即 “ 除百零五便得知”。
可以看到,解决这个问题的关键,其一在于“拆分”,其二在于求最简单形式的同余方程组的解。而此问题的解的存在性和唯一性,都是由这最简单形式的同余方程组决定的。我们可以仔细地来审视一下求得 a 的过程。其实这个过程中更关键的未知数是一个乘数 w, 满足 [5 × 7 × w]3= [1]3. 一旦求得这个 w, 则 a = 5 × 7 × w. 前面已经提到过,这个方程表明, w 应该是 5 × 7 的同余类倒数(以3为模数)。而这个倒数存在当且仅当 5 × 7 与 3 互素。当然,在这个例子里,5 × 7 的确与 3 互素。普遍而言,这个条件则是此类问题存在唯一解的充分必要条件。
总而言之,秦九韶实际上证明了:“物不知数” 问题存在唯一解当且仅当该问题所涉及的所有模数两两互素。
秦九韶对这个问题的解答被称为 “中国剩余定理”,它是很罕有的被世界数学界公认由中国人最早给出完整证明的数学定理。它在现代数学中有极其重要的推广,其普遍形式是现代数学的基石之一。
回到正题。这一节介绍的是有限域。首先回忆一下,“域” 就是一些互相能做加减乘除四则运算的东西放在一起的一个集合。我们在前面的篇章里介绍过有理数域、代数数域、实数域、p-adic 数域。它们都包含无限个元素。而在这一篇里,我们已经看到了有限域的例子:比如模5同余类组成的集合,{ [0], [1], [2], [3], [4] }, 记为 F5。
这些元素之间可以做加、减、乘运算,其过程无非是先把它们当作整数进行运算,再将运算结果模5。除法就没有这么直接,因为普通整数除法的结果不一定是整数,模5这种操作可能没有意义。不过我们知道除以一个数等价于乘上这个数的倒数,而当模数为素数的时候,非零同余类的倒数总是存在的。所以在 F5 里面我们也可以自由地做除法。
显然,对每一个素数 p, 我们就有一个有限域 Fp. 其它的有限域都是什么样子呢?数学论证表明,任何一个有限域,它的元素个数必定是某个素数的幂,pn, 而它的元素都满足多项式方程
xpn -x = 0.
实际上,正如有理数域通过添加多项式方程的解得到更大的数域,Fp 添加以上方程的所有解就得到元素个数为 pn 的有限域。不过,对于不熟悉抽象数学语言的读者,有限域跟其它我们提到的数域有一个重要差别:有限域的元素一般不存在直观的表示。而其它数域的元素一般会有比较直观的表示方法,比如,代数数一般可以表示为复数a+bi, 实数可以表示为小数,p-adic 数可以表示为大数,等等。所以,其实我们应该承认:余数非数。
由于有限域的元素个数有限,以它们为系数的“向量空间” 就成为有限的对象,同时又具有普通向量空间所具有的丰富结构,很多科学工程领域应用有限域上的向量空间帮助建立数学模型。比如,有限域在密码学和编码学中发挥着极其重要的作用。
纯数学领域,对有限域上代数方程组的研究引导数学家韦伊在 1949 年提出一系列猜想,试图将数论问题与几何(拓扑)概念作类比。 为了解决韦伊猜想,格罗登迪克发展出了一整套新概念、新方法、新体系,形成了“现代代数几何”。发展至今,这一“发源于”有限域的新体系已经全面改变了整个数学的观念和语言。
下一节我们将把眼光转向另一个创生新数的领域 ── 数学物理,接触一些似数非数,遵循另类运算规则的数学对象。首先出场的将是听上去很像从中国传统文化中走下来的“四元数”。
联系客服