对“§6.5合数模的二次同余方程”也作了较大改进

这节我们讨论一般合数模的二次二项同余方程，也就是讨论它有解的条件，解的个数以及如何求解等问题.

我们先讨论模是奇质数幂的同余方程（1）的解.

x²≡a（mod p^k），p不能整除a（1）

在§5.3中，将f（x）≡0（mod p^k）写成方程组的形式而得出方程有解的充要条件，这里也将（1）写成方程组的形式来看（1）的解.

将（1）写成如下方程组的形式

f（x）=x²-a≡0 （mod p） ①

f（x）≡0 （mod p²） ②

… … … （2）

f（x）≡0 （mod p^k）(k)

由§5.3的定理1知，（2）有解的充要条件是

f′(x_i)pⁱt_i+f(x_i) ≡0(mod pⁱ⁺¹),i=1,2,…,k-1,

∵f(x)= x²-a=> f′(x)=2x,

∴2x_ipⁱt_i+f(x_i) ≡0(mod pⁱ⁺¹),又f(x_i)≡0(mod pⁱ)=>

2x_it_i+ f(x_i)/pⁱ≡0(mod p). （3）

∵（x_i,p）=1,(2,p)=1=>(2x_i,p)=1,i=1,2……,k-1.

∴（3）有解，且只有两解，即，①,②,…,(k)有解且都只有两解.

因此若①有解，则（2）有解，即（1）有解，且仅有两解.

即然（1）若有解，有且只有两解，那么§6.4的定理2的判别条件就可作为（1）的判别条件.

定理1 （该定理由宋开福给出）设（2t+1）∈S，（2t+

1）^k=2n+1,（2n+1，a）=1，同余方程 x²≡a(mod 2n+1).（4）

（i）若a≡b（mod 2n+1），b=-n/2，（n为偶数）,或b=（n+1）/2，（n为奇数）.

则（4）的解是 x≡±n（mod 2n+1）. （5）

（ii）若a与b关于模2n+1不同余,则（4）有解的充要条件是

m（m+1）≡a-b（mod 2n+1）. （6）

这里m=1,2,…,n-1，假如这个条件成立，那么（4）的解是

x≡±（n-m）（mod 2n+1）. （7）

例1 解方程x²≡11（mod 125）.

解∵2n+1=125=>n=62=>b=-31,

∴x²≡-31（mod 125）是方程x≡±62的基准方程.

在[125k+(11+31)]/m(m+1)=(125k+42)/m(m+1)中，

k_个位=0,2,4,6,8.

则k=0.当k=0时，125k+42=42=6×7=>m=6=>

n-m=62-6=56，于是x≡±56（mod 125）是原方程的解.

下面我们来讨论方程（8）的解

x²≡a（mod 2^k）,（2,a）=1.（8）

同样，我们将（8）写成方程组的形式，即

f（x）=x²-a≡0 （mod 2） ①

f（x）≡0 （mod 2²） ②

… … … （9）

f（x）≡0 （mod 2^k）( k)

由§5.3的定理1和，（9）有解的充要条件是

f′(x_i)pⁱt _i+f(x_i) ≡0(mod pⁱ⁺¹),i=1,2,…k-1，

又f(x)=x²-a=> f′(x_i)=2x_i.

2·2ⁱx_it_i+f（x_i）≡f（x_i）≡x_i²-a≡（mod 2ⁱ⁺¹）.（10）

（i）∵（a,2）=1，∴x=±1是①的解，但1≡-1（mod 2），故这两个值只能作一个解，即取x≡1（mod 2）为①的解.

（ii）当k=2时，则②有解的充要条件是a≡1（mod 2²）.若此，②的解是x≡±1，（mod 2²）.

（iii）当k=3时，则③有解的充要条件是a≡1（mod 2³）.若此，③的解是x≡±1，±5（mod 2³）.

（iv）下面证明，若x≡α（mod 2ⁱ）i=3,4,…,k,是方程

x²≡a（mod 2ⁱ） ( i)

的一个解，则它的所有解是x≡±α，±（α+2^i-1）(mod 2ⁱ).

证 若x≡β（mod 2ⁱ）也是i的解，即β²≡A（mod 2ⁱ）,又

α²≡a（mod 2ⁱ）=>α²-β²≡0（mod 2ⁱ）=>

(α+β)(α-β)≡0(mod 2ⁱ) [(α+β) /2]·[(α-β) /2]

∵α,β为奇数

