theory of numbers

实例

  1. 求同余方程 $4x^2+27x-12\equiv0(mod \ 15)$ 的解。

  2. 求同余方程 $4x^2+27x-7\equiv0(mod \ 15)$ 的解。

  3. 求解同余方程 $4x^2+27-9\equiv0(mod \ 15).$

  4. 对素数 p,同余方程

    $x^p-x\equiv 0(mod \ p) $

    的解数为 p。

  5. 解同余方程 $x^3+5x^2+9\equiv0(mod \ 9)$

    $9=3*3$ ,故有 $x^3+5x^2+9\equiv 0 (mod \ 3)$ ,得到解为 0,1(这一步直接利用完全剩余系即可)。

    解为 0 时,x 可表示为 3y,带入原方程,恒成立,故原方程的解有 0,3,6。

    解为 1 时,x 可表示为 3y+1,带入原方程,化简得到 $30y+6\equiv 0 (mod \ 9)$ ,即 $10y+6\equiv 0 (mod \ 3)$

    即 $y\equiv 1 (mod \ 3)$ ,故 $y=3k+1, x=9k+4, k \in Z$ ,即 $x\equiv 4(mod \ 9)$ 。

    综上所述:x 的解有0,3,4,6。

背景知识

给定正整数 m,及 n 次整数系数多项式

$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\cdots(1)$

求出所有整数 x,使同余式

$f(x)\equiv0(mod \ m)\cdots (2)$

成立。这就是解同余方程式,式子(2)称为模 m 的同余方程

  1. 同余方程的解与解数

    显然同余类的解都一样,所以我们只需要在一个完全剩余系中找全部解,解数记作

    $T(f;m)\le m$

  2. 当 $m \mid (a_n,\cdots,a_0)$ 时,所有整数 x 都是同余方程 (2) 的解,没有讨论的必要。

    当 $m \nmid (a_n,\cdots,a_0)$ 时,必有唯一的 $l,0 \le l \le n$ ,满足

    $m \mid a_j,l<j\le n, m\nmid a_l$

    显见,这时模 m 的同余方程(2)与模 m 的同余方程

    $a_lx^l+\cdots+a_1x+a_0\equiv0(mod \ m)$

    是一样的,即它们的解与解数均相同,我们把 $l$ 称为是 模 m 的同余方程(2)的次数 ,也称为是 多项式 f 关于模 m 的次数,记作 $deg(f;m)$。