初等数论基础：一般二次同余方程的化归

本节的目的是指出，一般二次同余方程

的求解问题可归结为形如x2≡a（modm），（a，m）=1的二次二项同余方程的求解问题.不妨设a＞0.首先，对任意x∈Z，

注意到

并记y=2ax+b，d=b2-4ac，则有y2≡d（mod4am）.若x0满足同余方程

则y0=2ax0+b满足同余方程

于是，当（6.1.3）无解时，（6.1.2）无解，从而（6.1.1）也无解.设y1满足（6.1.3）.当y1满足方程（6.1.3）但时，没有与y1对应的数满足方程（6.1.2）；当y1满足方程（6.1.3）且2a|y1-b时，正好是与y1对应的满足方程（6.1.2）的一个数.这样，就可以从（6.1.3）的解中找出（6.1.2）的全部解，进而找出（6.1.1）的全部解.

据上述讨论知，一般二次同余方程（6.1.1）的求解问题可转化为形如

的特殊二次同余方程的求解问题.此时，设是m的标准分解式.则对任意x∈Z，

于是，求解（6.1.4）的问题就又转化为求解形如(www.xing528.com)

的同余方程的问题，其中p是素数，α是正整数.记则同余方程（6.1.5）变为

情形1　　　β≥α.此时，（6.1.6）即x2≡0（modpα）.显然，此方程有解.容易看出，当α=2k时，其解为

当α=2k+1时，其解为

情形2　　0≤β＜α.设x0满足方程（6.1.6）.若β=2k+1，则pk|x0.记x0=pky0并带入（6.1.6），有于是

由α-2k＞α-β≥1知p|y0.记y0=pt0.则即

注意到α-β≥1，这是不可能的.故β是奇数时（6.1.6）无解.设β=2k.则pk|x0.记x0=pky0并带入（6.1.6），有故于是，求解（6.1.5）的问题又转化为求解形如

的二次同余方程的问题，其中p是素数，γ是正整数.

综上所述，求解一般二次同余方程（6.1.1）的问题最终归结为求解形如的特殊的二次二项同余方程的问题.