同余:从无限到有限


绝大多数未经过中学生数学竞赛训练的人们,普遍会觉得初等数论里同余方程的概念相对突兀:好端端的整数进行加、减、乘法运算,小学阶段就已经进行过系统的学习和训练;考虑到有理数(正如北京师范大学数学科学学院的王昆扬教授所指出,将 rational number 翻译为比例数或许更为准确)的情形,对于非零有理数,我们还可以熟练地进行除法运算(现在有了计算器,相信两位数的加减都算不利索咯)。这就已经很好了。何苦要给自己找不痛快,非要考虑同余方程。然而,实际上,这种‘模数’的观点在现实生活中非常普遍,简单列举如下:

1. 众所周知,一周有 \(7\) 天,我们会按照星期一、星期二、……的方法数下来,直到星期日。但接下来的一天呢?如果你非要说明天星期八,无疑会被当做外星人。翻阅日历,我们会发现公元 \(2019\) 年 \(1\) 月 \(1\) 日是星期二,再过 \(28\) 天,即 \(2019\) 年 \(1\) 月 \(29\) 日,不用看日 历,我们也会知道它还是星期二,换句话说,我们在计算星期几的时候,会有一个基本操作:将 \(7\) 以及 \(7\) 的倍数‘清空’,重新开始计数。

2. 按照农历历法,自 \(2019\) 年 \(2\) 月 \(5\) 日(大年初一)起的一年是己亥年,也就是我们通常说的猪年。我国著名数学家陈省身出生于 \(1911\) 年 \(10\) 月。不看日历,你是否可以算出陈省身的属相呢?简单计算,你会发现 \(2019-1911=108=12\times 9\), 所以陈省身是属猪哒!类似于星期的计算,我们在这里会将 \(12\) 的倍数‘清空’。向前推一年,\(2018\) 年是农历戊戌年,第三次不看日历,你是否可以知晓中国近代历史上著名的戊戌变法是在哪一年呢?李碧华写过一本名为《胭脂扣》的小说,在开篇,女主角与算命先生的对话同样体现了这种干支纪年法。当一个算命先生也不容易,有可能遇到鬼,也有可能遇到残酷的同行竞争,参考  林开亮:算命是胡扯,猜姓却不然 。

chern.jpg

3. 在以 \(24\) 小时制计时的一天中,当时间的指针超过 \(23:59\) 时,如果你不是夜猫子,早就应该休息了;作为时钟,它会将 \(24\) 的倍数‘清空’,以 \(00:00\) 重新开始计时,还好这不是定时炸弹计时结束的标志。

4. 民主选举的唱票环节,我们通常采用画‘正’字的方法(虽然当下的各种综艺节目的投票、唱票早已进入电子唱票的时代)。为统计候选人得票结果,工作人员只需统计完整的‘正’字个数,将其乘以 \(5\) (汉字‘正’的笔画数为 \(5\)),再加上额外的笔画数(不完整的‘正’字)即可。事实上,这是将得票数按照‘个数 \(5\)’进行统计。

事实上,模数的观点、同余的方法并不神秘,而是人们在探索数学世界的旅途中发现的工具。除了上面提及的干支纪年法,我们的祖先还积累了很多关于同余的经验,例如:求一术、韩信点兵等;关于同余方程组求解的理论性结果,也被冠以中国剩余定理的名字,关于这些内容,更详细 的叙述,可参考  林开亮:从射雕到九章——在天大理学院物理系的报告 。伴随着时代的发展,作为同余的特殊情形,有限域,在密码、编码方向又带来了广阔的应用空间,可参考 [4, 第 4 章] 和 [9, 第 17 章]。让我们从整数集合 \(\{0, \pm 1, \pm 2, \cdots \}\) 开始,它的标准记号为 \(\mathbb{Z}\)。

