【初等数论】同余方程、与二次剩余互反律

~

剩余类可以看做是一个新的数系，它对 加减乘 运算是 封闭的 ，所以同余方程对多项式是有意义的。这里我们就来讨论下一元多项式方程（1）的解，当然它的解是一个剩余类集合，最多有 m 个解。

在正式解一个同余方程前，可以先进行一些简单的变形，最简单的就是将系数取模。对于两个多项式 ，如果它们的系数是模m同余的，则称 是模m同余的。记作

进一步，如果 恒成立，则称 是模 m 等价 的。比如根据费马小定理， 和 就是等价的。显然同余的多项式必定是等价的，但等价的多项式却不一定是同余的。例如上面的例子 和 就是等价的，但很明显能看出来其对应的幂次数签的系数并不同余，故两个式子不同余。使用等价多项式可以对方程进行降次，比如模为p的多项式 f(x) 一定可以通过多项式除法 降为次数小于p的多项式 r(x)。对于一般的合数 m，其实容易有 ，则有恒等式 ，故任何多项式都等价于某个次数小于 m 的多项式。

在这里我们先从一般的类似（1）式的最复杂的情况的一般同余方程开始讨论，接下来自然是要对模数进行分解，记方程（1）的解的个数为 ，且 中 两两互素。容易证明解方程（1）的问题可以等价为解方程组（2）的问题，且有 。

将 模数进行素数分解 ，则我们可以把问题集中在解方程 ，在这里我们可以看出我们的思路其实还是比较清晰的，针对任意的模数 m，我们有算术基本定理将其分解成各个素数之积，于是我们把问题归结到模数为 ,而我们想要得到的一个好的结果就是可以找到模数为 与 单个素数之间的关系，或者递推关系最好， 因为单素数这种情况最为简单 。于是我们先来考虑 对模“降次” 。首先显然该方程的解也必然是 的解，设c为后者的解，则前者的解必定在 中。将其带入原方程，经过整理后有式子 ，其中 即为 的导函数为 。注意去除含有 的项（被 整除），整理后得到 ，进而有式子（3）。于是我们来考察较为简单的一次同余方程式（3），易得当 时，y 有 唯一解 。否则当 ，同时 （等价 ）时恒成立,这时候（3）式子的解数为 p,即 ,这个时候再带入 即可得到 的解，依次迭代上去即可得到模 的解，否则当 ，同时 (等价 ) 时无解。这样就有了如公式（4）的方程的解的网状关系图,分别对应了上面三种情况，特别地当 无解时，所有 的解相同。

现在我们的问题被转化成了方程 ，研究的方向和一般多项式方程类似，是关于方程解的个数和多项式格式。先假设方程已经做了同余简化，但还未做等价简化，使用多项式除法和归纳法可以有以下 拉格朗日定理 ：若方程有 m 个不同的解 ，则必定有唯一表达式（5），其中g(x)的首项为 ， 的次数低于 m。该定理说明了 n 次同余方程的解的个数不可能大于 n，反之若大于 n，则必恒为 0。

拉格朗日定理给出了多项式同余方程与根有关的格式，值得注意的是，该格式与原多项式是同余，也就是它的本来面貌，这点很重要。该定理还有其它有趣的应用，比如由欧拉定理知 有 p−1 个非零解，则有公式（6），令 即可得到威尔逊定理！如果再比较 和 项的系数，就会有公式（7）（8）。这里需要注意的是（7）中的 与 是关于[p-1/2]对称的，分别对应 和 前面的系数。还有值得一提的是，同余方程同可以有“重根”的概念，有兴趣朋友可以自己研究一下。

这里给出一个（8）式的简单的示意证明，首先因为 p 为素数，我们以 5 来作为示意展示，证明任意素数 p 时，只需将如下证明思路的模式从 5 推广到任意 p 即可。观察（8）并将 乘到和式里面，上式左边便变为了 其中 的定义同以前文章中的定义及 的阶乘除以 , 于是问题就归结到了证明如下式子：
当 p = 5时，易知 ，同理其他式子也是一样，于是我们可观察得到，当 p = 5 时

