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

作者: 溺于恐 | 来源:发表于2019-02-12 07:03 被阅读8次

近世代数理论基础7：同余式·中国剩余定理
近世代数理论基础22：中国剩余定理
产品经理数学课（3）
模p多项式根定理
近世代数理论基础14：同构定理
近世代数理论基础5：算术基本定理
中国剩余定理
中国剩余定理
中国剩余定理
中国剩余定理

同余式·中国剩余定理

同余式

定义：给定整系数多项式 $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}$

近世代数理论基础7：同余式·中国剩余定理
同余式·中国剩余定理同余式定义：给定整系数多项式,则称同余方程为模m的同余式,若,则称它为n次同余式若,满足...
近世代数理论基础22：中国剩余定理
中国剩余定理设R是一个环,是R的理想,对于,若,则称x与y模I同余,记作当和都是环R的理想时,它们的乘积也是R...
产品经理数学课（3）
关键词：剩余，同余定理，数论，hash 参考：杨迎球，中国剩余定理与同余式组，[D]安顺学院数学与计算机科学系，2...
模p多项式根定理
引言对于多项式方程，根据代数基本定理，我们能算出其根的数量。对于同余式，是否也有相似的定理？没错，它就是模p多项...
近世代数理论基础14：同构定理
同构定理同态的基本性质设是同态映射,,令为S在映射f下的像集,对,令为集合的原像引理：设是满同态,则有 1....
近世代数理论基础5：算术基本定理
算术基本定理平凡因数设为任一整数,则与是他的因数,称为平凡因数素数若只有平凡因数,则称p为素数,否则称为合...
中国剩余定理
昨天下午同事给我出了一到题目：一筐鸡蛋，1个1个拿，拿完；2个2个拿，剩余1个；3个3个拿，拿完；4个4个拿，剩...
中国剩余定理
中国剩余定理给出了求解模数两两互质的线性同余方程组的一个特解。设是两两互质的整数，,,是线性同余方程的一个解。对于...
中国剩余定理
用中国剩余定理求解同于式组 / x≡b1 (mod m1)| x≡b2 (mod m2)| x≡b3 (mod m...
中国剩余定理
下表由本人制作，与上表字符含义不同，切勿混淆

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

同余式·中国剩余定理

同余式

中国剩余定理

相关文章