【初等数论】同余方程、与二次剩余互反律
同余方程、二次剩余、二次互反律
1、同余方程 剩余类可以看做是一个新的数系，它对加减乘运算是封闭的，所以同余方程对多项式是有意义的。这里我们就来讨论下一元多项式方程（1）的解，当然它的解是一个剩余类集合，最多有 m 个解。
f ( x ) = ∑ k = 0 n a k x k = a n x n + ? + a 1 x + a 0 ≡ 0 ( m o d m ) (1) f(x)=\sum_{k=0}^{n}{a_kx^k}=a^nx^n+\cdots+a_1x+a_0\equiv 0\pmod{m}\tag{1} f(x)=k=0∑n?ak?xk=anxn+?+a1?x+a0?≡0(modm)(1)
在正式解一个同余方程前，可以先进行一些简单的变形，最简单的就是将系数取模。对于两个多项式f ( x ) , g ( x ) f(x), g(x) f(x),g(x)，如果它们的系数是模m同余的，则称 f ( x ) , g ( x ) f(x),g(x) f(x),g(x)是模m同余的。记作 f ( x ) f(x) f(x)
文章图片
g ( x ) ( m o d m ) g(x) \pmod{m} g(x)(modm) 。显然模同余的多项式的解也必然是相同的，一般将化简后多项式的最高次数称为方程的次数。同余方程中也不是完全不能用除法，当 ( a n , m ) = 1 (a_n,m)=1 (an?,m)=1时，多项式乘上 a n ? 1 {a_n^{-1}} an?1? 就可以变成首 1 多项式。
进一步，如果 f ( x ) ≡ g ( x ) ( m o d m ) f(x)\equiv g(x)\pmod {m} f(x)≡g(x)(modm)恒成立，则称 f ( x ) , g ( x ) f(x), g(x) f(x),g(x)是模 m 等价的。比如根据费马小定理， f ( x ) = x p f(x)=x^p f(x)=xp和 g ( x ) = x g(x)=x g(x)=x就是等价的。显然同余的多项式必定是等价的，但等价的多项式却不一定是同余的。例如上面的例子f ( x ) = x p f(x)=x^p f(x)=xp和 g ( x ) = x g(x)=x g(x)=x就是等价的，但很明显能看出来其对应的幂次数签的系数并不同余，故两个式子不同余。使用等价多项式可以对方程进行降次，比如模为p的多项式 f(x) 一定可以通过多项式除法 f ( x ) = g ( x ) ( x p ? x ) + r ( x ) f(x)=g(x)(x^p-x)+r(x) f(x)=g(x)(xp?x)+r(x)降为次数小于p的多项式 r(x)。对于一般的合数 m，其实容易有a m ≡ a m ? φ ( m ) ( m o d m ) a^m\equiv a^{m-\varphi(m)}\pmod{m} am≡am?φ(m)(modm)，则有恒等式 x m ? x m ? φ ( m ) ≡ 0 ( m o d m ) x^m-x^{m-\varphi(m)}\equiv 0\pmod{m} xm?xm?φ(m)≡0(modm)，故任何多项式都等价于某个次数小于 m 的多项式。
在这里我们先从一般的类似（1）式的最复杂的情况的一般同余方程开始讨论，接下来自然是要对模数进行分解，记方程（1）的解的个数为 T ( m , f ) T(m,f) T(m,f)，且 m = m 1 m 2 ? m n m=m_1m_2\cdots m_n m=m1?m2??mn?中 m k m_k mk?两两互素。容易证明解方程（1）的问题可以等价为解方程组（2）的问题，且有 T ( m , f ) = T ( m 1 , f ) T ( m 2 , f ) ? T ( m n , f ) T(m,f)=T(m_1,f)T(m_2,f)\cdots T(m_n,f) T(m,f)=T(m1?,f)T(m2?,f)?T(mn?,f)。
f ( x ) ≡ 0 ( m o d m ) ? { ? f ( x ) ≡ 0 ( m o d m 1 ) ? ? ? ? ? f ( x ) ≡ 0 ( m o d m n ) (2) f(x)\equiv 0\pmod{m}\Leftrightarrow\begin{cases}\:f(x)\equiv 0\pmod{m_1}\\\:\cdots\:\cdots\\\:f(x)\equiv 0\pmod{m_n}\end{cases}\tag{2} f(x)≡0(modm)???????f(x)≡0(modm1?)??f(x)≡0(modmn?)?(2)
将模数进行素数分解，则我们可以把问题集中在解方程f ( x ) ≡ 0 ( m o d p e ) f(x)\equiv 0\pmod{p^e} f(x)≡0(modpe)，在这里我们可以看出我们的思路其实还是比较清晰的，针对任意的模数 m，我们有算术基本定理将其分解成各个素数之积，于是我们把问题归结到模数为p e p^e pe,而我们想要得到的一个好的结果就是可以找到模数为p e p^e pe与p p p 单个素数之间的关系，或者递推关系最好，因为单素数这种情况最为简单。于是我们先来考虑对模“降次”。首先显然该方程的解也必然是 f ( x ) ≡ 0 ( m o d p e ? 1 ) f(x)\equiv 0\pmod{p^{e-1}} f(x)≡0(modpe?1)的解，设c为后者的解，则前者的解必定在 c + p e ? 1 y , ( 0 ? y ? p ? 1 ) c+p^{e-1}y,(0\leqslant y\leqslant p-1) c+pe?1y,(0?y?p?1)中。将其带入原方程，经过整理后有式子f ( c ) + p e ? 1 f ′ ( c ) y + A 2 p 2 ( e ? 1 ) y 2 + ? ? ? + A n p n ( e ? 1 ) y n ≡ 0 ( m o d p e ) f(c) + p^{e-1}f'(c)y+A_2p^{2(e-1)}y^2 + ··· + A_np^{n(e-1)}y^n\equiv 0\pmod{p^e} f(c)+pe?1f′(c)y+A2?p2(e?1)y2+???+An?pn(e?1)yn≡0(modpe)，其中 f ′ ( x ) f'(x) f′(x)即为 f ( x ) f(x) f(x)的导函数为 f ′ ( x ) = n a n x n ? 1 + ( n ? 1 ) a n ? 1 x n ? 2 + ? ? ? + 2 a 2 x + a 1 f'(x)=na_nx^{n-1}+(n-1)a_{n-1}x^{n-2}+···+2a_2x+a_1 f′(x)=nan?xn?1+(n?1)an?1?xn?2+???+2a2?x+a1?。注意去除含有 ( p e ? 1 y ) k , ( k ? 2 ) (p^{e-1}y)^k,(k\geqslant 2) (pe?1y)k,(k?2)的项（被 p e p^e pe整除），整理后得到f ( c ) + f ′ ( c ) p e ? 1 y ≡ 0 ( m o d p e ) f(c)+f'(c)p^{e-1}y\equiv 0\pmod{p^e} f(c)+f′(c)pe?1y≡0(modpe)，进而有式子（3）。于是我们来考察较为简单的一次同余方程式（3），易得当 p ? f ′ ( c ) p\nmid f'(c) p?f′(c)时，y 有唯一解。否则当 p ∣ f ′ ( c ) p\mid f'(c) p∣f′(c)，同时p ∣ f ( c ) p 1 ? r p\mid f(c)p^{1-r} p∣f(c)p1?r（等价f ( c ) ≡ 0 ( m o d p e ) f(c)\equiv 0\pmod{p^e} f(c)≡0(modpe)）时恒成立,这时候（3）式子的解数为 p,即 y ≡ 0 , 1 , ? ? ? , p ? 1 ( m o d p ) y\equiv 0,1,···,p-1 \pmod{p} y≡0,1,???,p?1(modp),这个时候再带入 c + p e ? 1 y c+p^{e-1}y c+pe?1y 即可得到 f ( x ) ≡ 0 ( m o d p 2 ) f(x)\equiv 0\pmod{p^2} f(x)≡0(modp2)的解，依次迭代上去即可得到模p e p^e pe的解，否则当 p ∣ f ′ ( c ) p\mid f'(c) p∣f′(c)，同时p ? f ( c ) p 1 ? r p\nmid f(c)p^{1-r} p?f(c)p1?r(等价 f ( c ) ≡? 0 ( m o d p e ) f(c)\not\equiv 0\pmod{p^e} f(c)?≡0(modpe)) 时无解。这样就有了如公式（4）的方程的解的网状关系图,分别对应了上面三种情况，特别地当 f ′ ( x ) ≡ 0 ( m o d p ) f'(x)\equiv 0\pmod{p} f′(x)≡0(modp)无解时，所有 f ( x ) ≡ 0 ( m o d p e ) f(x)\equiv 0\pmod{p^e} f(x)≡0(modpe)的解相同。
f ′ ( c ) y ≡ ? f ( c ) p 1 ? e ( m o d p ) (3) f'(c)y\equiv -f(c)p^{1-e}\pmod{p}\tag{3} f′(c)y≡?f(c)p1?e(modp)(3)
f ( c ) ≡ 0 ( m o d p ) { ? p ? f ′ ( c ) ? ? f ( c ) ≡ 0 ( m o d p e ) ? p 2 ∣ f ( c ) ? f ( x ) ≡ 0 ( m o d p 2 ) , x = c + p y ? ? ? p 2 ? f ( c ) ? f ( c ) ≡? 0 ( m o d p e ) (4) f(c)\equiv 0\pmod{p}\begin{cases}\:p\nmid f'(c)\,\Rightarrow f(c)\equiv 0\pmod{p^e}\\\:p^2\mid f(c)\Rightarrow f(x)\equiv 0\pmod{p^2},x=c+py\Rightarrow\cdots\\\:p^2\nmid f(c)\Rightarrow f(c)\not\equiv 0\pmod{p^e}\end{cases}\tag{4} f(c)≡0(modp)??????p?f′(c)?f(c)≡0(modpe)p2∣f(c)?f(x)≡0(modp2),x=c+py??p2?f(c)?f(c)?≡0(modpe)?(4)
现在我们的问题被转化成了方程 f ( x ) ≡ 0 ( m o d p ) f(x)\equiv 0\pmod{p} f(x)≡0(modp)，研究的方向和一般多项式方程类似，是关于方程解的个数和多项式格式。先假设方程已经做了同余简化，但还未做等价简化，使用多项式除法和归纳法可以有以下拉格朗日定理：若方程有 m 个不同的解x 1 , x 2 , ? ? , x m x_1,x_2,\cdots,x_m x1?,x2?,?,xm?，则必定有唯一表达式（5），其中g(x)的首项为 a n x n ? m a_nx^{n-m} an?xn?m， r ( x ) r(x) r(x)的次数低于 m。该定理说明了 n 次同余方程的解的个数不可能大于 n，反之若大于 n，则必恒为 0。
f ( x ) = g ( x ) ( x ? x 1 ) ( x ? x 2 ) ? ( x ? x m ) + p r ( x ) ≡ g ( x ) ( x ? x 1 ) ( x ? x 2 ) ? ( x ? x m ) ( m o d p ) (5) f(x)=g(x)(x-x_1)(x-x_2)\cdots(x-x_m)+pr(x)\equiv g(x)(x-x_1)(x-x_2)\cdots(x-x_m)\pmod{p}\tag{5} f(x)=g(x)(x?x1?)(x?x2?)?(x?xm?)+pr(x)≡g(x)(x?x1?)(x?x2?)?(x?xm?)(modp)(5)
拉格朗日定理给出了多项式同余方程与根有关的格式，值得注意的是，该格式与原多项式是同余，也就是它的本来面貌，这点很重要。该定理还有其它有趣的应用，比如由欧拉定理知 x p ? 1 ? 1 ≡ 0 ( m o d p ) x^{p-1}-1\equiv 0\pmod{p} xp?1?1≡0(modp)有 p?1 个非零解，则有公式（6），令 x = 0 x=0 x=0即可得到威尔逊定理！如果再比较 x x x和 x p ? 2 xp?2 xp?2项的系数，就会有公式（7）（8）。这里需要注意的是（7）中的 i i i与 j j j是关于[p-1/2]对称的，分别对应 x x x和 x p ? 2 xp?2 xp?2前面的系数。还有值得一提的是，同余方程同可以有“重根”的概念，有兴趣朋友可以自己研究一下。
x p ? 1 ? 1 ≡ ( x ? 1 ) ( x ? 2 ) ? ( x ? p + 1 ) ( m o d p ) (6) x^{p-1}-1\equiv (x-1)(x-2)\cdots (x-p+1)\pmod{p}\tag{6} xp?1?1≡(x?1)(x?2)?(x?p+1)(modp)(6) ∑ 1 ? i ? j ? p ? 1 i j ≡ 0 ( m o d p ) (7) \sum_{1\leqslant i\leqslant j\leqslant p-1}ij\equiv 0\pmod{p}\tag{7} 1?i?j?p?1∑?ij≡0(modp)(7) ( p ? 1 ) ! ∑ k = 1 p ? 1 1 k ≡ 0 ( m o d p ) (8) \quad (p-1)!\sum_{k=1}^{p-1}{\dfrac{1}{k}}\equiv 0\pmod{p}\tag{8} (p?1)!k=1∑p?1?k1?≡0(modp)(8)
这里给出一个（8）式的简单的示意证明，首先因为 p 为素数，我们以 5 来作为示意展示，证明任意素数 p 时，只需将如下证明思路的模式从 5 推广到任意 p 即可。观察（8）并将( p ? 1 ) ! (p-1)! (p?1)!乘到和式里面，上式左边便变为了∑ M k , 1 ≤ k ≤ p ? 1 \sum M_k, 1 \leq k \leq p-1 ∑Mk?,1≤k≤p?1 其中M i M_i Mi?的定义同以前文章中的定义及p ? 1 p-1 p?1的阶乘除以i i i, 于是问题就归结到了证明如下式子：
∑ k = 1 p ? 1 M k ≡ 0 ( m o d p ) \sum_{k=1}^{p-1}{M_k}\equiv 0\pmod{p} k=1∑p?1?Mk?≡0(modp)当 p = 5时，易知4 × 3 × 2 = ( 5 ? 1 ) ( 5 ? 2 ) ( 5 ? 3 ) ≡ ? 1 × 2 × 3 ( m o d p ) 4\times3\times2=(5-1)(5-2)(5-3) \equiv -1\times2\times3 \pmod{p} 4×3×2=(5?1)(5?2)(5?3)≡?1×2×3(modp)，同理其他式子也是一样，于是我们可观察得到，当 p = 5 时
∑ M k = 4 × 3 × 2 + 4 × 3 × 1 + 4 × 2 × 1 + 3 × 2 × 1 ≡ ? 3 × 2 × 1 + ? 4 × 2 × 1 + 4 × 2 × 1 + 3 × 2 × 1 ≡ 0 ( m o d p ) \sum M_k = 4\times3\times2 + 4\times3\times1 + 4\times2\times1 + 3\times2\times1 \\ \equiv -3\times2\times1 + -4\times2\times1 + 4\times2\times1 + 3\times2\times1 \equiv 0\pmod{p} ∑Mk?=4×3×2+4×3×1+4×2×1+3×2×1≡?3×2×1+?4×2×1+4×2×1+3×2×1≡0(modp)
并且此方法可以推广到任意的素数 p，于是（8）式得证。
接下来我们假定方程做了等价简化，即 f ( x ) f(x) f(x)的次数小于p且首项系数为 1，看看会有什么性质。首先若有 f ( x ) ≡ g ( x ) ( m o d p ) f(x)\equiv g(x)\pmod{p} f(x)≡g(x)(modp)，则 f ( x ) ? g ( x ) f(x)-g(x) f(x)?g(x)有p个根，从而 f ( x ) = g ( x ) f(x)=g(x) f(x)=g(x)，换句话说，次数小于p的首1多项式如果等价则必唯一，即等价和同余是一致的。还有一个问题就是方程的根的个数问题了，当 f ( x ) f(x) f(x)恰有n个根时，有 f ( x ) ≡ ( x ? x 1 ) ? ( x ? x n ) ( m o d p ) f(x)\equiv (x-x_1)\cdots(x-x_n)\pmod{p} f(x)≡(x?x1?)?(x?xn?)(modp)，而 x p ? x = x ( x ? 1 ) ? ( x ? p + 1 ) ( m o d p ) x^p-x=x(x-1)\cdots(x-p+1)\pmod{p} xp?x=x(x?1)?(x?p+1)(modp)，这就有 x p ? x ≡ f ( x ) g ( x ) ( m o d p ) x^p-x\equiv f(x)g(x)\pmod{p} xp?x≡f(x)g(x)(modp)。反之也可以推得 f ( x ) , g ( x ) f(x),g(x) f(x),g(x)分别有 n , p ? n n, p?n n,p?n个根。这就是说 f ( x ) f(x) f(x)有n个解的充要条件是存在唯一表达式（9）。
x p ? x = f ( x ) g ( x ) + p r ( x ) (9) x^p-x=f(x)g(x)+pr(x)\tag{9} xp?x=f(x)g(x)+pr(x)(9)
关于高次方程更进一步的结论比较少，这里也不作深究，而二项同余方程 x n ≡ a ( m o d p ) x^n\equiv a\pmod{p} xn≡a(modp)放到后面的不定方程讨论会更简单，所以这里也不讨论了。对一些低次方程，可以直接对其研究，我们先从最简单的一次剩余方程 a x ≡ b ( m o d m ) ax\equiv b\pmod{m} ax≡b(modm)看起，显然它是否有解与不定方程 a x + m y = b ax+my=b ax+my=b是否有解是等价的，故有解的充要条件是 ( a , m ) ∣ b (a,m)\mid b (a,m)∣b。由同余的性质，原方程等价于方程（10）。故原方程共有 ( a , m ) (a,m) (a,m)个解，分别为 x 0 + m ( a , m ) k , ( k = 0 , ? ? , ( a , m ) ? 1 ) x_0+\dfrac{m}{(a,m)}k,(k=0,\cdots,(a,m)-1) x0?+(a,m)m?k,(k=0,?,(a,m)?1)，其中 x 0 x_0 x0?为任一解，也称为特解。如果将（10）简记为 a 0 x ≡ b 0 ( m o d m 0 ) a_0x\equiv b_0\pmod{m_0} a0?x≡b0?(modm0?)，则 a 0 ? 1 b 0 a_0^{-1}b_0 a0?1?b0?即为原方程的一个特解。
a ( a , m ) x ≡ b ( a , m ) ( m o d m ( a , m ) ) (10) \dfrac{a}{(a,m)}x\equiv \dfrac{b}{(a,m)}\pmod{\dfrac{m}{(a,m)}}\tag{10} (a,m)a?x≡(a,m)b?(mod(a,m)m?)(10)
直接求逆是复杂的，一次方程一般用辗转相除法，对于一些特殊格式，还可以动用一切同余的性质简化算法。你可以试解决下面这几个问题：
? 证明 2 e x ≡ b ( m o d m ) 2^ex\equiv b\pmod{m} 2ex≡b(modm)的解为 ( m + 1 2 ) e b (\dfrac{m+1}{2})^eb (2m+1?)eb，其中( 2 , m ) = 1 (2,m)=1 (2,m)=1。并由此给出系数为 2 i 3 j 2^i3^j 2i3j的方程的解法；
?( a , m ) = 1 (a,m)=1 (a,m)=1，若 a x ≡ 1 ( m o d m ) ax\equiv 1\pmod{m} ax≡1(modm)解为 x 0 x_0 x0?，则 1 ? ( 1 ? a x 0 ) e a \dfrac{1-(1-ax_0)^e}{a} a1?(1?ax0?)e?是 a x ≡ 1 ( m o d m e ) ax\equiv 1\pmod{m^e} ax≡1(modme)的解。
2、二次剩余 现在来研究模为素数的二次同余方程 a x 2 + b x + c ≡ ( m o d p ) ax^2+bx+c\equiv\pmod{p} ax2+bx+c≡(modp)，通过配方可以有 ( 2 a x + b ) 2 ≡ b 2 ? 4 a c ( m o d p ) (2ax+b)^2\equiv b^2-4ac\pmod{p} (2ax+b)2≡b2?4ac(modp)，从而方程其实等价于二次二项方程 x 2 ≡ d ( m o d p ) x^2\equiv d\pmod{p} x2≡d(modp)，当然这里不去考虑 p = 2 p=2 p=2和 p ∣ d p|d p∣d这样的平凡场景。如果方程有解， d d d称为 p p p的二次剩余，否则叫二次非剩余。为方便描述，这里先引进勒让德（Legendre）符号 ( d p ) \left(\dfrac{d}{p}\right) (pd?)，并且勒让德符号或函数有三个取值，当d d d为 p p p的二次剩余时其值为1，否则为 ?1，当p ∣ d p|d p∣d 时值为 0。
考虑将 p p p的既约剩余系分为对称的两部分 ? p ? 1 2 , ? ? , ? 2 , ? 1 -\dfrac{p-1}{2},\cdots,-2,-1 ?2p?1?,?,?2,?1和 1 , 2 , ? ? , p ? 1 2 1,2,\cdots,\dfrac{p-1}{2} 1,2,?,2p?1?，显然( ? x ) 2 = x 2 (-x)^2=x^2 (?x)2=x2，而当 1 ? i < j ? p ? 1 2 1\leqslant i
( d p ) = ± 1 ≡ d p ? 1 2 ( m o d p ) (11) \left(\dfrac{d}{p}\right)=\pm 1\equiv d^{\frac{p-1}{2}}\pmod{p}\tag{11} (pd?)=±1≡d2p?1?(modp)(11)
对于一些特殊值，可以单独讨论，得出的结论也是可以直接使用的。首先容易证明 ? 1 ?1 ?1只有在 p = 4 k + 1 p=4k+1 p=4k+1时才是二次剩余，并且由威尔逊定理知( p ? 1 2 ) ! (\dfrac{p-1}{2})! (2p?1?)! 是它的解。而且当p = 4 k + 1 p=4k+1 p=4k+1时，显然x , ? x x,?x x,?x 同时是或不是二次剩余，呈对称分布。当p = 4 k + 3 p=4k+3 p=4k+3 时，显然x,?x有且仅有一个二次剩余，从上面的欧拉判别式即可得到此结论。这些结构都是很有用的。接下来我们可以来看看如下几个小练习：
? 讨论x 2 + a y 2 ≡ 0 ( m o d p ) , ( x , y ) = 1 x^2+ay^2\equiv 0\pmod{p},(x,y)=1 x2+ay2≡0(modp),(x,y)=1 有解的充要条件，并给出求解的方法；
? 求模p p p 下所有二次剩余的积与和，再求模 p 下所有二次非剩余的积与和。
使用勒让德符号能更清晰地表述二次剩余的性质，如下列的这些性质（可自行验证）：
（1） ( d + k p p ) = ( d p ) \left(\dfrac{d+kp}{p}\right)=\left(\dfrac{d}{p}\right) (pd+kp?)=(pd?)
（2） ( d 1 d 2 p ) = ( d 1 p ) ( d 1 p ) \left(\dfrac{d_1d_2}{p}\right)=\left(\dfrac{d_1}{p}\right)\left(\dfrac{d_1}{p}\right) (pd1?d2??)=(pd1??)(pd1??)；
（3） ( d 2 p ) = 1 \left(\dfrac{d^2}{p}\right)=1 (pd2?)=1； ( 1 p ) = 1 \left(\dfrac{1}{p}\right)=1 (p1?)=1； ( ? 1 p ) = ( ? 1 ) p ? 1 2 \left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}} (p?1?)=(?1)2p?1?
使用素数分解并结合以上性质，可将求一般( d p ) \left(\dfrac{d}{p}\right) (pd?) 的问题转化为求解 ( 2 p ) \left(\dfrac{2}{p}\right) (p2?)和( q p ) \left(\dfrac{q}{p}\right) (pq?) 上。现在从另一方面讨论d p ? 1 2 d^{\frac{p-1}{2}} d2p?1?，在剩余系1 , 2 , ? ? , p ? 1 1,2,\cdots,p-1 1,2,?,p?1 中考察p ? 1 2 \dfrac{p-1}{2} 2p?1? 个数d , 2 d , ? ? , p ? 1 2 d d,2d,\cdots,\dfrac{p-1}{2}d d,2d,?,2p?1?d 的分布，即在既约剩余系中的前 (p-1)/2 个数乘以二次剩余 d，然后观察那些落在了 0到 p/2 内，那些落在了 p/2 到 p 内。容易证明它们互不相同且互不相反，所以它们是以p 2 \dfrac{p}{2} 2p? 为对称轴的两个数之一，右半边的数（设个数为n）需要取相反数才能回到左边。考虑它们的积则容易有d p ? 1 2 ≡ ( ? 1 ) n ( m o d p ) d^{\frac{p-1}{2}}\equiv (-1)^n\pmod{p} d2p?1?≡(?1)n(modp)，这样就有了二次剩余新的判定方法（公式（12）左），特别地时可以推得d = 2 d=2 d=2 是二次剩余的条件是 p = 8 k ± 1 p=8k±1 p=8k±1（可写成公式（12）右）。
( d p ) = ( ? 1 ) n , ( 2 p ) = ( ? 1 ) p 2 ? 1 8 (12) \left(\dfrac{d}{p}\right)=(-1)^n,\quad \left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}\tag{12} (pd?)=(?1)n,(p2?)=(?1)8p2?1?(12)
对一般的d d d 继续上面的结论，注意到d k = p [ d k p ] + r k dk=p[\dfrac{dk}{p}]+r_k dk=p[pdk?]+rk?（[x]是取整操作），对它们求和并在模2 下讨论，可以得到式子（13）。而后者有显著的几何意义，它是一个直角三角形区域内的整点个数。考虑( q p ) \left(\dfrac{q}{p}\right) (pq?) 对应的 △ O A B \triangle{OAB} △OAB和 ( p q ) \left(\dfrac{p}{q}\right) (qp?)对应的 △ O A C \triangle{OAC} △OAC，它们正好组成了一个长方形区域，这样就得到了著名的高斯二次互反律（公式（14））。
n ≡ ∑ k = 1 p ? 1 2 [ d k p ] ( m o d 2 ) (13) n\equiv\sum_{k=1}^{\frac{p-1}{2}}{\left[\dfrac{dk}{p}\right]}\pmod{2}\tag{13} n≡k=1∑2p?1??[pdk?](mod2)(13) ( q p ) ( p q ) = ( ? 1 ) ( p ? 1 ) ( q ? 1 ) 4 (14) \left(\dfrac{q}{p}\right)\left(\dfrac{p}{q}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\tag{14} (pq?)(qp?)=(?1)4(p?1)(q?1)?(14)
文章图片
有了这个公式，就可以将( q p ) \left(\dfrac{q}{p}\right) (pq?) 不断转化为更小模数的判定式，从而最终解决了任意 ( d p ) \left(\dfrac{d}{p}\right) (pd?) 的求解。如果上述证明过程，你感觉还有些不太清楚的话，你还可以参考这里：如何简洁地证明二次互反律？
在经过上述的论述之后，你还可以尝试思考下下面这几个问题：
? 求以3为二次剩余的充要条件，并由此对10 0 2 ? 3 100^2-3 1002?3 进行因式分解；
? 求证x 4 + 1 x^4+1 x4+1 的奇素因子都有格式8 k + 1 8k+1 8k+1；并由此证明格式为8 k + 1 8k+1 8k+1的素数有无穷多个；
?p = 4 k + 3 p=4k+3 p=4k+3，求证 2 p + 1 2p+1 2p+1为素数的充要条件是 2 p ≡ 1 ( m o d 2 p + 1 ) 2^p\equiv 1\pmod{2p+1} 2p≡1(mod2p+1)；
?p ? a p\nmid a p?a，求∑ x = 1 p ( x 2 + a x p ) \sum\limits_{x=1}^{p}{\left(\dfrac{x^2+ax}{p}\right)} x=1∑p?(px2+ax?)（提示：剩余系的遍历）。
在使用勒让德符号时要保证模数是素数，这一点很不方便，我们希望这种记法能更通用一点。扩展后的符号称为雅克比（Jacobi）符号： ( d P ) = ∏ k = 1 n ( d p k ) \left(\dfrac{d}{P}\right)=\prod\limits_{k=1}^n{\left(\dfrac{d}{p_k}\right)} (Pd?)=k=1∏n?(pk?d?)，其中 P = p 1 p 2 ? p n P=p_1p_2\cdots p_n P=p1?p2??pn?。雅克比符号虽然只是一个记法，但形式上却同样有着漂亮的性质，首先有下面几个简单的性质：
（1） ( d + k P P ) = ( d P ) \left(\dfrac{d+kP}{P}\right)=\left(\dfrac{d}{P}\right) (Pd+kP?)=(Pd?) ；
（2） ( d 1 d 2 P ) = ( d 1 P ) ( d 1 P ) \left(\dfrac{d_1d_2}{P}\right)=\left(\dfrac{d_1}{P}\right)\left(\dfrac{d_1}{P}\right) (Pd1?d2??)=(Pd1??)(Pd1??)； ( d P 1 P 2 ) = ( d P 1 ) ( d P 2 ) \left(\dfrac{d}{P_1P_2}\right)=\left(\dfrac{d}{P_1}\right)\left(\dfrac{d}{P_2}\right) (P1?P2?d?)=(P1?d?)(P2?d?)；
（3） ( d 2 P ) = ( d P 2 ) = 1 \left(\dfrac{d^2}{P}\right)=\left(\dfrac{d}{P^2}\right)=1 (Pd2?)=(P2d?)=1。
在得到更多结论之前，需要一个引理：如果 a = ∏ a k , a k ≡ 1 ( m o d m ) , ( k = 1 , 2 , ? ? , n ) a=\prod a_k,a_k\equiv 1\pmod{m},(k=1,2,\cdots,n) a=∏ak?,ak?≡1(modm),(k=1,2,?,n)，则用归纳法可以有公式（15）。
a ? 1 m ≡ ∑ k = 1 n a k ? 1 m ( m o d m ) (15) \dfrac{a-1}{m}\equiv\sum_{k=1}^n{\dfrac{a_k-1}{m}}\pmod{m}\tag{15} ma?1?≡k=1∑n?mak??1?(modm)(15)
利用这个结论就很容易得到雅克比符号的以下性质，这些性质可以使得雅克比公式的使用更加自由，中间无需关心操作数是否为素数，比如( 105 317 ) = ( 2 105 ) = 1 \left(\dfrac{105}{317}\right)=\left(\dfrac{2}{105}\right)=1 (317105?)=(1052?)=1。
（4）( ? 1 P ) = ( ? 1 ) P ? 1 2 \left(\dfrac{-1}{P}\right)=(-1)^{\frac{P-1}{2}} (P?1?)=(?1)2P?1?;
( 2 P ) = ( ? 1 ) P 2 ? 1 8 \left(\dfrac{2}{P}\right)=(-1)^{\frac{P^2-1}{8}} (P2?)=(?1)8P2?1?
（5） ( Q P ) ( P Q ) = ( ? 1 ) ( P ? 1 ) ( Q ? 1 ) 4 \left(\dfrac{Q}{P}\right)\left(\dfrac{P}{Q}\right)=(-1)^{\frac{(P-1)(Q-1)}{4}} (PQ?)(QP?)=(?1)4(P?1)(Q?1)?
3、特殊二次方程的快速解法 上面我们探讨一般性的同余方程，然后又探讨了较为简洁的二次同余方程的一般形式，在这里我们继续介绍一些特殊的二次同余方程的快速解法。这在利用计算机进行运算时时常会被用到。众所周知，一个素数m o d8 mod \ 8 mod 8 只可能是1 , 3 , 5 , 7 1,3,5,7 1,3,5,7。在这之中，对于 m o d8 mod \ 8 mod 8为 3 , 5 , 7 3, 5, 7 3,5,7的素数 ，我们都能够快速地解出二次方程 x 2 ≡ n ( m o d p ) x^2 \equiv n \pmod{p} x2≡n(modp)。
快速解法的要义实质上就是凑！但是如何优雅地凑、在凑的过程中碰到困难如何处理等等还是很有意思的。
首先，我们拿到一个二次方程后自然地会用Legendre符号 ( n p ) \left(\dfrac{n}{p}\right) (pn?) 判断其是否有解。在这里我们自然要讨论( d p ) = 1 \left(\dfrac{d}{p}\right) = 1 (pd?)=1的二次方程。那么利用 Euler 判别法， n p ? 1 2 ≡ 1 ( m o d p ) n^{\frac{p-1}{2}}\equiv 1\pmod{p} n2p?1?≡1(modp)。这就是我们凑方程解的起点所在。
自然地，我们有 n p + 1 2 ≡ n ( m o d p ) n^{\frac{p+1}{2}}\equiv n\pmod{p} n2p+1?≡n(modp)，下面把左侧凑成平方形式： ( n p + 1 4 ) 2 ≡ n ( m o d p ) (n^{\frac{p+1}{4}})^2 \equiv n\pmod{p} (n4p+1?)2≡n(modp) ，从而得到方程的解为：x ≡ ± n p + 1 4 ( m o d p ) x \equiv \pm n^{\frac{p+1}{4}}\pmod{p} x≡±n4p+1?(modp) 。但是我们得确保p + 1 4 ∈ Z \frac{p+1}{4} \in Z 4p+1?∈Z ，故这个方法仅仅对于m o d8 mod \ 8 mod 8为 3 , 7 3, 7 3,7的素数有效！
对于剩余类型的素数，我们可以换一个思路：先对于 n p + 1 2 ≡ 1 ( m o d p ) n^{\frac{p+1}{2}}\equiv 1\pmod{p} n2p+1?≡1(modp) 做因式分解（这是个常用的思路），得到 p ∣( n p ? 1 4 + 1 ) ( n p ? 1 4 ? 1 ) p | \ (n^{\frac{p-1}{4}} +1)(n^{\frac{p-1}{4}} -1) p∣ (n4p?1?+1)(n4p?1??1) 。故n p ? 1 4 ≡ 1 ( m o d p ) n^{\frac{p-1}{4}} \equiv 1\pmod{p} n4p?1?≡1(modp) 或n p ? 1 4 ≡ ? 1 ( m o d p ) n^{\frac{p-1}{4}} \equiv -1\pmod{p} n4p?1?≡?1(modp) 成立。（注意到这里m o d8 mod \ 8 mod 8为1 , 5 \ 1, 51,5 的素数都能保证p ? 1 4 ∈ Z \frac{p-1}{4} \in Z 4p?1?∈Z ）
若n p ? 1 4 ≡ 1 ( m o d p ) n^{\frac{p-1}{4}} \equiv 1\pmod{p} n4p?1?≡1(modp)成立，则开始凑： n p + 3 4 ≡ n ( m o d p ) n^{\frac{p+3}{4}} \equiv n \pmod{p} n4p+3?≡n(modp)，故 ( n p + 3 8 ) 2 ≡ n ( m o d p ) (n^{\frac{p+3}{8}})^2 \equiv n\pmod{p} (n8p+3?)2≡n(modp) ，解为x ≡ ± n p + 3 8 x \equiv \pm n^{\frac{p+3}{8}} x≡±n8p+3?。这个做法要求p + 3 8 ∈ Z \frac{p+3}{8} \in Z 8p+3?∈Z ，故仅对于 p ≡ 5 ( m o d 8 ) p \equiv 5 \pmod{8} p≡5(mod8)有效。
反之，若 n p ? 1 4 ≡ ? 1 ( m o d p ) n^{\frac{p-1}{4}} \equiv -1\pmod{p} n4p?1?≡?1(modp)成立，( n p + 3 8 ) 2 ≡ ? n ( m o d p ) (n^{\frac{p+3}{8}})^2 \equiv -n \pmod{p} (n8p+3?)2≡?n(modp)。但是我们遇到了问题：我们该如何凑出一个数，使得其平方在m o d p mod p modp 意义下为 -1 呢？Wilson 定理给了我们答案！对于素数 p， ( p ? 1 ) ! ≡ 1 × 2 ? ? ? × ( p ? 1 ) ≡ 1 × 2 × ? ? ? × p ? 1 2 × ( p ? p + 1 2 ) × ? ? ? × [ p ? ( p ? 1 ) ] ≡ ? 1 ( m o d p ) (p-1)! \equiv 1\times2···\times(p-1) \equiv 1\times2\times ···\times\frac{p-1}{2}\times(p-\frac{p+1}{2})\times···\times[p-(p-1)] \equiv -1 \pmod{p} (p?1)!≡1×2???×(p?1)≡1×2×???×2p?1?×(p?2p+1?)×???×[p?(p?1)]≡?1(modp)
即[ ( p ? 1 2 ) ! ] 2 ≡ ? 1 ( m o d p ) [(\frac{p-1}{2})!]^2 \equiv -1 \pmod{p} [(2p?1?)!]2≡?1(modp) 。这样一来立马得到解为：x ≡ ± ( p ? 1 2 ) ! n p + 3 8 ( m o d p ) x \equiv \pm(\frac{p-1}{2})!n^{\frac{p+3}{8}} \pmod{p} x≡±(2p?1?)!n8p+3?(modp)，这个做法同样仅对于p ≡ 5 ( m o d 8 ) p \equiv 5 \pmod{8} p≡5(mod8)有效。这里的Wilson定理使用得太为精妙了，这告诉我们Wilson定理不仅仅为我们提供了一个数为素数的充要条件，其也帮助我们计算出了域 Z p Z_p Zp? 上的? 1 \sqrt{-1} ?1 ?！
由于上述讨论中我们一直假定p 为奇素数，故我们一直没讨论模为2 a 2^a 2a 时的方程解法。下面我们讨论方程 x 2 ≡ n ( m o d 2 a ) x^2 \equiv n \pmod{2^a} x2≡n(mod2a)，其中假定 n 为奇数。
当模为 2 或 4 时我们分类讨论容易得到结论。模为2 时的解存在唯一，而模为4 时要么无解要么有唯一解，解存在的充要条件为n ≡ 1 ( m o d 4 ) n \equiv 1\pmod{4} n≡1(mod4) 。（这很自然，因为所有奇数的平方都是模 4 余 1 的）
在模为 2 a( a ≥ 3 ) 2^a \ (a\geq 3) 2a (a≥3)时，我们先讨论其解的存在性与解的结构。
方程的解存在当且仅当n ≡ 1 ( m o d 8 ) n \equiv 1 \pmod{8} n≡1(mod8)（这很好理解，因为所有奇数的平方都是模8 余 1 的），且给定方程特解 x 0 x_0 x0? 后，可以确定其所有四个解± x 0 , ± x 0 + 2 a ? 1 \pm x_0,\pm x_0+2^{a-1} ±x0?,±x0?+2a?1 。你可以自己验证下。
具体求解的情形中我们效仿高次同余方程的做法，利用x 2 ≡ n ( m o d 2 a ? 1 ) x^2 \equiv n\pmod{2^{a-1}} x2≡n(mod2a?1)的解构造 x 2 ≡ n ( m o d 2 a ) x^2 \equiv n \pmod{2^a} x2≡n(mod2a) 的解。若前一个方程有解 x ≡ x 0 ( m o d 2 a ? 1 ) x \equiv x_0\pmod{2^{a-1}} x≡x0?(mod2a?1)，则 x ≡ x 0 + n ? x 0 2 2 ( m o d 2 a ) x \equiv x_0 + \frac{n-x_0^2}{2} \pmod{2^a} x≡x0?+2n?x02??(mod2a)必定为后一个方程的解，这是极其容易验证的。
故对于形如 x 2 ≡ n ( m o d 2 a ) x^2 \equiv n \pmod{2^a} x2≡n(mod2a) 的方程，我们只需要先考虑 x 2 ≡ n ( m o d 2 3 ) x^2 \equiv n \pmod{2^3} x2≡n(mod23) ，求出其解后即可写出 x 2 ≡ n ( m o d 2 4 ) x^2 \equiv n \pmod{2^4} x2≡n(mod24) 的解，以此类推，最终写出一个x 2 ≡ n ( m o d 2 a ) x^2 \equiv n \pmod{2^a} x2≡n(mod2a) 的解x 1 x_1 x1? 。那么由这类方程解的结构，其全部四个解 ± x 0 , ± x 0 + 2 a ? 1 \pm x_0,\pm x_0+2^{a-1} ±x0?,±x0?+2a?1 我们就都知道了！
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长