并且此方法可以推广到任意的素数 p，于是（8）式得证。

接下来我们假定方程做了等价简化，即 的次数小于p且首项系数为 1，看看会有什么性质。首先若有 ，则 有p个根，从而 ，换句话说，次数小于p的首1多项式如果等价则必唯一，即等价和同余是一致的。还有一个问题就是方程的根的个数问题了，当 恰有n个根时，有 ，而 ，这就有 。反之也可以推得 分别有 个根。这就是说 有n个解的充要条件是存在唯一表达式（9）。

关于高次方程更进一步的结论比较少，这里也不作深究，而二项同余方程 放到后面的不定方程讨论会更简单，所以这里也不讨论了。对一些低次方程，可以直接对其研究，我们先从最简单的 一次剩余方程 看起，显然它是否有解与不定方程 是否有解是等价的，故有解的充要条件是 。由同余的性质，原方程等价于方程（10）。故原方程共有 个解，分别为 ，其中 为任一解，也称为 特解 。如果将（10）简记为 ，则 即为原方程的一个特解。

直接求逆是复杂的，一次方程一般用辗转相除法，对于一些特殊格式，还可以动用一切同余的性质简化算法。你可以试解决下面这几个问题：
　 • 证明 的解为 ，其中 。并由此给出系数为 的方程的解法；
　　• ，若 解为 ，则 是 的解。

现在来研究模为素数的二次同余方程 ，通过配方可以有 ，从而方程其实等价于二次二项方程 ，当然这里不去考虑 和 这样的平凡场景。如果方程有解， 称为 的二次剩余，否则叫二次非剩余。为方便描述，这里先引进 勒让德 （Legendre）符号 ，并且勒让德符号或函数有三个取值，当 为 的二次剩余时其值为1，否则为 −1，当 时值为 0。

考虑将 的既约剩余系分为对称的两部分 和 ，显然 ，而当 时， ，所以 。从而上面的式子给出了模 p 的全部二次剩余，故 共有 个二次剩余，又因为模 p 的既约剩余系共有 p-1 个数，所以另外的（p-1）/2 个都是模p的二次非剩余，共有 个二次非剩余，每个二次剩余有两个 互为相反数的根 。

我们自然要问：哪些数是二次剩余？如何判断它是二次剩余？根据欧拉定理有 ，通过移项平方差构造容易证明 。若 为二次剩余，则有 。若不为二次剩余，我们可以将 按照乘积为 配成 对，根据威尔逊定理有 。综合这两个结论就是二次剩余的 欧拉判别法 （公式（11）），当然对于大模数这个方法的计算量还是太大，它仅有理论价值。

对于一些特殊值，可以单独讨论，得出的结论也是可以直接使用的。首先容易证明 只有在 时才是二次剩余，并且由 威尔逊 定理知 是它的解。而且当 时，显然 同时是或不是二次剩余，呈对称分布。当 时，显然x,−x有且仅有一个二次剩余，从上面的欧拉判别式即可得到此结论。这些结构都是很有用的。接下来我们可以来看看如下几个小练习：

• 讨论 有解的充要条件，并给出求解的方法；
　　• 求模 下所有二次剩余的积与和，再求模 p 下所有二次非剩余的积与和。

使用勒让德符号能更清晰地表述二次剩余的性质，如下列的这些性质（可自行验证）：
　　（1）
　　
　　（2） ；
　　
　　（3） ； ；

使用素数分解并结合以上性质，可将求一般 的问题转化为求解 和 上。现在从另一方面讨论 ，在剩余系 中考察 个数 的分布，即在既约剩余系中的前 (p-1)/2 个数乘以二次剩余 d，然后观察那些落在了 0到 p/2 内，那些落在了 p/2 到 p 内。容易证明它们互不相同且互不相反，所以它们是以 为对称轴的两个数之一，右半边的数（设个数为n）需要取相反数才能回到左边。考虑它们的积则容易有 ，这样就有了二次剩余新的判定方法（公式（12）左），特别地时可以推得 是二次剩余的条件是 （可写成公式（12）右）。

