模的世界

本页面已浏览208次

本章我们进入模的世界!

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

定理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\)1

证明:(略)

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

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

定理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。2

多么令人悲伤的结论啊!这个定理向我们表明,我们没法找到一个具有“魔力”的多项式,使其只为我们产生素数。不过有一些多项式表现很不错,比如\(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以“中国余数定理”得名。3

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


  1. 这里我们假定所有多项式的系数都是整数。下同。 

  2. 定理3.8要求多项式首项系数\(a_n\gt 0\)。但定理3.13的叙述中并没有强调这点。我还要再思索一下。 

  3. 我看的教材到此戛然而止,并没有给出具体的解法。有可能在后续的章节中有解法。暂且先这样。 

Previous Post Next Post