又(α+β)/2+(α-β)/2=α为奇数，故(α+β)/2，(α-β)/2中一个是奇数，一个是偶数，因此(α+β)/2≡0（mod 2^i-2）=>β≡-α（mod 2^i-1），或(α-β)/2≡0（mod 2^i-2）=>β≡α（mod 2^i-1）.

这即关于模2ⁱ，方程i的解不外是

x≡±α，±（α+2 ^i-1）（mod 2ⁱ）. 证毕.

（v）下面证明，当k≥3时，若x≡±α是方程

x²≡a（mod 2^k）,2不能整除a

的解，则=±α与x=±（α+2^k-1）两组解有且仅有一组是方程x²≡a（mod 2^k+1）的解.

证 设α²-a=2^kt=>(α+2 ^k-1）²-a=（α²-a）+2^kα+2 ^2(k-1)=2^k（t+α+2 ^k-2）,而t与t+α+2 ^k-2的和是奇数，因此这两数一为奇数，一为偶数，即x=±α与x=±（α+2 ^k-1）两组解中有且仅且组是x²≡a（mod 2 ⁱ⁺¹）的解.证毕.

（vi）下面证明x²≡a（mod 2 ⁱ），i=3,4,…,k-1，有解的充要条件是 a≡1（mod 8）.

证 因为x²≡a（mod 8）有解的充要条件是a≡1（mod 8），于是方程(i)有解的充要条件是a≡1（mod 8）.

下面证明它的充分性.

当k=3时，充分性成立，假设当k=i,i=3,4,…,k-1时，充分性成立.由（iv）可知，方程(i)若有解，则i的两组解是

x≡±α，±（α+2^i-1）（mod 2ⁱ）.

由（10）可知，这两组解中，有一组是方程x²-a≡0（mod 2 ⁱ⁺¹）的解.由假设x²-a≡0（mod 2 ⁱ）有解的充分性是a≡1（mod 8），于是当x=±α或x=±（α+2^i-1）是方程x²-a≡0（mod 2 ⁱ⁺¹）的解时，方程x²-a≡0（mod 2 ⁱ⁺¹）有解的充分性也是a≡1（mod 8）.从而定理成立.

综上所述得：

定理2 同余方程x²≡a（mod 2 ^k）,（2,a）=1.（8）

（i）当k=1时，方程（8）有唯一的一个解x≡1（mod 2）.

（ii）当k=2时，方程（8）有解的充要条件是a≡1（mod 4）.若此，则（8）的解是x≡±1（mod 4）.

(iii)当k≥3时，方程（8）有解的充要条件是a≡1（mod 8）,

若此，则（8）有4个解，若x=α是（8）的一个解，则（8）的全部解是

x≡±α，±（α+2^k-1）（mod 2^k）.

若知道（8）的一个解，就可得（8）的全部解，于是下面讨论如何求（8）的一个解.下面介绍的方法如同介绍解奇质数模的二次同余方程一样，先写出模为2^k的基准方程，再利用基准方程来判别（8）是否有解，对有解的写出其解（其观点和方法由宋开福给出）.

同余方程x²≡（2k-1）²≡b（mod 2^k）,（k≥3）显然有

x≡±（2k-1）（mod 2^k）的解.

定义（该定义由宋开福给出）同余方程

x²≡（2k-1）²≡b（mod 2^k），k≥3，

叫做关于模2^k及解x≡±（2k-1）（mod 2^k）的基准方程.

下面讨论如何利用基准方程来判别同余方程（8）的解.

∵x²≡（2k-1）²≡4k²-4k+1≡4k（k-1）+1≡b（mod 2^k），k≥3,有 x=±（2k-1）的解.

（i）若a≡b（mod 2^k），则

x≡±（2k-1）, ±（2k-1+2^k-1）（mod 2^k）为（8）的解.

（ii）若a与b关于模2^k不同余，设x≡（2k-1）+2m（mod 2^k）是方程x²≡a（mod 2^k）的一个解，则

[（2k-1）+2m] ²≡4(m+k)（m+k-1）+1≡a（mod 2^k），

∴b-a≡4k（k-1）-4（m+k）（m+k-1）（mod 2^k）

∵k≥3时，8|（b-a）

（m+k）（m+k-1）≡k（k-1）+(a-b)/4(mod 2^k-2).

于是得出利用基准方程来判别（8）是否有解的问题.

定理3 （该定理由宋开福给出）同余方程

x²≡a (mod 2^k),（2,a）=1，k≥3. （8）

（i）若a≡b (mod 2^k), b≡（2k-1）²（mod 2^k）,则（8）的解是x≡±（2k-1），±（2k-1+2^k-1） （mod 2^k）.

（ii）若a与b关于模2^k不同余时，则（8）有解的充要条件是（m+k）（m+k-1）≡k（k-1）+(a-b)/4（mod 2^k-2）. （11）

假如这个条件成立，那么（8）的解是

x≡±[（2k-1）+2m], ±[（2k-1）+2m+2^k-1]（mod 2^k-2）. （12）

解题的关键是求条件中的m，即在解题中是求

[2^k-2n+k(k-1)+(a-b)/4]/(m+k)(m+k-1)中的整数m.因为（m+k）（m+k-1）是两个连续整数的积，而两个连续整数积的个位数是0，2，6，所以在一般情况，某10之间仍只需检验3个数.

例2 解方程x²≡57（mod 64）.

解 ∵64=2⁶=>k=6=>2k-1=11，∴x²≡11²≡121≡57（mod 64）是x≡±11（mod 64）的基准方程，∴原方程的解是

x≡±11，±（11+2⁵）≡±11，±21（mod 64）。

例3 解方程x²≡145（mod 256）.

解 ∵256=2⁸=>k=8=>2k-1=15.∴x²≡15²≡225（mod 256）是x≡±15（mod 256）的基准方程.而[2^k-2n+k(k-1)+（a-b）/4]/ (m+k)(m+k-1)=(64n+36)/(m+7)(m+8)，n_个位=0，4，6.

则n=6.当n=6时，64n+36=420=20×21=>m+7=20=>m=13=>（2k-1）+2m=15+26=41. ∴原方程的解是

x≡±41，±（41+2⁷）≡±41，±87（mod 256）.

对于一般合数模的二次二项同余方程，由上面的定理及§5.3我们有

定理4 设m=2^α°p₁^α1…p_k^αk，p_i∈奇，（α0=α₀、α1=α₁、…αk=α_k）那么同余方程

x²≡a（mod m），（a,m）=1

有解的充要条件是（a/p_i）=1，i=1,2,…,k.

并且当α₀=2时，a≡1（mod 4），当α₀≥3时，a≡1（mod 8）.假如上面条件成立，则方程有解

（i）当α₀=0，1时，方程有2^k个解.

（ii）当α₀=2时，方程有2^k+1个解.

（iii）当α₀≥3时，方程有2^k+2个解.

到此，我们的第二个问题已完全解决了.

12）、对“§6.5合数模的二次同余方程”也作了较大改进

这节我们讨论一般合数模的二次二项同余方程，也就是讨论它有解的条件，解的个数以及如何求解等问题.

我们先讨论模是奇质数幂的同余方程（1）的解.

x²≡a（mod p^k），p不能整除a（1）

在§5.3中，将f（x）≡0（mod p^k）写成方程组的形式而得出方程有解的充要条件，这里也将（1）写成方程组的形式来看（1）的解.

将（1）写成如下方程组的形式

f（x）=x²-a≡0 （mod p） ①

f（x）≡0 （mod p²） ②

… … … （2）

f（x）≡0 （mod p^k）(k)

由§5.3的定理1知，（2）有解的充要条件是

f′(x_i)pⁱt_i+f(x_i) ≡0(mod pⁱ⁺¹),i=1,2,…,k-1,

∵f(x)= x²-a=> f′(x)=2x,

∴2x_ipⁱt_i+f(x_i) ≡0(mod pⁱ⁺¹),又f(x_i)≡0(mod pⁱ)=>

2x_it_i+ f(x_i)/pⁱ≡0(mod p). （3）

∵（x_i,p）=1,(2,p)=1=>(2x_i,p)=1,i=1,2……,k-1.

∴（3）有解，且只有两解，即，①,②,…,(k)有解且都只有两解.

因此若①有解，则（2）有解，即（1）有解，且仅有两解.

即然（1）若有解，有且只有两解，那么§6.4的定理2的判别条件就可作为（1）的判别条件.

定理1 （该定理由宋开福给出）设（2t+1）∈S，（2t+1）^k=2n+1,（2n+1，a）=1，同余方程

x²≡a(mod 2n+1). （4）

（i）若a≡b（mod 2n+1），b=-n/2，（n为偶数）,或b=（n+1）/2，（n为奇数）.

则（4）的解是 x≡±n（mod 2n+1）. （5）

（ii）若a与b关于模2n+1不同余,则（4）有解的充要条件是

m（m+1）≡a-b（mod 2n+1）.（6）

这里m=1,2,…,n-1，假如这个条件成立，那么（4）的解是

x≡±（n-m）（mod 2n+1）. （7）

例1 解方程x²≡11（mod 125）.

解∵2n+1=125=>n=62=>b=-31,

∴x²≡-31（mod 125）是方程x≡±62的基准方程.

在[125k+(11+31)]/m(m+1)=(125k+42)/m(m+1)中， k_个位=0,2,4,6,8.

则k=0. 当k=0时，125k+42=42=6×7=>m=6=> n-m=62-6=56，

于是x≡±56（mod 125）是原方程的解.

下面我们来讨论方程（8）的解

x²≡a（mod 2^k）,（2,a）=1. （8）

同样，我们将（8）写成方程组的形式，即

f（x）=x²-a≡0 （mod 2） ①

f（x）≡0 （mod 2²） ②

… … … （9）

f（x）≡0 （mod 2^k）( k)

由§5.3的定理1和，（9）有解的充要条件是

f′(x_i)pⁱt _i+f(x_i) ≡0(mod pⁱ⁺¹),i=1,2,…k-1，

又f(x)=x²-a=> f′(x_i)=2x_i.则

2·2ⁱx_it_i+f（x_i）≡f（x_i）≡x_i²-a≡（mod 2ⁱ⁺¹）.（10）

（i）∵（a,2）=1，∴x=±1是①的解，但1≡-1（mod 2），故这两个值只能作一个解，

即取x≡1（mod 2）为①的解.

（ii）当k=2时，则②有解的充要条件是a≡1（mod 2²）.若此，②的解是x≡±1，（mod 2²）.

（iii）当k=3时，则③有解的充要条件是a≡1（mod 2³）.若此，③的解是x≡±1，±5（mod 2³）.

（iv）下面证明，若x≡α（mod 2ⁱ）i=3,4,…,k,是方程

x²≡a（mod 2ⁱ） ( i)

的一个解，则它的所有解是x≡±α，±（α+2^i-1）(mod 2ⁱ).

证 若x≡β（mod 2ⁱ）也是i的解，即β²≡A（mod 2ⁱ）,又

α²≡a（mod 2ⁱ）=>α²-β²≡0（mod 2ⁱ）=>

(α+β)(α-β)≡0(mod 2ⁱ) [(α+β) /2]·[(α-β) /2].

∵α,β为奇数,

又(α+β)/2+(α-β)/2=α为奇数，故(α+β)/2，(α-β)/2中一个是奇数，一个是偶数，

因此(α+β)/2≡0（mod 2^i-2）=>β≡-α（mod 2^i-1），或(α-β)/2≡0（mod 2^i-2）=>β≡α（mod 2^i-1）.

这即关于模2ⁱ，方程i的解不外是

x≡±α，±（α+2 ^i-1）（mod 2ⁱ）. 证毕.

（v）下面证明，当k≥3时，若x≡±α是方程

x²≡a（mod 2^k）,2不能整除a

的解，则=±α与x=±（α+2^k-1）两组解有且仅有一组是方程x²≡a（mod 2^k+1）的解.

证 设α²-a=2^kt=>(α+2 ^k-1）²-a=（α²-a）+2^kα+2 ^2(k-1)=2^k（t+α+2 ^k-2）,而t与t+α+2 ^k-2的和是奇数，因此这两数一为奇数，一为偶数，即x=±α与x=±（α+2 ^k-1）两组解中有且仅且组是x²≡a（mod 2 ⁱ⁺¹）的解. 证毕.

（vi）下面证明x²≡a（mod 2 ⁱ），i=3,4,…,k-1，有解的充要条件是 a≡1（mod 8）.

证 因为x²≡a（mod 8）有解的充要条件是a≡1（mod 8），于是方程(i)有解的充要条件是

a≡1（mod 8）.

下面证明它的充分性.

当k=3时，充分性成立，假设当k=i,i=3,4,…,k-1时，充分性成立.由（iv）可知，方程(i)若有解，则(i ）的两组解是

x≡±α，±（α+2^i-1）（mod 2ⁱ）.

由（10）可知，这两组解中，有一组是方程x²-a≡0（mod 2 ⁱ⁺¹）的解.由假设x²-a≡0（mod 2 ⁱ）有解的充分性是a≡1（mod 8），于是当x=±α或x=±（α+2^i-1）是方程x²-a≡0（mod 2 ⁱ⁺¹）的解时，方程

x²-a≡0（mod 2 ⁱ⁺¹）有解的充分性也是a≡1（mod 8）.从而定理成立.

综上所述得：

定理2 同余方程x²≡a（mod 2 ^k）,（2,a）=1.（8）

（i）当k=1时，方程（8）有唯一的一个解x≡1（mod 2）.

（ii）当k=2时，方程（8）有解的充要条件是a≡1（mod 4）.若此，则（8）的解是x≡±1（mod 4）.

(iii)当k≥3时，方程（8）有解的充要条件是a≡1（mod 8）,

若此，则（8）有4个解，若x=α是（8）的一个解，则（8）的全部解是

x≡±α，±（α+2^k-1）（mod 2^k）.

若知道（8）的一个解，就可得（8）的全部解，于是下面讨论如何求（8）的一个解.下面介绍的方法如同介绍解奇质数模的二次同余方程一样，先写出模为2^k的基准方程，再利用基准方程来判别（8）是否有解，对有解的写出其解（其观点和方法由宋开福给出）.

同余方程x²≡（2k-1）²≡b（mod 2^k）,（k≥3）显然有

x≡±（2k-1）（mod 2^k）的解.

定义（该定义由宋开福给出）同余方程

x²≡（2k-1）²≡b（mod 2^k），k≥3，

叫做关于模2^k及解x≡±（2k-1）（mod 2^k）的基准方程.

下面讨论如何利用基准方程来判别同余方程（8）的解.

∵x²≡（2k-1）²≡4k²-4k+1≡4k（k-1）+1≡b（mod 2^k），k≥3,有 x=±（2k-1）的解.

（i）若a≡b（mod 2^k），则

x≡±（2k-1）, ±（2k-1+2^k-1）（mod 2^k）为（8）的解.

（ii）若a与b关于模2^k不同余，设x≡（2k-1）+2m（mod 2^k）是方程x²≡a（mod 2^k）的一个解，则

[（2k-1）+2m] ²≡4(m+k)（m+k-1）+1≡a（mod 2^k），

∴b-a≡4k（k-1）-4（m+k）（m+k-1）（mod 2^k）.

∵k≥3时，8|（b-a）,

∴（m+k）（m+k-1）≡k（k-1）+(a-b)/4(mod 2^k-2).

于是得出利用基准方程来判别（8）是否有解的问题.

定理3 （该定理由宋开福给出）同余方程

x²≡a (mod 2^k),（2,a）=1，k≥3. （8）

（i）若a≡b (mod 2^k), b≡（2k-1）²（mod 2^k）,则（8）的解是

x≡±（2k-1），±（2k-1+2^k-1）（mod 2^k）.

（ii）若a与b关于模2^k不同余时，则（8）有解的充要条件是

（m+k）（m+k-1）≡k（k-1）+(a-b)/4（mod 2^k-2）. （11）

假如这个条件成立，那么（8）的解是

x≡±[（2k-1）+2m], ±[（2k-1）+2m+2^k-1]（mod 2^k-2）. （12）

解题的关键是求条件中的m，即在解题中是求

[2^k-2n+k(k-1)+(a-b)/4]/(m+k)(m+k-1)中的整数m.因为（m+k）（m+k-1）是两个连续整数的积，而两个连续整数积的个位数是0，2，6，所以在一般情况，某10之间仍只需检验3个数.

例2 解方程x²≡57（mod 64）.

解 ∵64=2⁶=>k=6=>2k-1=11，∴x²≡11²≡121≡57（mod 64）是x≡±11（mod 64）的基准方程，

∴原方程的解是 x≡±11，±（11+2⁵）≡±11，±21（mod 64）。

例3 解方程x²≡145（mod 256）.

解 ∵256=2⁸=>k=8=>2k-1=15.∴x²≡15²≡225（mod 256）是x≡±15（mod 256）的基准方程.而

[2^k-2n+k(k-1)+（a-b）/4]/ (m+k)(m+k-1)=(64n+36)/(m+7)(m+8)，n_个位=0，4，6.

则n=6.当n=6时，64n+36=420=20×21=>m+7=20=>m=13=>（2k-1）+2m=15+26=41. ∴原方程的解是

x≡±41，±（41+2⁷）≡±41，±87（mod 256）.

对于一般合数模的二次二项同余方程，由上面的定理及§5.3我们有

定理4 设m=2^α°p₁^α1…p_k^αk，p_i∈奇，（α0=α₀、α1=α₁、…αk=α_k）那么同余方程

x²≡a（mod m），（a,m）=1

有解的充要条件是（a/p_i）=1，i=1,2,…,k.

并且当α₀=2时，a≡1（mod 4），当α₀≥3时，a≡1（mod 8）.假如上面条件成立，则方程有解

（i）当α₀=0，1时，方程有2^k个解.

（ii）当α₀=2时，方程有2^k+1个解.

（iii）当α₀≥3时，方程有2^k+2个解.

到此，我们的第二个问题已完全解决了.