对一般的 继续上面的结论，注意到 （[x]是取整操作），对它们求和并在模2 下讨论，可以得到式子（13）。而后者有显著的几何意义，它是一个直角三角形区域内的 整点个数 。考虑 对应的 和 对应的 ，它们正好组成了一个长方形区域，这样就得到了著名的 高斯二次互反律 （公式（14））。

在经过上述的论述之后，你还可以尝试思考下下面这几个问题：
• 求以3为二次剩余的充要条件，并由此对 进行因式分解；
　　• 求证 的奇素因子都有格式 ；并由此证明格式为 的素数有无穷多个；
　　• ，求证 为素数的充要条件是 ；
　　• ，求 （提示：剩余系的遍历）。
　　在使用勒让德符号时要保证模数是素数，这一点很不方便，我们希望这种记法能更通用一点。扩展后的符号称为 雅克比（Jacobi）符号 ： ，其中 。雅克比符号虽然只是一个记法，但形式上却同样有着漂亮的性质，首先有下面几个简单的性质：
　　
（1） ；

（2） ； ；

（3） 。

在得到更多结论之前，需要一个引理：如果 ，则用 归纳法 可以有公式（15）。

利用这个结论就很容易得到雅克比符号的以下性质，这些性质可以使得雅克比公式的使用更加自由，中间无需关心操作数是否为素数，比如 。
（4） ;
（5）

上面我们探讨一般性的同余方程，然后又探讨了较为简洁的二次同余方程的一般形式，在这里我们继续介绍一些特殊的二次同余方程的快速解法。这在利用计算机进行运算时时常会被用到。众所周知，一个素数 只可能是 。在这之中， 对于 为 的素数 ，我们都能够快速地解出二次方程 。

快速解法的要义实质上就是凑！但是如何优雅地凑、在凑的过程中碰到困难如何处理等等还是很有意思的。

首先，我们拿到一个二次方程后自然地会用Legendre符号 判断其是否有解。在这里我们自然要讨论 的二次方程。那么利用 Euler 判别法， 。这就是我们凑方程解的起点所在。

自然地，我们有 ，下面把左侧凑成平方形式： ，从而得到方程的 解为 ： 。但是我们得确保 ，故这个方法仅仅 对于 为 的素数有效！

对于剩余类型的素数，我们可以换一个思路：先对于 做因式分解（这是个常用的思路），得到 。故 或 成立。（注意到这里 为 的素数都能保证 ）

若 成立 ，则开始凑： ，故 ， 解为 。这个做法要求 ，故 仅对于 有效 。

反之， 若 成立 ， 。但是我们遇到了问题：我们该如何凑出一个数，使得其平方在 意义下为 -1 呢？ Wilson 定理 给了我们答案！对于素数 p，

即 。这样一来立马得到 解为 ： ，这个做法同样 仅对于 有效 。这里的Wilson定理使用得太为精妙了，这告诉我们Wilson定理不仅仅为我们提供了一个数为素数的充要条件，其也帮助我们计算出了域 上的 ！

由于上述讨论中我们一直假定p 为奇素数，故我们一直没讨论 模为 时的方程解法 。下面我们讨论方程 ，其中假定 n 为奇数。

当模为 2 或 4 时我们分类讨论容易得到结论。 模为2 时的解存在唯一，而模为4 时要么无解要么有唯一解，解存在的充要条件为 。（这很自然，因为所有奇数的平方都是模 4 余 1 的）

在模为 时，我们先讨论其解的存在性与解的结构。

方程的解存在当且仅当 （这很好理解，因为所有奇数的平方都是模8 余 1 的），且 给定方程特解 后，可以确定其所有四个解 。你可以自己验证下。

具体求解的情形中我们效仿高次同余方程的做法， 利用 的解构造 的解 。 若前一个方程有解 ，则 必定为后一个方程的解 ，这是极其容易验证的。

故对于形如

