同余方程与二次剩余

一次同余方程

首先考虑关于xx的最简单的一次同余方程:

axb(modp)ax\equiv b(\mathrm{mod}p)

如果apa\perp p,那么可以偷懒,用欧拉定理aφ(p)1(modp)a^{\varphi(p)}\equiv 1(\mathrm{mod}p)求出aa的逆元。比较普适的办法则是列出不定方程ax+py=bax+py=b,当且仅当(a,p)b(a,p)|b时有解,然后ex_gcd求解ax+py=dax'+py'=d,结果就是

{x=bdxy=bdy\left\{\begin{matrix} x&=&\frac bdx'\\ y&=&\frac bdy' \end{matrix}\right.

更加一般的同余方程

我们的目标当然是能推导出求模任意数意义下的同余方程,但是大部分情况下,模素数意义下都比较好讨论。根据算数基本定理,可以大致分为以下几步求解:

modpmodpamod(pa)\mathrm{mod}p\Rightarrow\mathrm{mod}p^a\Rightarrow\mathrm{mod}\left(\prod p^a\right)

模素数意义下的解

高次同余方程似乎没有特别好用的通解,只能暴力枚举或者巧妙利用题目性质。不过有一个比较好用的定理,可以帮助我们判断是否已经求完所有的解。

拉格朗日定理

类似高斯证明的代数基本定理,拉格朗日定理也给出了同余方程解数量的信息。不同之处在于,代数基本定理是说“任意nn次方程在复数域内有且仅有nn个解”,而拉格朗日定理是说“nn次同余方程在Fp\mathbb{F}_ p内最多nn个解”。

可以归纳证明。在n=1n=1时上面已经讨论过了,最多一个解。假设当n=k1n=k-1时,方程最多k1k-1个解;则当n=kn=k时,假设该方程存在至少k+1k+1个互不相同的解,设前k+1k+1个解为x0,x1,x2,,xkx_0,x_1,x_2,\cdots,x_k。那么这个方程f(x)0(modp)f(x)\equiv0(\mathrm{mod}p)可以因式分解成(xx0)g(x)0(modp)(x-x_0)g(x)\equiv0(\mathrm{mod}p)。现在来说,pp是一个质数,所以x1,x2,,xkx_1,x_2,\cdots,x_k都是g(x)0(modp)g(x)\equiv0(\mathrm{mod}p)的解。可是g(x)g(x)是一个k1k-1次多项式,归纳假设说k1k-1次多项式不可能有kk个互不相同的解,矛盾。故对于任意nNn\in \mathbb N^{* }都有nn次同余方程在模素数意义下最多nn个解。

什么时候真的有nn个解?如果它有nn个解,那么恰好可以把左边的函数写成这样的形式:f(x)=ai(xxi)f(x)=a\prod_i (x-x_i)。考虑这样一个多项式:xpxx^p-x,由费马小定理知它在modp\mathrm{mod}p意义下始终等于00。也就是说,它有pp个解,也可以写成这样的形式:xpxj=0p1(xj)(modp)x^p-x\equiv\prod_{j=0}^{p-1}(x-j)(\mathrm{mod}p)(这似乎给了威尔逊定理的一个证明)。可以发现,f(x)f(x)就是xpxx^p-x的一部分乘上一个常数,而那个非零常数一定有逆元,所以nn次同余方程f(x)0(modp)f(x)\equiv0(\mathrm{mod}p)nn个解当且仅当(xpx)modf(x)=0(x^p-x)\mathrm{mod}f(x)=0(UPD 2018.5.15:已修正。Credit: Owen)。

模素数幂意义下的解

模素数幂意义下的解不比模素数意义下的解好求。但是如果我们求得了模素数意义下的解,是否就能得到模素数的幂意义下的解呢?

不妨考虑一个更具归纳性的问题。当我们得到了一个modpa1\mathrm{mod}p^{a-1}时的解x0x_0,我们会想从这些解里面得到modpa\mathrm{mod}p^a的解x0+kpa1x_0+kp^{a-1}。易知modpa\mathrm{mod}p^a所有的解都是这个形式的。

设同余方程为f(x)0(modpa)f(x)\equiv0(\mathrm{mod}p^a)。对于xnx^n项:

(x0+kpa1)nx0n+(n1)x0n1kpa1x0n+kpa1(nxn1)(modpa)(x_0+kp^{a-1})^n\equiv x_0^n+\binom n 1 x_0^{n-1}kp^{a-1}\equiv x_0^n+kp^{a-1}(nx^{n-1})(\mathrm{mod}p^a)

这看起来怎么这么像求导……那同余方程就变成了:

f(x0+kpa1)f(x0)+kpa1f(x0)0(modpa)f(x_0+kp^{a-1})\equiv f(x_0)+kp^{a-1}f'(x_0)\equiv 0(\mathrm{mod}p^a)

嗯,这是一个一次同余方程。

这也说明,modpa\mathrm{mod}p^a的解数量不会比modpa1\mathrm{mod}p^{a-1}的解的数量多。于是拉格朗日定理也成立。 UPD 2018.5.15:拉格朗日定理不成立。比如:x21(mod8)x^2\equiv1(\mathrm{mod}8)有四个解(Credit: Owen)。

模合数意义下的解

对于一个数A=ipiaiA=\prod_i p_i^{a_i},我们先求出modpiai\mathrm{mod}p_i^{a_i}意义下的解xix_i,然后用小学生都会的中国剩余定理(Chinese Residue Theorem,CRT)合并一下结果。

但是大部分小学生可能只会三五七的CRT,像我这样的垃圾选手连三五七的都不记得了。还是回顾一下吧。

Xxi(modpi)X\equiv x_i(\mathrm{mod}p_i)

X=ixi(1j!=ipjmodpi)j!=ipjX=\sum_{i}x_i\left(\frac 1{\prod_ {j!=i}p_j}\mathrm{mod}p_i\right)\prod_ {j!=i}p_j

这和拉格朗日插值法有着异曲同工之妙:把对别的项的影响消掉,再把对自己的项的影响消掉,最后直接乘上自己需要的系数。

如果模数不两两互质,那就质因数分解,对于每一个质因数求它的最高次项的方程,然后再正常CRT;或者干脆别管什么CRT了,两两用ex_gcd合并。

二次剩余

对一些比较低次的同余方程还是比较能讨论的。尤其是二次剩余,二次剩余相关的理论已经相当完善,只是还没有什么人引进竞赛里面。

使用上面提到的各种方法,只需要求解当pPp\in\mathbb P时的同余方程就可以了。而二次同余方程ax2+bx+c0(modp)ax^2+bx+c\equiv0(\mathrm{mod}p)可以转化为求解(2ax+b)2b24ac(modp)(2ax+b)^2\equiv b^2-4ac( \mathrm{mod}p)

p=2p=2时,讨论二次剩余意义不大。所以之后的讨论,都认为pp是奇素数。

x2n(modp)x^2\equiv n(\mathrm{mod}p)如果有解,那么称nnmodp\mathrm{mod}p意义下的二次剩余(不考虑n=0n=0,否则称为二次非剩余。若我们得到了这个方程的一个解aa,则我们也同时得到了另外一个一定不同的解:pap-a。这是显然的。然后,对于一个质数来说,考虑12,22,,(p1)21^2,2^2,\cdots,(p-1)^2,前一半和后一半恰好两两相同。那前一半数就互异吗?假设存在0<a,b<p120<a,b<\frac{p-1}2使得a2b2a^2\equiv b^2,则(ab)(a+b)0(a-b)(a+b)\equiv 0。而0<a+b<p10<a+b<p-1,所以ab0a-b\equiv0,所以aba\equiv b。即a2b2a^2\equiv b^2当且仅当aba\equiv b对于0<a,b<p120<a,b<\frac{p-1}2成立。故模pp意义下至少有p12\frac{p-1}2个二次剩余。显然这已经是模p$意义下的所有二次剩余了,剩下的都是二次非剩余。

根据欧拉定理np11(modp)n^{p-1}\equiv 1(\mathrm{mod}p),可以推出另一个欧拉定理:

np12{1,xFp,x2n(modp)1,xFp,x2n(modp)n^{\frac{p-1}2}\equiv\left\{\begin{matrix} 1&,&\exists x\in\mathbb F_p,x^2\equiv n(\mathrm{mod}p)\\ -1&,&\nexists x\in\mathbb F_p,x^2\equiv n(\mathrm{mod}p) \end{matrix}\right.

证明:式1因为存在二次剩余,可以根据欧拉定理得出,只需证明式2。由拉格朗日定理,y21(modp)y^2\equiv1(\mathrm{mod}p)最多两个解,在pp为奇素数时这两个解为111-1,故np12n^{\frac{p-1}2}只有这两种取值。设原根为ggngk(mod)n\equiv g^k(\mathrm{mod}),若np121n^{\frac{p-1}2}\equiv1,则gp12k1g^{\frac{p-1}2k}\equiv1,当且仅当p12kmod(p1)=0\frac{p-1}2k\mathrm{mod}(p-1)=0时成立,也就是kk是偶数。如果kk是偶数,那gk2g^{\frac k2}的平方就是nn,与nn为二次非剩余矛盾。

为了让记号更加简洁,引入勒让德记号(Legendre Symbol):

(np)np12(modp)\left(\frac{n}{p}\right)\equiv n^{\frac{p-1}2}(\mathrm{mod}p)

只不过勒让德记号里面的1-1是真·1-1而不是Fp\mathbb F_p下的1-1

欧拉定理已经能够很方便地帮助我们在程序中解决二次剩余的问题了。有一大堆算法,如Tonelli-Shanks算法(CodeChef上看到的)[1],Peralta(miskcoo给的算法?)[2];还有我觉得很好用的的Cipolla随机化算法,这个在维基上就能查到。

Cipolla算法

莫名其妙的求解x2n(modp)x^2\equiv n(\mathrm{mod}p)的主过程:

  1. 用欧拉定理/勒让德记号判断方程是否有解;
  2. 随机出一个数aa使得(a2np)=1\left(\frac{a^2-n}{p}\right)=-1
  3. 扩域,设j2a2n(modp)j^2\equiv a^2-n(\mathrm{mod}p),则x±(a+j)p+12(modp)x\equiv\pm(a+j)^{\frac{p+1}2}(\mathrm{mod}p)

结束!

来给一下证明。

((a+j)p+12)2(a+j)p(a+j)(ap+jp)(a+j)(a+(a2n)p12j)(a+j)(aj)(a+j)a2j2a2(a2n)n\begin{aligned} &\left((a+j)^{\frac{p+1}2}\right)^2\\ \equiv&(a+j)^p(a+j)\\ \equiv&(a^p+j^p)(a+j)\\ \equiv&\left(a+(a^2-n)^{\frac{p-1}2}j\right)(a+j)\\ \equiv&(a-j)(a+j)\\ \equiv&a^2-j^2\\ \equiv&a^2-(a^2-n)\\ \equiv&n \end{aligned}

这样得出来了一个扩域后的解。适当推广一下拉格朗日定理,可以得到新的域的解也最多就两个;而我们知道在Fp\mathbb F_p上就有两个解,所以现在解出来的就是在Fp\mathbb F_p上的。

感觉上面的jj就是实数域中ii一样反直觉的存在。对于任意aFpa\in\mathbb F_p,费马小定理说apa(mod)a^p\equiv a(\mathrm{mod}),可是jpj(mod)j^p\equiv -j(\mathrm{mod})。对于一个二次非剩余,x=jx=j却可能是它的解。我研究了一个下午,也没有发现什么更加直观的理解,所以可能就这样了吧……

二次互反律

如果只是程序求的话,二次剩余到这里就可以结束了。但有的时候我们需要手判是否存在二次剩余[3],有一些更好的办法。

高斯引理:记mmS={knmodpk[1,p12])}S=\{kn\mathrm{mod}p|k\in[1,\frac{p-1}2])\}>p/2>p/2的数(容易发现没有恰好等于p/2p/2的数)的个数,则

nP12(1)m(modp)n^{\frac{P-1}2}\equiv (-1)^m(\mathrm{mod}p)

证明:设a,bSa,b\in Sa<p/2,b>p/2a<p/2,b>p/2。则a+b=pa+b=p当且仅当存在k1+k2=pk_1+k_2=p。但是k1+k2<p/22=pk_1+k_2<p/2* 2=p,所以把所有的bb换成pbp-b不会和aa重复。

那么SS中的元素的乘积就为

np12(p12)!iaijbj(1)m(p12)!n^{\frac{p-1}2}\left(\frac{p-1}2\right)!\equiv\prod_{i}a_i\prod_{j}b_j\equiv (-1)^m\left(\frac{p-1}2\right)!

证毕。

但是这个mm如果要枚举算出来,也不好求。还有一个结论,nn为奇数时,

mk=1p12knp(mod2)m\equiv \sum_{k=1}^{\frac{p-1}2}\left\lfloor\frac{kn}{p}\right\rfloor(\mathrm{mod}2)

证明:类似ex_gcd的推导,把knp\left\lfloor\frac{kn}{p}\right\rfloor换掉。

k=1p12knp=k=1p12kn(knmodp)p=1p(nk=1p12kk=1p12(knmodp))=1p(nk=1p12kiaiibi)=1p(nk=1p12ki=1p12i2ibi+mp)=1p((n1)k=1p12k2ibi)+mm(mod2)\begin{aligned} &\sum_{k=1}^{\frac{p-1}2}\left\lfloor\frac{kn}{p}\right\rfloor\\ =&\sum_{k=1}^{\frac{p-1}2}\frac{kn-(kn\mathrm{mod}p)}{p}\\ =&\frac1p\left(n\sum_{k=1}^{\frac{p-1}2}k-\sum_{k=1}^{\frac{p-1}2}(kn\mathrm{mod}p)\right)\\ =&\frac1p\left(n\sum_{k=1}^{\frac{p-1}2}k-\sum_ia_i-\sum_ib_i\right)\\ =&\frac1p\left(n\sum_{k=1}^{\frac{p-1}2}k-\sum_{i=1}^{\frac{p-1}2}i-2\sum_ib_i+mp\right)\\ =&\frac1p\left((n-1)\sum_{k=1}^{\frac{p-1}2}k-2\sum_ib_i\right)+m\\ \equiv&m(\mathrm{mod}2) \end{aligned}

证毕。

这样的话勒让德符号就可以用类欧几里得求解了,但这样还不如直接高斯定理来得快。不妨考虑会类欧几里得算法的解释:直线y=npxy=\frac npx下整点的个数。这能求吗?

下面可以给出二次互反律:对于两个互异奇素数p,qp,q

(pq)(qp)=(1)p12q12\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}

证明:左边的式子改写成上面那个结论的形式之后,1-1的指数是y=pqxy=\frac pqx下方的整点数量加上y=qpxy=\frac qpx下方的整点数量。而这两条直线上都不会有整点。把他们放到一个图中,其中一个直线方程的x,yx,y对调,发现这个数量和就刚好是p12×q12\frac{p-1}2\times\frac{q-1}2这个矩形内整点数量!那不就刚好是p12q12\frac{p-1}2\cdot\frac{q-1}2吗?证毕。

勒让德符号求解

二次互反律有什么用?不如写成一个更加有用的形式:

(pq)=(1)p12q12(qp),(q<p)\left(\frac pq\right)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}\left(\frac qp\right),(q<p)

这样子倒过来,qq就可以模一下pp了,这样可以搞出和辗转相除的一样的复杂度。真的可以吗?如果模完之后不是质数,可以用勒让德记号的积性分解一下:

(mnp)(mn)p12=mp12np12=(mp)(np)\left(\frac{mn}p\right)\equiv(mn)^\frac{p-1}{2}=m^\frac{p-1}2n^\frac{p-1}2=\left(\frac mp\right)\left(\frac np\right)

然后再递归求解。这样的话复杂度就不一样了,但是应该不会很慢,毕竟是手算,一看算不出来,肯定弃了啊!

万一nn22怎么办?

回归高斯引理咯,因为k[1,p12]k\in\left[1,\frac{p-1}2\right],所以根本不用取模,只要统计2kp\left\lfloor\frac{2k}p\right\rfloor中有多少个数比p/2p/2大,即2kpp+12\frac{2k}p\geq\frac{p+1}2的数量。解一下,得到k[p(p+1)4,p12]k\in\left[\frac{p(p+1)}4,\frac{p-1}2\right],所以就是p12p(p+1)4+1\frac{p-1}2-\left\lceil\frac{p(p+1)}4\right\rceil+1个。可以手动分类讨论一些情况,反正在mod2\mathrm{mod}2意义下做,运算不会很复杂。

后话

从一开始自己脑补Fp\mathbb F_p下开根,到听说二次剩余,到认真学习,再到会写求二次剩余,已经过了大半年了,到最后还是只能粗浅地过了一下。一是之前根本没有zwl的那本好书,二是自己根本没有静下心来好好看,导致学习效率极其低下。

今天又花了一天的时间,边思考边凑完了这篇博客。理解之后,当然感觉easy不少,但是因为学识浅陋,疏忽之处在所难免,还请见谅。

查资料的时候还发现了一篇有趣的求三次同余方程的论文[4],以及分解一般多项式的方法[5]。那些不知道又要什么时候才能动工开始学习呢……

2018.1.17UPD:发现P+12\frac{P+1}2其实是12modP\frac 12\mathrm{mod}P。这样就好记多了。但为什么有这样的联系,我还没想明白。


  1. D. Shanks, Five number-theoretical algorithms, In Proc. Second Manitoba Conf. on Numerical Mathematics, University of Manitoba, Winnipeg, Manitoba, Canada, (1972).

  2. R.C. Peralta, A simple and fast probabilistic algorithm for computing square roots modulo a prime number, IEEE Z?unsactions on Information Theory IT-32 (6), 846-847, (November 1986).

  3. CodeChef FN

  4. C. Padro, G. Saez, Taking cube roots in Zm\mathbb Z_m, Appl. Math. Lett. 15 (2002) 703–708.

  5. H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, Springer-Verlag, Berlin, (1995).

avatar
Kerry Su