 我们在做小学生的时候，经常会遇到诸如此类的题目：已知2019年10月1日是星期二，请问2018年的10月1日是星期几？众所周知，这题的计算很简单，只要用365天除以每周七天的周期，看看余数是多少，最后根据已知条件调整一下即可。由于365除以7的余数是1，而2019年10月1日是星期二，所以很容易得到2018年的10月1日是星期一。在上面这个问题上，假如两个日子相差不多，我们可以直接数，但假如两者相差很大，比如说前后相隔有1000天之多，那么简单的数数就显得力不从心了，甚至近于不可能。这个时候，对“余数”的关注就成了解题的关键所在。
在自然数范围内，两数相除，要么除尽，要么有余数。前者就是整除问题，后者则是余数问题。在余数问题中，有一些数除以同一个数的余数是相同的。比如：7和0除以7的余数都是0，同样，除以7余数是0的还有14、21、28、35、……。又比如：24和9除以5的余数都是4，47和11除以9的余数都是2，……。它们都有一个共同的特征，即它们同时除以同一个整数后得到的余数相同，也就是我们要讲的“同余”（congruence）概念。同余的思想可以追溯到古希腊数学家欧几里得的《几何原本》，直到德国数学家高斯之前，历代数学家已经积累了丰富的整数知识，高斯首次在他的成名作《算术探索》（Disquisitiones Arithmeticae，1800年）中用标准化的符号对同余问题进行了系统地处理，他发明的同余符号“≡”被沿用至今。如果整数a和b被整数m（称为模，modulo）除的余数相同，我们就称a和b关于模m同余，简称同余。记作a≡b(mod m)，例如31≡5(mod 13)。不过，高斯在他的《算术探索》开篇第一段是用另外一种方式来表述同余的。他说：“若数a是数b和c的差的除数，则称b和c对于a同余；在相反的情形，则称b和c对于a不同余。我们把数a称为模。在第一种情形，数b和c中的每一个称为是它们中的另一个的剩余。而在第二种情形，则称为是它们中的另一个的非剩余。”高斯想说明什么呢？其实高斯关于同余的定义，与我们前面的定义是一回事。高斯是通过两个关于模m同余的整数可以被该模整除这个角度来定义同余的。通过下面的图，大家就可以很清楚地明白高斯如此定义的理由。当两个关于模m同余的整数相减时，他们的余数刚好相抵消，因此他们之间的差数一定可以被该模整除。同余的概念和符号适用于所有整数，无论是正的还是负的整数，但不能推广到分数。例如：﹣9和﹢16对模5同余；﹣7和﹢15对模11同余。这里显而易见，由于0可以被任何数整除，所以对于任意的模来说，每个数都和0同余。同余在日常生活中很常见。例如，钟表对于小时是模12或24的，对于分钟和秒是模60的；日历对于星期是模7的，对于月份是模12的；水表电表通常是模1000的。同余式的发明，使得我们能够像处理方程一样的方式来处理整除问题。高斯本人对于同余式的符号曾说过这样的话：“这种新计算法，适应于经常发生的基本要求，所以即使没有天赋才能那样无意识的灵感，只要掌握了这种计算方法，不论是谁都能解决问题。这就是这种新计算法的长处。即便是天才，碰到错综复杂的情况不知如何是好时，也可以机械地解决问题。”（1）反身性（Reflexive Property）：若a是整数，则a≡a(mod m)；（2）对称性（Symmetric Property）：若a和b是整数，且a≡b(mod m)，则b≡a(mod m)；（3）传递性（Transitive Property）：若a、b和c是整数，且a≡b(mod m)和b≡c(mod m)，则a≡c(mod m)。前两条性质很显而易见，大家在任何一本初等数论的教材中都能找到相关证明，这里就不再赘述。最后一条“传递性”可从下图中得到证明：（1）若a≡b(mod m)，c≡d(mod m)，则a±c≡b±d(mod m)；（2）若a≡b(mod m)，c≡d(mod m)，则a×c≡b×d(mod m)；（3）若a≡b(mod m)，且n∈N，则an≡bn(mod m)；（4）若a≡b(mod m)，且k是整数，则k×a≡k×b(mod m)；（5）若a≡b(mod m)，且m＝qn，则a≡b(mod n)。第（1）条模运算很好理解，这里再次用图形来解释一下第（2）条模运算的几何性质。如下图所示：从上图中我们可以很清楚地看到，除了面积为bd的这块矩形以外，其他都是m的倍数。至于第（3）条模运算，则是在第（2）条模运算基础上的延伸。即：若a≡b(mod m)，a≡b(mod m)，则a×a≡b×b(mod m)。另外，稍微有一些高中数学中多项式基础的朋友应该也不难理解。第（4）条模运算与第（3）条同理。但是，这里需要特别注意的是，对同余式作除法运算时要小心。若k×a≡k×b(mod m)，不一定可以推出a≡b(modm)。比如6≡12(mod 2)，两边同除以3，可以得到2≡4(mod 2)，但两边同除以2，得不到3≡6(mod 2)。这里，只有当GCD(k,m)＝1时，才可以进行除法运算。这个要格外小心。第（5）条模运算也是很显而易见的，因为a－b是m的倍数，而n又是m的约数，则a－b一定也是n的倍数。以上是同余的概念和基本的性质和模运算法则，下面我们来看看同余式到底有什么神奇的应用。我们知道210等于1024，290会是一个很庞大的数字，直接计算近于不可能，但我们可以通过刚刚学过的模运算将290进行简化。即：290≡445≡4×444≡4×1622≡4×522≡4×2511≡4×311≡12×310≡95≡9×94≡9×812≡9×42≡9×5≡45≡1(mod 11)哇，是不是很神奇啊！我们居然通过同余式和模运算将一个非常复杂的计算完成了。举一反三，用这个方法可以解决类似的问题，比如：今天是星期六，101000天后是星期几？应用2 求证：对于任意正整数n，32n＋1＋2n＋2必为7的倍数。这道题很多人的第一反应是数学归纳法，但在这里，我们通过同余式可以很快得到证明。32n＋1＋2n＋2≡3(32)n＋4×2n≡3×2n＋4×2n≡(3＋4)×2n≡7×2n≡0×2n≡0(mod 7)由于2n＋1≡0(mod3)，则2n≡﹣1(mod 3)，进而得到(﹣1)n≡﹣1(mod3)。因此，当且仅当n为正奇数时，2n＋1是3的倍数。一般而言，对于任意正整数m以及正奇数n，(m－1)n＋1必定是3的倍数。应用4 求99^9的末两位数字。（说明，由于排版问题，这里9^9代表99）一个数的末两位就是这个数除以100后的余数。根据上一题的一般性结论可知，99≡﹣1≡9(mod 10)，因此存在正整数n使得99＝10n＋9。由二项式定理将(10－1)9展开得到：(10－1)9＝109－C(9,1)108＋…＋C(9,8)10－1。除了最后两项C(9,8)10－1外，其余都是100的倍数。因此，99≡9×10－1≡89(mod 100)，910≡9×89≡1(mod 100)。所以对于模100而言，99^9≡910n＋9≡(910)n×99≡89，即末两位数字为89。由于n不可能是负数或者0，因此2n＋7一定是奇数，可知x也一定是奇数。又由于任何奇数的平方除以4一定余1，因此可以推出：2n＋7≡1(mod 4)，2n≡2(mod 4)。n显然只可能是1，此时x＝±3。应用6 ISBN是国际标准书号的英文缩写，它是应图书出版、管理的需要，并便于国际间出版品的交流与统计所发展的一套国际统一的编号制度，用以识别出版品所属国别地区或语言、出版机构、书名、版本及装订方式。2007年以前，书号一般由10位数字组成，它们分成四段，用半字线隔开，每段都有不同的含义。第一段是国家代码，第二段是出版社代码，第三段是书的代码，最后一段是校验码。国家代码以1位数居多，例如：英语国家是0和1,2是法语国家，3是德语国家，4是日本，5是俄语系国家，7是中国大陆出版物。小语种的国家号码一般是多位，例如：瑞典是91, 克罗地亚是953, 西班牙语国家尚没有统一，墨西哥是970, 哥伦比亚是958。其中校验码是由前9位数字的加权和模11确定的，这里不再介绍。国际标准化组织规定，从2007年1月1日起，国际标准书号升级为13位。现有的出版机构在其出版物前加上一个三位数字的前缀 “978”，新成立的出版机构则加上前缀“979”，4位~13位与以前一样。之所以规定新ISBN为13位，是为了与国际条形码编码EAN-UCC系统接轨，因为超市中商品的条形码都为13位。设ai(i＝1,2,...,13)表示13位ISBN 的各个数码，校验码a13的计算分如下两步进行：(1)计算s12≡[(a1＋a3＋…＋a11)＋3(a2＋a4＋…＋a12)](mod 10)。(2)若s12＝0, 则规定a13＝O; 若s12≠0,则规定a13＝10－s12。例如，高斯的《算术探索》（哈尔滨工业大学出版社，2011)的ISBN是978-7-5603-3409-7。s12≡[(9＋8＋5＋0＋3＋0)＋3(7＋7＋6＋3＋4＋9)]≡133≡3(mod 10)上面几个例子只是小试牛刀，有兴趣的读者朋友可以进一步阅读后面关于费马小定理、威尔逊定理和中国剩余定理的文章，以领略同余式的巨大威力，以及数论之美。以中国剩余定理中的“物不知数”为例：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？用数论中的同余式表达就是：x≡2(mod 3)，x≡3(mod 5)，x≡2(mod 7)。约翰·卡尔·弗里德里希·高斯（Carl Friedrich Gauss，1777年4月30日－1855年2月23日），德国数学家、物理学家、天文学家、大地测量学家，生于布伦瑞克，卒于哥廷根。高斯被认为是历史上最重要的数学家之一，并有“数学王子”的美誉。
高斯是一对普通夫妇的儿子。他的母亲是一个贫穷石匠的女儿。高斯三岁时便能够纠正他父亲的借债账目，这件事情已经成为一个轶事流传至今。他曾说，他能够在脑袋中进行复杂的计算。据说高斯在9岁时，就发明了一个快速计算等差数列求和的小技巧，在很短的时间内计算完成了他的小学老师在黑板上给出的问题：计算从1到100这100个自然数之和。他所使用的方法是：将第1个数字与最后1个数字相加、第2个数字与倒数第2个数字相加……以此类推，可以得到50对101，于是101×50＝5050便是答案。小时候高斯家里很穷，且他父亲不认为学问有什么用，但高斯依旧喜欢看书，话说在小时候，冬天吃完饭后他父亲就会要他上床睡觉，以节省燃油，但当他上床睡觉时，他会将芜菁的内部挖空，里面塞入棉布卷，当成灯来使用，以继续读书。当高斯12岁时，已经开始怀疑几何原本中的基础证明。当他16岁时，预测在欧氏几何之外必然会产生一门完全不同的几何学，即非欧几里德几何学。他导出了二项式定理的一般形式，将其成功的运用在无穷级数，并发展了数学分析的理论。高斯的老师布吕特内尔与他的助手马丁·巴尔特斯很早就认识到了高斯在数学上的天赋，同时卡尔·威廉·斐迪南·冯·布伦瑞克也对这个天才儿童留下了深刻印象。于是他们从高斯14岁起便资助其学习与生活。这也使高斯能够在公元1792年进入Carolinum学院（今天布伦瑞克工业大学的前身）学习，并在那里开始对高等数学作研究：独立发现二项式定理的一般形式、数论上的“二次互反律”、素数定理及算术—几何平均数。1795年，高斯转入哥廷根大学学习。1796年，19岁的高斯完成《正十七边形尺规作图之理论与方法》，成为第一位只用尺规作图成功画出正十七边形的人。18岁的高斯发现了最小二乘法，并猜测了质数定理。通过对足够多的测量数据的处理后，可以得到一个新的、概率性质的测量结果。在这些基础之上，高斯随后专注于曲面与曲线的计算，并成功得到高斯钟形曲线（正态分布曲线）。其函数被命名为标准正态分布（或高斯分布），并在概率计算中大量使用。高斯总结了复数的应用，并且严格证明了每一个n阶的代数方程必有n个实数或者复数解。1801年，在他的第一本著名的著作《算术探索》中，作出了二次互反律的证明，成为数论继续发展的重要基础。《算术探索》当时对于数学家也很难读，由于此书刚好七章，因此它曾被称为“七印封严之书”（这是西方人对难解之书喜用的词，近于中国人所谓的“天书”，典出《圣经·启示录》第五章第一节：“我看见坐宝座的右手有书卷，里外都写着书，用七印封严了” )后来迪利克雷作了详细注释。此书简洁完美的风格多少减慢了它的传播速度，而最终当富有才华的年轻人开始深入研读它时，由于出版商的破产，又买不到它了，甚至高斯最喜欢的学生艾森斯坦从未能拥有一本，有些学生不得不从头到尾抄录全书。高斯在最小二乘法基础上创立的测量平差理论的帮助下，测算天体的运行轨迹。他用这种方法，测算出了小行星谷神星（Ceres）的运行轨迹。谷神星于1801年被意大利天文学家皮亚齐发现，但因病他耽误了观测，从而失去了这颗小行星的轨迹。皮亚齐以希腊神话中的“丰收女神”对它命名，称为谷神星，并将自己以前观测的数据发表出来，希望全球的天文学家一起寻找。高斯通过以前3次的观测数据，计算出了谷神星的运行轨迹。奥地利天文学家海因里希·欧伯斯根据高斯计算出的轨道成功地发现了谷神星。高斯将这种方法发表在其著作《天体运动论》中。1807年，高斯成为哥廷根大学的教授和当地天文台的台长。为了获知每年复活节的日期，高斯推导了复活节日期的计算公式。他的母亲是文盲，从未记录他出生的日期，只记得他出生于耶稣升天节前八天的一个星期三（复活节后第三十九天）。高斯后来在找到复活节的日期的情况下解决了关于他出生日期的这个难题，并且继而推导出计算过去和未来年份复活节日期的方法。1818年至1826年间，高斯主导了汉诺威公国的大地测量工作。通过最小二乘法为基础的测量平差的方法和求解线性方程组的方法，显著地提高了测量的精度。高斯亲自参加野外测量工作。他白天观测，夜晚计算。在五六年间，经他亲自计算过的大地测量数据超过100万个。当高斯领导的三角测量外场观测走上正轨后，高斯把主要精力转移到处理观测成果的计算上，写出了近20篇对现代大地测量学具有重大意义的论文。在这些论文中，他推导了由椭圆面向圆球面投影时的公式，并作出了详细证明。这个理论直至现在仍有应用的价值。汉诺威公国的大地测量工作至1848年结束。这项大地测量史上的巨大工程，如果没有高斯在理论上的仔细推敲，在观测上力图合理和精确，在数据处理上尽量周密和细致，就不能圆满的完成。在当时的不发达的条件下，布设了大规模的大地控制网，精确地确定2578个三角点的大地坐标。为了用椭圆在球面上的正形投影理论以解决大地测量中出现的问题，在这段时间内高斯亦从事了曲面和投影的理论，并成为了微分几何的重要理论基础。相对论证明了宇宙空间实际上是非欧几何的空间。高斯的思想被近100年后的物理学所认可。高斯试图在汉诺威公国的大地测量中通过测量Harz的Brocken—Thuringer Wald的Inselsberg—哥廷根的Hohen Hagen三个山头所构成的三角形的内角和，以验证非欧几何的正确性，但未成功。高斯的朋友鲍耶的儿子雅诺斯在1823年证明了非欧几何的存在，高斯对他勇于探索的精神表示了赞扬。1840年，罗巴切夫斯基用德文写了《平行线理论的几何研究》一文。这篇论文的发表引起了高斯的注意。他非常重视这一论证，积极建议哥廷根大学聘请罗巴切夫斯基为通信院士。为了能直接阅读他的著作，从这一年开始，63岁的高斯开始学习俄语，并最终掌握了这门外语。高斯最终成为微分几何的始祖（高斯、雅诺斯和罗巴切夫斯基）之一。出于对实际应用的兴趣，高斯发明了日光反射仪。日光反射仪可以将光丛反射至大约450公里外的地方。高斯后来不止一次地为原先的设计作出改进，试制成功了后来被广泛应用于大地测量的镜式六分仪。19世纪30年代，高斯发明了磁强计。他辞去了天文台的工作，而转向物理的研究。他与威廉·韦伯（1804－1891）在电磁学领域共同工作。他比韦伯年长27岁，以亦师亦友的身份与其合作。1833年，通过受电磁影响的罗盘指针，他向韦伯发送出电报。这不仅是从韦伯的实验室与天文台之间的第一个电话电报系统，也是世界首创的第一个电话电报系统。1840年，他和韦伯画出了世界第一张地球磁场图，并且定出了地球磁南极和磁北极的位置。次年，这些位置得到美国科学家的证实。高斯在数个领域进行研究，但只把他认为已经成熟的理论发表出来。他经常对他的同事表示，该同事的结论自己以前已经证明过了，只是因为基础理论的不完备而没有发表。事实上高斯把他的研究结果都记录了起来。他死后，他的20部纪录着他的研究结果和想法的笔记被发现，证明高斯所说的是事实。一般人认为，20部笔记并非高斯笔记的全部。下萨克森州和哥廷根大学图书馆已经将高斯的全部著作数位化，并放置于互联网上。高斯的肖像曾被印刷在从1989年至2001年流通的10元德国马克纸币上。高斯是个热心的完美主义者且工作认真。他从来不是个多产作家，他拒绝发布他认为不完整和有瑕疵的作品。这符合他个人的座右铭。他的个人日记里有说到，他在几年还是几十年前就已提出了一些重要的数学发现，与他同一时代的人发表了他的发现。数学历史学家埃里克·梵钟估计，若高斯及时发表他的发现，将使高等数学往前推50年。高斯不喜欢教学是众所皆知的，教授的学生不多。有人说他只参加过1828年在柏林的科学会议，但他的一些学生却成为了具有影响力的数学家，其中包括理查德·戴德金、黎曼和弗里德里希·贝塞尔。索菲热尔曼建议在她死后由高斯接受她的荣誉学位。高斯往往都是很优雅地拒绝提出他怎么发现这些数学原理的直觉。他更喜欢他们来自“无中生有”，所以消除了所有他如何发现这些数学原理的痕迹。 参考文献： 高斯，《算术探索》，哈尔滨工业大学出版社，2011年； 华罗庚，《数论导引》，科学出版社，1957年； Kenneth H. Ross，夏鸿刚译，《初等数论及其应用》，机械工业出版社，2015年； Joseph H. Silverman，孙智伟等译，《数论概率》，机械工业出版社，2016年； 远山启（日），吕砚山等译，《数学与生活》，人民邮电出版社，2014年； James E. Pommersheim，Tim K. Marks，Erica L. Flapan，Number Theory: A Lively Introduction with Proofs, Applications, and Stories，John Wiley & Sons, Inc., 2010； Martin H. Weissman，An Illustrated Theory of Numbers, American Mathematical Society, 2010； - Oystein Ore, Number Theory and Its History, McGraw-Hill Company, 1948。
|