选定一个正整数 \(m\),并称其为模数(例如,令 \(m=15\) 为模数)。若整数 \(a, b\) 的差能被 \(m\) 整除,我们称\(a, b\) 模 \(m\) 同余,或者,整数 \(a\) 模 \(m\) 同余于 \(b\),并且记为\(a\equiv b\pmod m\),例如:由 \(15|((-13)-2)\) 可知 \(-13\equiv 2 \pmod {15}\),而 \(2019\equiv 9\pmod {15}\)。不同余的定义是自然的,例如 \(32\not \equiv 4 \pmod {15}\)。勒让德使用 \(=\) 表示同余;为了与一般的等号区别,高斯最早引入 \(\equiv \) 表示同余。将整数里所有 \(m\) 的倍,此时我们留下了有限个‘非负整数’\(\{0, 1, 2, \cdots , m-1\}\)。需要注意,这里的‘整数’不再只是它本身,而是代表了具有相同性质的一些数。正如前面提到的,我们只需清楚某天是工作日(需要上班),无需单独记忆 \(2019\) 年 \(1\) 月 \(1\) 日、\(8\) 日、\(29\) 日是 星期二,这样做并无不妥。同样有鉴于此,对于‘清空’\(m\) 倍以后的集合,人们将其记为

$$\mathbb { Z } / m \mathbb { Z } : = \{ \overline { 0 } , \overline { 1 } , \cdots , \overline { m - 1 } \}$$

关于它,还能说些什么?我们是否可以像正常的整数一样,进行加、减、乘法运算呢?答案是肯定的,以模数 \(m=15\) 为例,可以进行如下的计算

\[\begin{array}{c} 5-2\equiv 3\pmod {15},\ 11+9\equiv 5\pmod {15},\ 3-14\equiv -11\equiv 4\pmod {15}\\[2mm] 3\cdot 5\equiv 0\pmod {15},\ 2\cdot 8\equiv 1\pmod {15},\ 7\cdot 8\equiv 11\pmod {15},\ 12\cdot 12\equiv \ 9\pmod {15} \\[2mm] 2^2\equiv 4\pmod {15},\ 5^2\equiv 10\pmod {15},\ 12^3\equiv 3\pmod {15}\\ \end{array}\]

它们可以像整数一样进行加、减、乘法运算,虽然结果在整数的意义下并不唯一。但 \(3\cdot 5\equiv 0\pmod {15}\) 确实有些奇怪,注意 \(3\not \equiv 0\pmod {15}, 5\not \equiv 0\pmod {15}\),但 \(3\cdot 5\equiv 0\pmod {15}\),整数中并无这种现象出现。

截至目前,我们并没有谈及除法运算。允许分数出现以后,在有理数 $\mathbb{Q}$ 中,任意非零数都可以作被除数。但为了在‘有限’的情形下进行除法,人们在绝大多数情形选择素数 $p$ 作为模数。如此一来,上例出现的非零数相乘同余于零的情形将不再发生(为什么?)。根据整数互素的性质,若 $(p, a)=1$,则存在整数 $\alpha, \beta$,使得 $$\alpha\cdot p+\beta\cdot a=1.$$ 对这个等式模 $p$,我们有 $\beta \cdot a\equiv 1\pmod p$,换言之,类似于有理数情形的 $23\cdot \dfrac{1}{23}=1$,对于任意非零元,都存在唯一的数(在模 $p$ 的意义下),使得二者乘积为 $1$:例如对于 $p=11$,计算可得 $3\cdot4\equiv1\pmod{11}, 2\cdot6\equiv1\pmod{11}$,可以采用如下的表示(虽然这看起来有些奇怪,但请允许我们继续) $$\frac{1}{3}\equiv 4\pmod{11},\quad \frac{1}{2}\equiv6\pmod{11}.$$ 仍需指出一点,在有理数中 $\dfrac{1}{3}$ 是唯一一个与 $3$ 相乘为 $1$ 的元素(人们称 $\dfrac{1}{3}$ 与 $3$ 互逆,并将 $\dfrac{1}{3}$ 称为 $3$ 的逆元);但对于不同的素(数)模数,同一元素的逆元会因为模数的改变而改变。例如 $$\frac{1}{3}\equiv4\pmod{11},\quad \mbox{而}\quad \frac{1}{3}\equiv 6\pmod{17}.$$ 鉴于模数为素数的情形有这么好(可以像有理数一样进行除法运算)的性质,人们发明了新的记号,将 $\mathbb{Z}/p\mathbb{Z}$ 简记为 $\mathbb{F}_p$,并将它们称为有限域,例如 $\mathbb{F}_{5}, \mathbb{F}_{17}, \mathbb{F}_{19}$ 均为有限域。是一个伴随着代数发展产生的概念,目前我们强调的是‘有限’二字(想想看,对于模数不是素数的情形,有没有什么办法,使得除法运算可以进行?提示:在模数 $m=15$ 时,有 $2\cdot8\equiv1 \pmod{15}$)。

