初等数论基础：解合数模二次二项同余方程

本节讨论合数模同余方程x2≡a（modm），（a，m）=1有解的条件及解的个数.先看下面的引理.

引理6.6.1　设p是奇素数，α，a∈Z，α≥2，（a，p）=1.若≡a（modpα-1），则存在tα∈Z使得xα=xα-1+pα-1tα满足即x2≡a（modpα）有解x≡xα（modpα）.此时显然有xα≡xα-1（modp）.

证明　由，（a，p）=1及p是奇素数知（2xα-1，p）=1和于是关于t，y的不定方程有解.设（tα，yα）是其一解.则故记xα=xα-1+pα-1tα.则

命题6.6.2　设p是奇素数，a，α∈Z.则同余方程

有解当且仅当　此时，该同余方程有两个解.

证明　注意到x2≡a（modpα）有解蕴含x2≡a（modp）有解，必要性显然.下证充分性.若　则x2≡a（modp）有两个解，设其两个解为x≡x1，y1（modp）.据引理6.6.1知同余方程（6.6.1）有解

由于x≡x1（modp）和x≡y1（modp）是x2≡a（modp）的不同的解，故（6.6.2）也是（6.6.1）的不同的解.设x≡x0（modpα）是（6.6.1）的解，则≡a（modp）.这说明x≡x0（modp）是x2≡a（modp）的解.由于x2≡a（modp）只有两个解x≡x1，y1（modp），故x0≡x1（modp）或x0≡y1（modp）.不妨设x0≡x1（modp）.由x≡xα（modpα），xα≡x1（modp）和x≡x0（modpα）是（6.6.1）的解知x0≡xα（modp）和于是p|x0-xα，pα|（x0-xα）（x0+xα）.若p|x0+xα，则有p|（x0+xα）+（x0-xα）=2x0.这与p是奇素数及（a，p）=1矛盾.这表明（p，x0+xα）=1，从而（pα，x0+xα）=1.故由pα|（x0-xα）（x0+xα）知pα|x0-xα.这说明x≡x0（modpα）与x≡xα（modpα）是同一解.上述讨论说明，（6.6.2）是（6.6.1）的全部解.　　　证毕.

下面的命题是显然的.

命题6.6.3　设a，α∈Z，α＞0且（2，a）=1.若α=1，则x2≡a（mod2α）恒有1解x≡1（mod2）.若α=2，则x2≡a（mod2α）有解当且仅当a≡1（mod4）.此时，恰有两解x≡±1（mod4）.

命题6.6.4　设a，α∈Z，α≥3且（2，a）=1.则

x2≡a（mod2α）有解当且仅当a≡1（mod8）.

此时，恰有4解.若设其中一解为x≡x0（mod2α），则其全部解为

x≡±x0，±x0+2α-1（mod2α）.

证明　若x2≡a（mod2α）有解，则存在x0∈Z使得，从而由（a，2）=1知x0必为奇数.设x0=2k+1.则

反之，设a≡1（mod8）.下对α用数学归纳法证明x2≡a（mod2α）有解.当α=3时，由a≡1（mod8）知x2≡a（mod23）就是x2≡1（mod23）.显然，x2≡1（mod23）有四个解x≡±1，±1+23-1（mod23）.故当α=3时结论成立.

设方程x2≡a（mod2α-1），α≥4有解x≡m（mod2α-1）.则m2≡a（mod2α-1）.于是是整数.由（2，a）=1知m是奇数，从而（2，m）=1.由定理5.2.1知存在整数n使得

这导致2α-1mn≡a-m2（mod2α）.由于α≥4，从而2α-4-α=α-4≥0.于是

这表明x2≡a（mod2α）有解.由归纳法原理知，对任意α≥3，x2≡a（mod2α）均有解.

设x≡x0（mod2α）是x2≡a（mod2α）的一解，而x≡x1（mod2α）为另一解.则

由（a，2）=1知x0，x1均为奇数.这导致x0-x1，x0+x1皆为偶数，而，一奇一偶（否则其和x0为偶数）.　由2α|（x0-x1）（x0+x1）知(www.xing528.com)

但一奇一偶，故有或于是

这说明满足同余方程x2≡a（mod2α）的整数只能是如下形式的数：

可以证明，这些整数对模2α形成4个剩余类

容易验证，它们的确都是同余方程x2≡a（mod2α）的解.证毕.

综合命题6.6.2，6.6.3和6.6.4，可得本节的主要结果，它对二次二项同余方程x2≡a（modm），（a，m）=1的解的情况作了完整的回答.

定理6.6.5　设a，m∈Z，m＞1且

则同余方程x2≡a（modm），（a，m）=1有解当且仅当同余方程组

有解.此时，下述情形之一成立：

（1）α=0，1；=1，i=1，2，…，k.此时解数为2k.

（2）α=2；=1，i=1，2，…，k.此时解数为2k+1.

（3）α≥3；=1，i=1，2，…，k.此时解数为2k+2.

例6.6.6　判定同余方程x2≡19（mod45）的解数并求其解.

解　注意到

据定理6.6.5知该方程有4个解.事实上，容易看出x2≡19（mod32）的解为

x≡±1（mod9），而x2≡19（mod5）的解为x≡±2（mod5）.故原方程组的解为

x≡1（mod9），x≡2（mod5）或x≡1（mod9），x≡-2（mod5）或

x≡-1（mod9），x≡2（mod5）或x≡-1（mod9），x≡-2（mod5）.

用孙子定理可求得原方程组的解为x≡±8，±17（mod45）.解毕.