本页面已浏览136次

本章我们进入模的世界！

我们先复习一下第一章中的几个定理：

定理1.12：令\(a, b, c, d, n\)为整数，且\(n\gt0\)。若\(a\equiv b\pmod{n}, c\equiv d\pmod{n}\)，则\(a+c\equiv b+d\pmod{n}\)。

定理1.13：令\(a, b, c, d, n\)为整数，且\(n\gt0\)。若\(a\equiv b\pmod{n}, c\equiv d\pmod{n}\)，则\(a-c\equiv b-d\pmod{n}\)。

定理1.14：令\(a, b, c, d, n\)为整数，且\(n\gt0\)。若\(a\equiv b\pmod{n}, c\equiv d\pmod{n}\)，则\(ac\equiv bd\pmod{n}\)。

定理1.18：令\(a, b, k, n\)为整数，且\(n\gt0, k\gt0\)。若\(a\equiv b\pmod{n}\)，则\(a^k\equiv b^k\pmod{n}\)。

也就是说，模的运算对加法、减法、乘法以及指数运算都是成立的。

练习3.1：证明41可以整除\(2^{20}-1\)。

证明：

1. \(2^5\equiv -9\pmod{41}\)（算术运算）
2. \((2^5)^4\equiv (-9)^4\pmod{41}\)（模的指数运算）
3. \(2^{20}\equiv81^2\pmod{41}\equiv(-1)^2\pmod{41}\equiv 1\pmod{41}\)
4. \(2^{20}-1\equiv0\pmod{41}\)

练习3.2：找到一个数字\(k, 0\le k\le11\)，s.t \(k\equiv 37^{453}\pmod{12}\)。

解：

1. \(37\equiv 1\pmod{12}\)
2. \(37^{453}\equiv 1\pmod{12}\)

所以，\(k=1\)。

练习3.3：找到一个数字\(k, 0\le k\le 6\)，s.t. \(2^{50}\equiv k\pmod{7}\)。

解：

\(2^3\equiv 1\pmod{7}\)。\(2^{50}=2^{3*16+2}\equiv{2^3}^{16}*4\pmod{7}\equiv 4\pmod{7})\)，所以\(k=4\)。

练习3.4：找到一个数字\(k, 0\le k\le 11\)，s.t. \(39^{453}\equiv k\pmod{12}\)。

解：

因为\(39\equiv 3\pmod{12}\)，所以\(39^{453}\equiv 3^{453}\pmod{12}\)。

解法一：简单观察可以知道，\(3^1\equiv 3\pmod{12}, 3^2\equiv 9\pmod{12}, 3^3\equiv 27\equiv 3\pmod{12}, 3^4\equiv 81\equiv 9\pmod{12}\)。所以，通过数学归纳法可以证明，3的奇数次方与3同模于12，3的偶数次方与9同模于12。而453是个奇数，所以\(39^{453}\equiv 3^{453}\equiv 3\pmod{12}\)。所以\(k=3\)。

解法二：

\(3^{453}=3^{3*151}=(3^3)^{151}\equiv 3^{151}\pmod{12}\)。

\(3^{151}=3^{3*50+1}=(3^3)^{50}*3\equiv 3^{50}*3=3^{51}\pmod{12}\)。

\(3^{51}=3^{3*17}=(3^3)^{17}\equiv 3^{17}\pmod{12}\)。

\(3^{17}=3^{3*5+2}=(3^3)^5*3^2\equiv 3^5*3^2=3^7\pmod{12}\)。

\(3^7=3^{3*2+1}=(3^3)^2*3\equiv 3^2*3=3^3\equiv 3\pmod{12}\)。

所以\(k=3\)。

练习3.5：证明\(39\mid (17^{48}-5^{24})\)

证明：

我们先看\(17^{48}\)。以下计算中省去对39求模的书写：

1. \(17^2=289=16\)
2. \(16^2=256=22\)
3. \(22^3=10648=1\)

换句话说，也就是\(17^{48}=((17^2)^2)^3=(17^4)^3\equiv 22^3=10648\equiv 1\pmod{39}\)。

同时，注意到\(5^4=625=1\)，所以\(5^{24}=(5^4)^6\equiv 1\pmod{39}\)。