初等数论四大定理分别是什么?
答：欧拉定理：若n,a为正整数，且n,a互质，(a,n)=1，则：a^φ(n)≡1(mod n)百度百科链接：http://baike.baidu.com/view/48903.htm 剩余定理（孙子定理）：若有一些两两互质的整数m1,m2,…,mn，则对任意的整数a1,a2,…,an，以下联立同余方程组对模m1,m2,…,mn有公解：x≡a1(mod m1)x...

有带余号的方程吗
答：没理解错的话~lz指的是除法的余数~有这种方程的~在数论中就会涉及到~下面给出的连接是初等数论的教程~同余方程：a≡b(mod c)a,b,c均为整数~这个方程的含义为在除数为c的情况下~≡左右两边的a、b两个数的余数相等~~参考资料：http://www.scopen.net/asfroot/scddip/cdsl/ ...

线性回归方程定义和算法是怎么样的?
答：二次剩余 中国剩余定理 谈谈解线性同余方程 因为ACM/ICPC中有些题目是关于数论的，特别是解线性同余方程，所以有必要准备下这方面的知识。关于这部分知识，我先后翻看过很多资料，包括陈景润的《初等数论》、程序设计竞赛例题解、“黑书”和很多网上资料，个人认为讲的最好最透彻的是《算法导论》中的有关...

数学题:求解题过程!
答：根据这个定义，楼主自己思考下看你所提的实际问题是否就对应着前述三个同余式构成的同余方程组？从那三个同余方程组解出x ≡ 23 (mod 105)这不难，但这种一次同余方程组的一般求解确是有点难度的，楼主可以参考任意一本初等数论的教材。下面是解出x ≡ 23 (mod 105)的一个思路：因为x ≡ 2 (...

初等数论高阶同余式求解 6x^70+27x^24+17x^4+20x==0(mod45)
答：需要单独讨论x与模数不互质的情况.对本题,易见x ≡ 0 (mod 5)是6x^70+27x^24+17x^4+20x ≡ 0 (mod 5)的解.当x ≡ 0 (mod 3)时,易见0 ≡ 6x^70+27x^24+17x^4+20x ≡ 2x (mod 9),解得x ≡ 0 (mod 9).以下只讨论x与模数互质的情况.方程变为x²+4 ...

论初等数论与小学数学的关系
答：初等数论是小学教育专业，尤其是理科方向学生的必修专业课程，也是从事小学数学教学的老师的进修课程。其中包括整数的整除性、同余、同余方程、不定方程、不定方程、简单连分数几方面的知识。这些方面的内容在符合了小学数学教师应具有的教学思维外，也有利于学习者积累从事小学数学教育工作必备的能力与知识。有...

初等数论高阶同余式求解 6x^70+27x^24+17x^4+20x==0(mod45)
答：(mod 3).设x = 3y-1, 则在mod 9意义下, x³+4 = (3y-1)³+4 = 27y³-27y²+9y-1+4 ≡ 3.因此x³+4 ≡ 0 (mod 9)无解.综上, 解得x ≡ 0, 1, 4 (mod 5), x ≡ 0 (mod 9).求解该线性同余方程组得x ≡ 0, 9, 36 (mod 45).

数学必读10本经典著作
答：7. 《初等数论》：这本书是米克罗斯·利波夫斯基的经典之作，它涵盖了数论的基本概念和定理，包括质数、同余方程、剩余等。这本书对于理解初等数论和其他数学分支非常重要。8. 《代数几何基础》：这本书是J. E. S. Math英塞尔的经典之作，它深入探讨了代数几何的基本概念和定理，包括多项式方程...

中国剩余定理是在初等代数哪章
答：翻译一下就是：已知一个正整数模3余2，模5余3，模7余2，求这个数是几？写成数学语言就是求解同余方程组 在Part1中我们曾经提到过一下，解这种同余方程组的时候我们往往使用中国剩余定理 已知正整数  两两互质，定义  和 又已知整数  ，那么同余...

2的多少次方末尾六位数为505152
答：2的12421+12500x次幂，其中x=0,1,2...