人们认知世间万物都是从有限开始,慢慢进入无限。关于这样一个过程,华罗庚在 [3, 二] 的叙述非常精彩:

“以识数为例。小孩子识数,先学会数一个、两个、三个;过些时候,能够数到十了;又过些时候,会数到二十、三十、……一百了。但后来,却决不是这样一段一段地增长,而是飞跃前进,到了某一个时候,他领悟了,他会说:‘我什么数都会数了’。这一飞跃,竟从有限跃到了无穷!”。

《数学归纳法》“数学小丛书”系列(截至 \(2002\) 年,共计 \(18\) 册)的一本。这些可读性极强的系列图书是在华罗庚的倡导下,为推广我国中学生数学竞赛活动,许多知名数学家编写的,更多的相关内容,可参考  五虎上将,威震京城:中科大数学系与中学生数学竞赛  与  李克正:和肖刚一起学习的日子 。

之前的讨论反复强调‘有限’二字。通过模数,我们将无限的整数集合变成了‘有限’的集合,并且对于素模数,保持了它们在有理数情形的四则运算。这样做的好处是什么呢?正如上文,从有限到无限的认知,可以通过有限的积累得到;而无限到有限呢?取模数作为一种方法,它提供了一个途径、桥梁,使得我们可以用有限讨论无限。数学家们更倾向于建立不同数学对象之间的桥梁,英国著名的科普作家西蒙·辛格在 [7, 第五章] 中如是说:

“数学中的桥有着巨大的价值。它们使生活在孤岛上的各个数学家社团能够交流想法,探讨彼此的创造。数学是由未知海洋中的一个个知识孤岛组成的。例如,在那里有一个几何学家占据的孤岛,他们研究形状和形式;也有一个概率论的孤岛,数学家们在那里讨论风险和机遇。有着几十个这样的孤岛, 每个孤岛上使用它们各自独立的语言,这种语言别的岛上的居民是不懂的。几何学的语言与概率论的语言有很大差异,而微积分中的术语对那些只讲统计学语言的人是没有意义的。”

利用取模数,人们建立了从无限到有限的工具;它的一个的基本应用如下所述:

观点 \(1\):给定关于整数的某个断言 \(P\)。若 \(P\) 在整数范围内成立,那么对于任意模数 \(m\),断言 \(P\) 在 \(\mathbb {Z}/m\mathbb {Z}\) 中同样成立。

注意原命题与逆否命题等价,人们通常利用上述基本观点的逆否命题:

观点 \(2\):给定某个关于整数的断言 \(P\)。若存在某个模数 \(m\),使 \(P\) 在 \(\mathbb {Z}/m\mathbb {Z}\) 中不成立,则此断言在整数中不成立。

关于这样两个基本观点,需要指出:只能在保证断言 \(P\) 在 \(\mathbb {Z}/m\mathbb {Z}\) (对于某个模数 \(m\))有意义的情形下才能使用。诸如 \(15>3\)、以及 \(60\) 为偶数的断言,在 \(\mathbb {Z}/m\mathbb {Z}\) 中一般并无意义,因此不能使用。这种观点试用的题目中,有一大类是关于不定方程求解的问题。下面通过一个典型的例子来进行说明。