所以\(17^{48}\equiv 5^{24}\equiv 1\pmod{39}\implies 17^{48}-5^{24}\equiv 0\pmod{39}\implies 39\mid 17^{48}-5^{24}\)。QED。

思考题3.6：令\(a, n, r\)为自然数，存在一个过程来找到\(k, 0\le k \le n-1\)，s.t \(k\equiv a^r\pmod{n}\)，而且在此过程中你不用乘以大于\(n\)的数字，而且这样的乘法步数不超过\(log_2 r\)。

这个步骤对于计算机而言而重要，在后续的公钥加密中还会深入讨论。

练习3.7：证明\(f(98)\equiv f(-100)\pmod{99}\)，其中\(f(x)=13x^{49}-27x^{27}+x^{14}-6\)。

证明：

由\(98\equiv -100\pmod{99}\)，以及模运算的定理，我们知道这个由加减乘和指数运算构成的多项式也一定同模于99。QED。

定理3.8：令\(f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0\)是一个多项式。令\(a, b, m\)为整数且\(m\gt 0\)。如果\(a\equiv b\pmod{m}\)，那么\(f(a)\equiv f(b)\pmod{m}\)。

证明：（略）

定理3.11：令\(f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0\)是一个多项式，其中\(n\gt 0, a_n\gt 0\)，那么存在一个整数\(k\)，s.t 如果\(x\gt k\)，那么\(f(x)\gt 0\)。

证明：

\(lim_{x\to \infty}\frac{f(x)}{x^n}=lim_{x\to \infty}a_n+a_{n-1}x^{-1}+...+a_1x^{1-n}+a_0x^{-n}=a_n\gt 0\)。只要\(x\)是正整数，\(x^n\)就会越来越大，这意味着\(lim_{x\to \infty}f(x)=\infty\)，所以我们可以找到某个数字\(k\), s.t. 对于所有\(x\gt k\)，\(f(x)\gt 0\)。QED。

定理3.12：令\(f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0\)是一个多项式，其中\(n\gt 0, a_n\gt 0\)，那么对于任何一个数字\(M\)，存在一个整数\(k\)，s.t 如果\(x\gt k\)，那么\(f(x)\gt M\)。¹

证明：（略）

上面两个定理与模运算无关。它们表明，一个首项系数为正整数的多项式函数值，从某一点开始不仅永远为正，而且会越来越大。

下面这个定理将多项式和素数加以关联。它表明，每个多项式都可以产生无数多个合数，也就是不存在一个多项式只产生素数。

定理3.13：令\(f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0\)是一个多项式。那么存在无数多的整数\(x\)，s.t \(f(x)\)是一个合数。提示：使用定理3.8和3.12。

证明：

第一步，我们要证明对于任意\(n\)次多项式，它最多取一个相同值的次数不超过\(n\)次。

我们首先证明：对于任意\(n\)次多项式方程（也就是\(f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0=0\)，它最多有\(n\)个根。

对于\(n=1\)，定理成立。假定\(n-1\)时，定理也成立。

假定\(a\)是方程的一个根，\(f(x)\)可以写成\(f(x)=(x-a)g(x)=0\)，其中的\(g(x)\)为\(n-1\)次。

\(f(b)=0 \Leftrightarrow b=a\)或者\(g(x)=0\)。所以\(g(x)\)最多提供\(n-1\)个\(f(x)=0\)的根，\(a\)是最多第\(n\)个根。所以\(f(x)=0\)最多有\(n\)个根。QED。

顺便说一句，这个定理在某种程度上可以被视为“代数基本定理”（Fundamental Theorem of Algebra）。

证明这个后，我们可以马上证明，任意\(n\)次多项式，也就是\(f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0\)得到某个特定值最多有\(n\)次。

下面进入定理3.13的证明。假定不存在任何整数，使得\(f(x)\)为合数，那么\(f(x)\)只能取值0,1或者一个素数。由代数基本定理，\(f(x)=0\)或者\(1\)的次数是有限的，所以\(f(x)\)可以得到无数多个素数。

假定\(f(x)=p\)，且\(p\)是一个素数。我们观察：

