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

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

作者: 溺于恐 | 来源:发表于2019-02-12 07:03 被阅读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}$

相关文章

网友评论

近世代数

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

本文链接：https://www.haomeiwen.com/subject/mfuteqtx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

近世代数

关于我们|服务条款|联系我们|近世代数理论基础7：同余式·中国剩余定理|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！