扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
求解同余式组:x=8(mod 15) x=3(mod10) x=1(mod8)
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
加7以后都能整除15、10、8的最小公倍数是120所以x＝120n－7 n为自然数最小值是113
为您推荐：
其他类似问题
扫描下载二维码基本概念及一次同余式_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
基本概念及一次同余式
&&给出了闵嗣鹤、严士健所编的初等数论一书第四章第一节“基本概念及一次同余式”的教案及部分习题解答。
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩4页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢中国剩余定理解线性同余方程 - he_qiao_2010的专栏 - CSDN博客
中国剩余定理解线性同余方程
加密解密和数论
&&&&&& 先说一个典故：淮安民间传说着一则故事——“韩信点兵”，其次有成语“韩信点兵，多多益善”。韩信带1500名兵士打仗，战死四五百人，站3人一排，多出2人；站5人一排，多出4人；站7人一排，多出6人。韩信马上说出人数：1049。而在一千多年前的《孙子算经》中，也有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以3余2，除以5余3，除以7余2，求这个数。这样的问题，也有人称为“韩信点兵”.它形成了一类问题，也就是初等数论中的解同余式问题。在《孙子算经》中，该书的作者已经给出了该类问题的具体描述以及该类问题的解法。这个发现要比西方早很多年，现在这个问题的推广和解法被称之为中国剩余定理。
&&&&&& 到了明代，到了明代，数学家程大位用诗歌概括了这一算法，他写道：
三人同行七十稀，五树梅花廿一枝;
七子团圆月正半，除百零五便得知。
&&&&&& 这首诗的意思是：用3除所得的余数乘上70，加上用5除所得余数乘以21，再加上用7除所得的余数乘上15，结果大于105就减去105的倍数，这样就知道所求的数了。
&&&&& 下面给出中国剩余定理的一般描述和证明。
&&&&& 中国剩余定理描述：
令&n1,&n2,&…,&nt为两两互素的正整数;
令&N=&n1*n2* …*nt (其中t是一个正整数);
&则以下同余系统：x=&a1&mod&n1,&x=&a2&mod&n2,&…,&x=&at&mod&nt, 中x会在[0,&N-1]内有唯一解。
&&&&& 下面给出中国剩余定理的证明：
首先我们计算N/ni，其中i=1,2,3,...,t。（即N/ni = n1*n2*...*n(i-1)*n(i+1)*...*nt,不包括ni），由n1到nt这t个数两两互素，可以知道N/ni和ni互素，也就是说（N/ni，ni）的最大公约数是1.
这样我们就可以定义：
yi * (N/ni) = 1 mod ni
yi 等于N/ni模ni的逆
这样算出所有的yi我们就可以构造一个x如下：
下面我们来验证这个x是否满足上面同余系统中的要求：
对于同余系统中的第i个方程：
x mod ni&= (N/n1)*y1*a1 + (N/n2)*y2*a2 + ... + (N/ni)*yi*ai + ... + (N/nt)*yt*at& mod ni&&&= (N/ni)*yi*ai mod ni&&& //因为只有(N/ni)这一项中没有ni这一个因子= ai& //由上面的分析知道yi是(N/ni)对于模ni的逆，即yi * (N/ni) = 1 mod ni
所以对于所有i,&1≤&i&≤t,都有：
因此这个x是满足上面同余系统的要求的，也就是说我们找到了这样一个解满足上述同余式组。又由于一个素数对于模i的逆是唯一的，即对于素数a和b至多只能找到一个这样的整数c使得 a * c = 1 mod b。所以yi都只有一个解，都是唯一的，因此x也是唯一的。也就是说这个同余系统有且仅有一个解，而且这个解就是：
下面可以用这种方法来解同余式组：
x = 2 mod 3
x = 3 mod 5
x = 2 mod 7
第一步我们计算N=3×5×7=105,然后计算N/ni：
N/n1=35, N/n2=21, N/n3=15
然后来求所有的yi：
y1 = 35 模 3 的逆 =2 ， y2= 21模 5的逆 =1 ， y3 = 15模7的逆 =1;
得到了这些之后，就直接用上面构造的那个x，就可以得到所求解了：
x = 35×2×2 + 21×1×3 + 15×1×2 mod 105 =& 23
不确定的话再代入检验一下。
我的热门文章}