\(f(x+kp)-f(x)=a_n((x+kp)^n-x^n)+a_{n-1}((x+kp)^{n-1}-x^{n-1})+...+a_1((x+kp)-x)+(a_0-a_0)=kpa_n((x+kp)^{n-1}+...+x^{n-1})+kpa_{n-1}((x+kp)^{n-2}+...+x^{n-2}+...+kpa_1\)。因此\(f(x+kp)-f(x)\)一定是\(p\)的倍数，而\(f(x)=p\)，所以\(f(x+kp)\)也是p的倍数。但是，我们规定\(f(x)\)只能产生素数，所以\(f(x+kp)=p\)。换句话说，我们有无数个\(k\)使得\(f(x+kp)=p\)。这个和基本定理是矛盾的。

所以，\(f(x)\)不能只产生素数，只能产生无数多个合数。QED。

注意：上述证明中没有用到定理3.8和3.12。

另外一种证法用到3.8和3.12（至少是3.8）。

我们选择一个\(m\)，使得\(f(m)\ne \pm 1\)——这可以通过前一个证明中得到。选择一个素数\(p\)，使得\(p\mid f(m)\)。因此，对于\(m+pk\)，我们有\((m+pk)\equiv m\pmod{p}=0\)。根据定理3.8，有\(f(m+pk)\equiv f(m)\pmod{p}=0\)。所以\(f(m+pk)\)是一个合数。QED。²

多么令人悲伤的结论啊！这个定理向我们表明，我们没法找到一个具有“魔力”的多项式，使其只为我们产生素数。不过有一些多项式表现很不错，比如\(f(x)=x^2+x+41\)可以为我们连续产生80个素数（\(n\in [-40, 39]\)）。但在\(n=40\)时，\(f(40)=1681=41^2\)。

我们在考虑一个自然数对\(n\)的模时，它一定和某个小于\(n\)的非负整数同模。

定理3.14：对任意的整数\(a\)和自然数\(n\)，在集合\(\{0, 1, 2, ..., n-1\}\)中一定存在唯一的一个整数\(t\)，使得\(a\equiv t\pmod{n}\)。

证明：

根据“分而治之”中除法算法的描述，对于题中给定的\(a\)和\(n\)，存在\(a=bn+t\)，而且\(0\le t \lt n\)。所以\(t\in \{0, 1, 2, ..., n-1\}\)，而且满足\(a\equiv t\pmod{n}\)。QED。

定义：令\(n\)为一个自然数，那么集合\(\{0, 1, 2, ..., n-1\}\)被称为是\(n\)求模的标准完全余数集（canonical complete residue system modulo n）。

当然还存在其他余数集。

定义：令\(k, n\)为自然数，集合\(\{a_1, a_2, ..., a_k\}\)被称为\(n\)求模的完全余数集，如果一个整数正好与集合中的某个元素对\(n\)同模。

练习3.15：找到三个对4同模的完全余数集：一个是标准的，一个包含负数，一个不包含两个相邻的数。

定理3.16：令\(n\)为自然数。那么每个对\(n\)的完全余数集都有\(n\)个元素。

证明：（略）

定理3.17：令\(n\)为自然数。任何\(n\)个整数的集合\(a_1, a_2, ..., a_n\)，如果其中没有两个整数对\(n\)同模，那么它就是对\(n\)求模的完全余数集。

证明：

令\(A=\{a_1, a_2, ..., a_n\}\)，如果\(i\ne j \implies a_i\not\equiv a_j\pmod{n}\)。根据除法算法，\(a_i=q_in+r_i, a_j=q_jn+r_j\implies r_i\ne r_j\)，而\(0\le r_i, r_j\le n-1\)。于是\(n\)个\(A\)中的元素必然有\(n\)个不同的\(r\)，\(\forall a_k\in A,\: \exists r_k\in\{0, 1, ..., n-1\}\)，使得\(a_k\equiv r_k\pmod{n}\)。根据之前的定理，\(A\)构成一个完全余数集。QED。

线性同余

在第一章“分而治之”中，我们讨论了如何求解线性丢番都方程。我们现在开始着手处理模运算中的类似问题。我们的下一个目标是确定形如\(ax\equiv b\pmod{n}\)这样的方程有没有解。

练习3.18：在合适的标准完全余数集中找到下列同余方程的解。

1. \(26x\equiv 14\pmod{3}\)

解：3的标准完全余数集只有三个元素：\(\{0, 1, 2\}\)。14对3的余数是2，将\(0,1,2\)代入\(26x\)，可以得到\(0, 26, 52\)，而\(26\)对3的余数是2。所以\(x=1\)。

1. \(2x \equiv 3\pmod{5}\)

解：将\(\{0, 1, 2, 3, 4\}\)分别代入，得到\(x=4\)是本题的解。

1. \(4x \equiv 7\pmod{8}\)

解：将\(\{0, 1, 2, 3, 4, 5, 6, 7\}\)分别代入，得到本题无解。

1. \(24x\equiv 123\pmod{213}\)

解：这题用试错法做太累了。我们稍后来求解。

定理3.19：令\(a, b, n \in \mathbb{Z}, n\gt 0\)。那么\(ax\equiv b\pmod{n}\)有解当且仅当存在\(x, y\in \mathbb{Z}\:s.t\:ax+ny=b\)。

证明：假定\(ax\equiv b\pmod{n}\)有解，那么存在一个整数\(z\)并满足\(ax-b=nz \implies ax+n(-z)=b\)，定理成立。

又，假定存在\(x,y\)使得\(ax+ny=b\)成立，那么\(ax-b=n(-y)\implies n\mid(ax-b)\implies ax\equiv b\pmod{n}\)。

定理3.20：令\(a, b, n \in \mathbb{Z}, n\gt 0\)。那么等式\(ax\equiv b\pmod{n}\)有解当且仅当\((a,n)\mid b\)。

证明：有定理3.19以及定理1.48后，我们可以很方便证明本定理。

我们回头看之前留下的练习：\(24x\equiv 123\pmod{213}\)是否有解呢？

这个方程中，\(a=24, n=213, b=123\)。\((a,n)=3\)，而\(3 \mid 123\)。所以有解。可以得到\(x=14\)是本方程的解。具体求解过程略。

定理3.24：令\(a, b, n\in \mathbb{Z}, n\gt 0\)，那么：

1. 同余方程\(ax\equiv b\pmod{n}\)有解，当且仅当\((a, n)\mid b\)。
2. 如果\(x_0\)是上述方程的一个解，那么所有的解具有如下形式：\(x_0+(\frac{n}{(a, n)}*m)\pmod{n}\)，其中\(m=0, 1, 2, .., (a,n)-1\)。
3. 如果方程有解，那么在\(n\)的标准完全余数集中正好有\((a, n)\)个解。

证明：

定理3.24中的1就是定理3.20。

令\((a, n)=g\)。

如果\(x_0\)是方程的解，因此有\(ax_0\equiv b\pmod{n}\)。

\(ax_m=ax_0+a\frac{n}{g}*m=ax_0+(\frac{a}{g}*m)*n\implies ax_m-ax_0=kn\implies ax_m\equiv ax_0\pmod{n}\implies ax_m\equiv b\pmod{n}\)。QED。所以，定理中的\(x_m\)肯定是同余方程的解。

另外，假定\(x\)是同余方程的解，那么：

\(ax\equiv ax_0\equiv b\pmod{n}\implies a(x-x_0)\equiv 0\pmod{n}\implies \frac{a}{g}(x-x_0)\equiv 0\pmod{\frac{n}{g}}\implies x-x_0=t*\frac{n}{g}\implies x=x_0+\frac{n}{g}t\)。

最后，我们对\(t\)进行限定。\(t\)对\(g\)的模肯定可以得到一个标准完全余数集\(m=\{0, 1, 2, ..., g-1\}\)。

以上证毕定理的第二部分。

第三部分我不会证明。

线性同余系统：中国余数定理

线性同余系统或者说“中国余数定理”用来解决一系列联立的同余方程。

练习3.25：17个海盗抢了一堆金币。17个人平均分，剩下3个；他们杀死了一个海盗，16人平均分，剩下10个；他们又杀死一个海盗，15人终于可以平均分完这些金币。那么这些海盗抢来的金币最少有几个？

练习3.26（婆罗门笈多，Brahmagupta在公元7世纪时提出）一篮子鸡蛋，每次分别取出2/3/4/5/6个时，分别会留下1/2/3/4/5个鸡蛋在篮子里，而每次取7个时，正好能取完。篮子里最少要有几个鸡蛋？

这些题目都很有挑战性，但解题过程也很有趣！

这里我们先给出答案，分别是最少有3930枚金币以及最少有199个鸡蛋！

所有这些类似的问题都是对一元线性同余方程组求解，都可以归并到“中国余数问题”并有所谓“中国余数定理”（Chinese Remainder Theorem）来进行求解。相关知识可以参阅维基百科词条的说明。

下面我们先来看看比较简单的问题和相关的问题。

定理3.27：令\(a, b, m, n\in \mathbb{Z}, m\gt0, n\gt0\)。那么：
\(x\equiv a\pmod{n}\\x\equiv b\pmod{m}\)

有解当且仅当\((n,m)\mid a-b\)。

证明：

假定：\(x\equiv a\pmod{n}\\x\equiv b\pmod{m}\)，那么令\((n,m)=g\)，可以得到：

\(x-a=k_1n=k_1n'g\\x-b=k_2m=k_2m'g\)，两式相减得到：

\(a-b=k_2m'g-k_1n'g=g(k_2m'-k_1n')\implies g\mid a-b\)。

而如果\(g\mid a-b\)，那么我们有\(a-b=kg\)。对于第一个等式来说，\(x=a+ln\)肯定是解。我们要找出\(l\)使得\(x\)也满足第二个方程\(x=a+ln\equiv b\pmod{m}\Leftrightarrow ln\equiv b-a\pmod{m}\)。而既然\((n, m)=g\)，根据定理1.40，一定存在两个整数\(y, z\)使得\(ny+mz=g\implies ny-g=mz\implies ny\equiv g\pmod{m}\implies n(-yk)\equiv g(-k)=b-a\pmod{m}\)。令\(l=-yk\)，那么\(x=a-ykn\)同样满足第二个方程。

定理3.28：令\(a, b, m, n\in\mathbb{Z}, m\gt0, n\gt0, (n, m)=1\)。那么\(x\equiv a\pmod{n}\\x\equiv b\pmod{m}\)有一个以\(mn\)为模的唯一解。

证明：

根据定理3.27，我们知道这个方程组有解，因为\((n, m)=1\mid a-b\)。

假定\(x, x'\)都是方程组的解。那么有：

\(x\equiv a\pmod{n}\\x\equiv b\pmod{m}\)以及\(x'\equiv a\pmod{n}\\x'\equiv b\pmod{m}\)。

根据定理1.13，我们得到：

\(x-x'\equiv 0\pmod{n}\\x-x'\equiv 0\pmod{m}\)。

因此有：\(n\mid(x-x')\)以及\(m\mid(x-x')\)，而由于\((n, m)=1\)，根据定理1.48（或者2.25），我们有\(mn\mid(x-x')\implies x\equiv x'\pmod{mn}\)。QED。

中国余数定理是线性同余方程中的一个重要定理。最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位在《算法统宗》中将解法编成易于上口的《孙子歌诀》：

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知。

意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后再减去105或者105的整数倍，得到的数就是答案（除以105得到的余数则为最小答案）。比如说在以上的物不知数问题里面，使用以上的方法计算就得到：

\(70\times 2+21\times 3+15\times 2=233=2\times 105+23\)

所以一个特征解就是23。

对于线性同余方程组的形式化描述是：

定理3.29：令\(n_1, n_2, ..., n_L\)是正整数，且两两互质，也就是\((n_i, n_j)=1\:(i\ne j, 1\le i, j\le L)\)。那么\(L\)个线性同余方程构成的方程组：

\(x\equiv a_1\pmod{n_1}\\x\equiv a_2\pmod{n_2}\\...\\x\equiv a_L\pmod{n_L}\)有一个对\(n_1n_2n_3...n_L\)求模得到的唯一解。

王子和大师

高斯被称为“数学王子”，他对当代同模的理论作出了接触的贡献。而孙子是中国的一位数学大师。《孙子算经》第三卷中的第26个问题就是我们之前看到的同余问题。他是最早提出这样的问题的人，所以此类问题以及定理3.29以“中国余数定理”得名。³

本章极富挑战性！也许人类虽然习惯了“循环”，但是到了“循环”计算方面，还是很不习惯吧！