近世代数理论基础7：同余式·中国剩余定理

2019-02-12 本文已影响8人溺于恐

同余式·中国剩余定理

同余式

定义：给定整系数多项式 $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$ ,则称同余方程 $f(x)\equiv 0(mod\; m)$ 为模m的同余式,若 $a_n\not\equiv 0(mod\; m)$ ,则称它为n次同余式

若 $a\in Z$ ,满足 $f(a)\equiv 0(mod\; m)$ ,则 $\forall b\in Z,b\equiv a(mod\;m)$ ,b也满足 $f(b)\equiv 0(mod\; m)$ ,因而称 $x\equiv a(mod\; m)$ 为该同余式的一个同余解

定理：一次同余式 $ax\equiv b(mod\; m)$ , $a\not\equiv 0(mod\; m)$ 有解 $\Leftrightarrow$$(a,m)|b$ ,若有解,则有 $(a,m)$ 个同余解

证明：

$若ax\equiv b(mod\; m)有解$

$设x\equiv x_0(mod\; m)为其一个解$

$则ax_0\equiv b(mod\; m)$

$即\exists k\in Z使ax_0=b+km$

$\because (a,m)|a,(a,m)|m$

$\therefore (a,m)|(ax_0-km)$

$即(a,m)|b$

$若(a,m)|b,设b=(a,m)c$

$则\exists s,t\in Z使得$

$as+mt=(a,m)$

$asc+mtc=b$

$即a(sc)\equiv b(mod\; m)$

$从而x\equiv sc(mod\; m)$

$为同余式ax\equiv b(mod\; m)的解$

$下证(a,m)|b时,同余式ax\equiv b(mod\; m)恰有(a,m)个解$

$设x\equiv x_0(mod\; m)是其一个同余解$

$则\exists k\in Z使得$

$ax_0=b+km$

$若x\equiv \bar{x}(mod;m)为任一同余解$

$则\exists\bar{k}\in Z使得$

$a\bar{x}=b+\bar{k}m$

$\therefore a(\bar{x}-x_0)=(\bar{k}-k)m$

$若令d=(a,m)$

$则有a=a_1d,m=m_1d,(a_1,m_1)=1$

$a_1(\bar{x}-x_0)=(\bar{k}-k)m_1$

$(a_1,m_1)=1\Rightarrow a_1|(\bar{k}-k)$

$令\bar{k}-k=k_1a_1$

$则\bar{x}=x_0+k_1m_1=x_0+k_1{m\over d}$

$即同余式的任一解均可表成x_0+k_1{m\over d}(k\in \Z)$

$显然,\forall k_1\in \Z,x\equiv x_0+k_1{m\over d}(mod\; m)均为同余式$

$ax\equiv b(mod\; m)的解$

$故同余式的解均有上述形式$

$但在模m的意义下$

$仅有d=(a,m)个不同的同余解$

$x_0,x_0+{m\over d},a_0+2{m\over d},\cdots,a_0+[(a,m)-1]{m\over d}\qquad\mathcal{Q.E.D}$

中国剩余定理

定理：设 $m_1,m_2,\cdots,m_r\in N$ ,且两两互素,则同余式组 $\begin{cases}x\equiv b_1(mod;m_1)\\ x\equiv b_2(mod\;m_2)\\ \cdots\\ x\equiv b_r(mod\;m_r)\end{cases}$ ,模 $M=m_1m_2\cdots m_r$ 有唯一同余解

证明：

$令M_i=m_1\cdots m_{i-1}m_{i+1}\cdots m_r=M/m_i$

$\forall i\neq j,(m_i,m_j)=1$

$\therefore \forall 1\le i\le r,有(M_i,m_i)=1$

$\therefore \exists s_i,t_i,使M_is_i+m_it_i=1$

$令N_i=M_is_i$

$下证x\equiv N_1b_1+N_2b_2+\cdots+N_rb_r(mod\;M)为同余式组的解$

$\forall j\neq i,有m_i|M_j$

$\therefore N_j\equiv 0(mod\;m_i)$

$\therefore N_i\equiv 1(mod\;m_i)$

$\therefore \forall 1\le i\le r,有N_1b_1+N_2b_2+\cdots+N_rb_r\equiv b_i(mod\;m_i)$

$即N_1b_1+N_2b_2+\cdots+N_rb_r为同余式组的解$

$再证同余解的唯一性$

$设x_1,x_2均为同余式组的解$

$则x_1\equiv x_2(mod\;m_1),x_1\equiv x_2(mod\;m_2),\cdots,x_1\equiv x_2(mod\;m_r)$

$\because m_1,m_2,\cdots,m_r两两互素$

$\therefore [m_1,m_2,\cdots,m_r]=m_1m_2\cdots m_r=M$

$\therefore x_1\equiv x_2(mod\; M)\qquad\mathcal{Q.E.D}$

上一篇下一篇

猜你喜欢

热点阅读