证明:数列 \(11, 111, 1111, \cdots \) 中没有平方数。

这个题目被收录于 [6] 的附录中(\(6.13.1\))。经历过诸多数列习题的考验,不难看出数列中的数字可以按照如下的方式重新表述(变换形式,试图以更简洁的方式理解题目):

\[\begin {array}{rcl} 11&=&1+10\\ 111&=&1+10+100\\ 1111&=&1+10+100+1000\\ &\cdots & \end {array}\]

回到断言本身,证明数列里没有平方数。考虑两种方法。

方法 \(1\)。不妨假定存在某个数为平方数,这个数无疑只能是奇数,即:对于某个正整数 \(k\),存在等式

\[1+10+100+1000+\cdots =(2k+1)^2=4k^2+4k+1.\]

抵消左右两端的 \(1\),我们有

\[10+100+1000+\cdots =4k^2+4k.\]

等式右边可以被 \(4\) 整除,而对于等式左边,从 \(100\)(如果存在)起,所有的数都可以被 \(4\) 整除,因此如果假定成立,那么 \(10\) 就可以被 \(4\) 整除,这显然是不可能的。换句话说,原结论成立。

重新理解一下这个题目的求解。我们在前面反复提及‘有限’的说法,如果数列里存在某项(记为 \(a_n\))为平方数,那么模掉任意的数以后,\(a_n\) 同样还是平方数。但本题要证明数列中不含有平方数,根据前面的叙述,我们只需说明对于某个模数,数列取模数以后,不存在平方数即可。

方法 \(2\)。数列中所有数均为奇数,如果对数列模 \(2\),你会发现,数列将变成 \(1, 1, 1, \cdots \),所有的数均为平方数(显然 \(1^2\equiv 1\pmod 2\)),初步的尝试以失败告终。

因为 \(10^n\equiv 1\pmod 3\),若对数列模 \(3\),它将是 \(2, 1, 2, 1, \cdots \)。在 \(\mathbb {Z}/3\mathbb {Z}\) 中,计算可得 \(1^2\equiv 1\pmod 3,\ 2^2\equiv 1\pmod 3\),这样一半的数是平方数,这个尝试依旧失败。

注意 \(100\) 及以后的数均可被 \(4\) 整除,而 \(1\equiv 3\pmod 4, 10\equiv 2\pmod 4\),若对数列模 \(4\),它变成 \(3, 3, 3, \cdots \)。在 \(\mathbb {Z} /4\mathbb {Z}\) 中,计算可得 \(1^2 \equiv 1\pmod 4, 2^2\equiv 0\pmod 4, 3^2\equiv 1\pmod 4\),仅有的平方数为 \(0\) 和 \(1\),因此 \(3\) 不是平方数。

综上,对数列进行 \(\pmod 4\),所有的数均不是平方数,故原数列中没有平方数。

对于这个题目,我们进行两点说明:

第一:取模数的做法最早由已故著名数学家肖刚指出,单墫又进行了优化( 单墫:忆肖刚 )。在 [6] 中,波利亚提供了其它解法。有兴趣的读者可以翻阅。

xg.jpg

上图左、右两人依次为李克正肖刚。\(1986\) 年 \(8\) 月的国际数学家大会ICM)在美国伯克利举行,这张照片拍摄于那段时间。感谢李克正教授在  几张老照片  中的提供。

第二:进行对比,我们不难体会,两种方法本质一样,仅在叙述上略有不同。我们依旧进行两种方法的讨论,这符合波利亚在 [5, 第 53 节] 阐明的下述观点:

“即使我们已经成功地找到了一个满意的解答,我们仍然会对找到另一种解答感兴趣,正如我们希望通过两种不同的直觉来感觉一个物体一样,我们希望通过两种不同的途径使我们确信一个理论结果的有效性。在有了一种证明以后,我们还想找到另外一中,就好像我们在看到一个物体以后,还希望能 触摸它。”

polya.jpg

聪明的你,或许已经意识到,给定关于整数的某个断言 \(P\),若其关于某个模数成立,并不足以保证在整数的情形成立。是否可以关心这样的问题:断言 \(P\) 关于多个、甚至是无限多个模数成立,能够推出断言 \(P\) 在整数情形成立呢?关于这种类型的问题,涉及到更深刻‘局部——整体 原则’。

为了认知无限,人们发展了多种工具;同余的观点,正是伴随着人们对于数论的探索而逐步发展和建立的。如果你觉得不太适应,这也再正常不过。毕竟,人们为了认识它的结构,也经历了很长的历史。高斯在 1801 出版的巨著 [2] 中也用了前面几章对同余进行了严格的讨论(同样是在这 本书中,高斯证明了正 17 边形可以尺规作图)。对于素模数更精细的论证,高斯得到他称之为“基本定理”的结果;对于互异的奇素数 \(p, q\),令 \((\frac {p} {q})\) 表示勒让德符号,则

\[\left(\frac{p}{q}\right)\cdot\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.\]

当代,人们将这个叙述称为二次互反律。就此结论,时代更早的欧拉进行过猜测和不完整的计算;勒让德给出了一个不完整的证明;高斯,最早给出了完整证明(而且远不止一个证明),可参考 [1, 第 2 章]、[8, 第 3.8 节、第 4.6 节]。在 [8, 第 4 章] 中,数论学家韦伊还对勒让德高斯进行了一些严肃的八卦,关于韦伊,可参考吴帆翻译的这份 André Weil 年表 。友情提示:千万不要被点开的标题吓到,译者顽皮地添加了非常详细的注释、增补。

作为一种工具,同余的一个优势在于仅涉及‘有限’个数的运算;若素模数 \(p\) 变得比较大,\(\mathbb {F}_p\) 的计算量会比较大,人们会采利用诸如费马小定理威尔逊定理、上面提及的二次互反律等工具;但若素数 \(p\) 变得更大(例如:长度为几 百位),即便对于长于计算的机器而言,相关的问题也会非常困难,即:计算量会随着数量的增加而变化,例如:判断一个正整数 \(m\) 是否为素数的威尔逊定理,其叙述如下

\[m\ \mbox {为素数}\Leftrightarrow (m-1)!\equiv -1\pmod {m}.\]

当 \(m\) 很大的时候,阶乘的计算量就非常恐怖。因此,前面反复提及的有限,更多是理论上的说法。直到目前,搜寻大素数、大整数的分解、寻找有限域的生成元等问题依旧十分困难。

致谢 感谢西北农林科技大学理学院的林开亮教授、中国科学院数学与系统科学研究院的陈亦飞研究员、首都师范大学的李克正教授。

参考文献

  1. 冯克勤;《代数数论简史》; 长沙;湖南教育出版社;2002年。

  2. 高斯(著);潘承彪、张明尧(译);《算术探究》;哈尔滨;哈尔滨工业大学出版社;2011 年。

  3. 华罗庚;《数学归纳法》;上海;上海教育出版社;1964年。

  4. 大栗博司(著);尤斌斌(译);《用数学的语言 看世界》;北京;人民邮电出版社;2017年。

  5. 波利亚(著);涂泓、冯承天(译);《怎样解题:数学思维的新方法》;上海;上海科技教育出版社;2007年。

  6. 波利亚(著);刘景麟、曹之江、邹清莲(译);《数学的发现》;北京;科学出版社;2006年。

  7. 西蒙·辛格(著);薛密(译);《费马大定理:一个困惑了世间智者\(358\)年的迷》;桂林;广西师范大学出版社;2013年。

  8. 安德烈·韦伊(著);胥鸣伟(译)、王元(校);《数论:从汉穆拉比到勒让德的历史导引》;北京; 高等教育出版社;2010年。

  9. 吴军;《数学之美》;北京;人民邮电出版社;2014年。

作者简介: 陈见柯,2013 年于首都师范大学数学科学学院获得博士学位,目前于中国传媒大学数据科学与智能媒体学院担任讲师。