扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
怎么解以下的同余方程问题?（敬求尽可能详细的讲解,因为本人数学学的不多,最好能给每一个步骤做详细的解释.）1.求以下同余方程组的最小四位正整数解.x ≡ 1（mod 3）x ≡ 2（mod 5）x ≡ 3（mod 7）2.求 1234x ≡ 33（mod 2013）的最小正整数解.Tp：解同余方程需要注意哪些地方?Tp II：
作业帮用户
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
求以下同余方程组的最小四位正整数解.x ≡ 1（mod 3）x ≡ 2（mod 5）x ≡ 3（mod 7）& & & &70≡1 & &mod &3.(1)& & & &21≡1 & &mod &5.(2)& & & &15≡1 & mod & 7.(3)& & & &由(1)得 &490≡1 & mod & 3 & 且490≡0 & mod &35& & & &由(2)得 &126≡1 & mod & 5 & 且126≡0 &mod & 21& & & &由(3)得 &120≡1 & mod & 7 & 且120≡0 &mod & 15& & & &故最小的四位数是490×1+126×2+120×3=1102
70是被3除余1且能被5和7整除的最小正整数；那么70的(3m-2)倍都有此性质。
21是被5除余1且能被3和7整除的最小正整数；那么21的(5n-4)倍都有此性质。
15是被7除余1且能被3或5整除的最小正整数；那么15的(7p-6)倍都有此性质。
其中m，n，p都是正整数。
题目要求找到一个最小的四位正整数，使其满足被3除余1，被5除余2，被7除余3，因此只能选择适当的m，n和k，使得[70×(3m-2)×1+[21×(5n-4)]×2+[15×(7p-6)]×3是一个最小的四位正整数。
我选的m=3，n=2，p=2；是不是还有比1102更小的四位数满足此要求，你可以再找一找，我找的不是很细致。
为您推荐：
其他类似问题
扫描下载二维码同余方程X~2≡a（modp~α）的公式解法
同余方程Ｘ~２≡ａ（ｍｏｄｐ~α）的公式解法李鹤年，冯肇华摘要当Ｐ是奇素数，ａ是模ｐ的平方剩余时，同余方程ｘ~２≡ａ（ｍｏｄｐ）的解可以用公式表达。本文利用平方剩余函数ｒ（ｍ）推广了这一结果，把α＞１时同余方程ｘ~２≡ａ（ｍｏｄｐ~α）的解也用公式表示出来。关键词：平方剩余，平方非剩余，正整数的标准分解式，平方剩余函数ｒ（ｍ），欧拉函数（ｍ）。本文讨论用公式表达同余方程的解，其中ｐ是奇素数，ａ是模ｐα的平方剩余，α是正整数。众所周知，同余方程（１）有解的充分必要条件是勒让德符号，并且（１）有解时共有两个解。特别是（１）中α＝１时，它的两个解可以用公式表达出来。具体说是：（ｉ）α＝１，ｐ＝４ｎ＋３时（１）的两个解是时（１）的两个解是ｘ或，ｈ是奇数时，（１）的两个解是，其中ｂ是模ｐ的任意一个平方非剩余，ｔ是使成立的非负整数，０≤ｔ≤２ｎ－１－１。本文将把α＝１时同余方程（１）的解可以用公式表达的这一结果加以推广，使得α＞ｌ时同余方程...&
(本文共4页)
权威出处：
本文中所言的逐步淘汰法是指解同余方程 广.a(modp),(p,a)二l····························································……(l)的一个方法.假定(l)中的p是奇素数,并且(l)有解.1现在流行的逐步淘汰法 众所周知,解同余方程(l)有一个著名而且与德国数学家高斯(Gauss)有关的逐步淘汰法.这个方法是把同余方程(l)化为一个不定方程 护二Py十a,。、y专··································································……(2)来解.它的具体解法是,任取一个与(2)中y的系数P互素的奇素数q,为模,再在模q:的绝对最小完全剩余系里,求出模q.的全部平方非剩余b,,玩,…b.来,其中S二冬(。一1).然后 ’-----一”””’-一”一一,’--一一”‘一””“‘’一,’一‘’一‘’一’‘...&
(本文共6页)
权威出处：
本文讨论用公式表达同余方程 xZ三a(modp‘)(l)的解,其中p是奇素数,a是p‘的平方剩余,a是正整数. 众所周知,同余方程(1)有解的充分与必要条件是勒让得符号(粤)=;,并且(l)有解时共有两 p一’一个解。特别是(l)中a=l时,它的两个解可以用公式表达出来,具体说是,(i)a=l,p二4n+3时(l)的两个解是:,士砂‘,+,,(modp);(11)a=l,p=sm+s时(一)的两个解是、二士2干‘,一‘,.砂‘,+,,(m“p)或二.士:古‘,+,,(m。dp);(551)。一,p二矛h+1,。)3,h是奇数时,(l)的两个解是x,士。:“.a士“+‘,(m“p),其中b是模p的任意一个平方非剩余,:是使b”“.。、二l(modp)成立的非负整数,。《t(2’一‘一l。 本文将把a=1时同余方程(1)的解可以用公式表达的这一结果加以推广,使得al时同余方程(l)的解也可以用公式表达出来. 文[21中对正整数m引进...&
(本文共3页)
权威出处：
本文给出同余方程x’二a(modm),(a,m)-(1)的统一的解法,这里a是任意整数,模m是大于1的整数。粥产一,在流行的解法 众所周知,现在广为流行的同余方程(1)的解法是,先求出模m的标准分解式m二p吞p户二p李 来,然后用判别法断定它有解后转化为解下列同余方程组x’三a(m。dp争),…,x’三a(m。dp李).x’三a (m。dp冲(2)在分别求出了(2、中每一个同余方程的解来以后,把这些解又组成以下各种不同 的同余方程组x三al(,),x主a:(modp护),…,x兰a。(modp:·)(3) 来解,其中a矛二a(modp户),s一l,2,…,n,这里求出来的(3)的唯一解x二e(modm)就是同余方程组 (2)的一个解,也是同余方程(1)的一个解。若同余方程组(2)中每一个同余方程、竺三a(m。dp户)的解 的个数是T,,i=1,2,…n,那末(3)这样的同余方程组就共有T一T,T:…T。组,因此同余方程...&
(本文共5页)
权威出处：
一类同余方程?ａ_ｉｘ_ｉ~２≡ｄ（ｍｏｄｐ）的解数杨照华（华南师范大学数学系广州５１０６３１）摘要本文给出了ｎ项二次同余方程模ｐ的解数。关键词：同余方程；Ｌｅｇｅｎｄｒｅ符号；素域；素数；二次剩余中图法分类号：Ｏ１５６．７对二次不定方程的研究，是一个具有广泛兴趣的问题，（例如，参考［１］，［２］，［３］．）著名的Ｐｅｌｌ方程：ｘ￣２－Ｄｙ￣２＝±１就是这类不定方程的一种特例。本文的目的是讨论这类方程在素域中的解数。为了行文的方便，我们先引进若干记号。ｐ：表示奇素数；；ａ＿１，ａ＿２…ａ＿ｎ；ａ，ｂ，ｃ，ｄ…：表示整数；当时，ａ￣（－１）表示满足的整数；［ａ］：实数ａ的整数部份；：Ｌｅｇｅｎｄｒｅ符号。我们将证明定理设ｐ是奇素数；ａ＿１，ａ＿２，…ａ＿ｎ，ｂ是整数，且．记同余方程模ｐ的解数分别是Ｓ＿ｎ和Ｔ＿ｎ则首先，我们先证明几个引理；引理１设；α，β∈｛－１，１｝．则满足的整数ｚ的个数引理２设ｐ为奇素数，．则证明显然，显然，当...&
(本文共5页)
权威出处：
已知同余方程x,二a(modp.)侈1,(1) 有解,其中p是奇素数,最大公因数(p,a)=1. 众所周知,现在解同余方程(1)的方法是先求出x,二a(modp)的解来,用它的解再求出x’二a(modpZ)的解来,又由此求出x2.a(modp,)的解来,这样一步一步地做下去,最后求出(1)的解来·本文将给出一个新的方法来求同余方程(1)的解,在(l)的模p“是较小的正整数时,可以用这个新方法直接求出(1)的解来,在p“较大时为了计算简单一些起见,先求出同余方程x’“a(modp、)的解来,其中。。,(2x:,p、、)~1,众所周知,这个t:的一次同余方程有唯一的解tZ二x,(modp、、),把t:=x:+p、一、t‘代入x=士(x:+p、tZ)中得到x二士(x:+p、x、+p气t、),即x二士(x:+p、x:)(modp、). x二(xZ+p、x:)(modp、)就是同余方程(3)的解,因为2吸a,,2x2xl三a,(modp、...&
(本文共5页)
权威出处：
扩展阅读：
CNKI手机学问
有学问，才够权威！
xuewen.cnki.net
出版：《中国学术期刊（光盘版）》电子杂志社有限公司
地址：北京清华大学 84-48信箱 大众知识服务
京ICP证040431号&
服务咨询：400-810--9993
订购咨询：400-819-9993
传真：010-一次同余方程的求解技巧_百度文库
您的浏览器Javascript被禁用，需开启后体验完整功能，
享专业文档下载特权
&赠共享文档下载特权
&10W篇文档免费专享
&每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
一次同余方程的求解技巧
&&一次同余方程的求解技巧,经典
阅读已结束，下载本文需要
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩1页未读，
定制HR最喜欢的简历
你可能喜欢扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
如何解同余方程ax ≡ b(Mod M)
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
ax≡b(mod m) a≠0(mod m)有解的充要条件是(a,m)|b且有x≡x0+mk/(a,m) (mod m)k=0,1,2,...,(a,m)-1x0是一个特解
为您推荐：
其他类似问题
扫描下载二维码我的图书馆
因为ACM/ICPC中有些题目是关于数论的，特别是解线性同余方程，所以有必要准备下这方面的知识。关于这部分知识，我先后翻看过很多资料，包括陈景润的《初等数论》、程序设计竞赛例题解、“黑书”和很多网上资料，个人认为讲的最好最透彻的是《算法导论》中的有关章节，看了之后恍然大悟。经过几天的自学，自己觉得基本掌握了其中的“奥妙”。拿出来写成文章。
那么什么是线性同余方程？对于方程：ax≡b(mod&&&m)，a，b，m都是整数，求解x
解题例程：
符号说明：
&&&&&&&&&&&&&&&&& mod表示：取模运算
&&&&&&&&&&&&&&&&& ax≡b(mod&&&m)表示：(ax - b)
mod m = 0，即同余
&&&&&&&&&&&&&&&&& gcd(a,b)表示：a和b的最大公约数
求解ax≡b(mod n)的原理：
对于方程ax≡b(mod n)，存在ax + by =
gcd(a,b)，x，y是整数。而ax≡b(mod
n)的解可以由x，y来堆砌。具体做法，见下面的MLES算法。
第一个问题：求解gcd(a,b)
定理一：gcd(a,b) = gcd(b,a mod b)
实现：古老的欧几里德算法
int Euclid(int a,int b){if(b == 0)&&&&& return
a;else&&&&& return Euclid(b,mod(a,b));}
附：取模运算
int mod(int a,int b){if(a &= 0)&&&&& return a %
b;else&&&&& return a % b +}
第二个问题：求解ax + by = gcd(a,b)
定理二：gcd(b,a mod b) = b * x' + (a mod b) * y'
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& = b * x' + (a - a / b * b) *
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& = a * y' + b * (x' - a / b
*&&&&& y')
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& = a * x + b * y
&&&&&&&&&&&&&&&&& 则：x = y'
&&&&&&&&&&&&&&&&&&&&&&&& y = x' - a / b * y'
triple Extended_Euclid(int a,int b){if(b ==
0){&&&&& result.d =&&&&& result.x = 1;&&&&& result.y =
0;}else{&&&&& triple ee = Extended_Euclid(b,mod(a,b));&&&&&
result.d = ee.d;&&&&& result.x = ee.y;&&&&& result.y = ee.x -
(a/b)*ee.y;}}
附：三元组triple的定义
struct triple{int d,x,y;};
第三个问题：求解ax≡b(mod n)
实现：由x，y堆砌方程的解
int MLES(int a,int b,int n){triple ee =
Extended_Euclid(a,n);if(mod(b,ee.d) == 0)&&&&& return mod((ee.x * (b /
ee.d)),n / ee.d);else&&&&& return
-1;}//返回-1为无解，否则返回的是方程的最小解
说明：ax≡b(mod n)解的个数：
&&&&&&&&&& 如果ee.d 整除 b 则有ee.d个解；
&&&&&&&&&& 如果ee.d 不能整除 b 则无解。
第四个问题：求解a≡bi(mod m[i]),用
中国剩余定理和一次同余方程组的通用解法
今天参加了一家做图形软件的公司的笔试，出了这样一道题：一堆鸡蛋，3个3个数余2，5个5个数余1，7个7个数余6，问这堆鸡蛋最少有多少个？
&&&&作为数学专业出身的我看到这道题当即笑了，因为这是一个很经典的一次同余方程的问题。当然很快就用曾经记得的算法给出了答案101，但我觉得还不过瘾，又因为觉得这类问题对于搞计算机的实在很重要，所以又回忆了一下初等数论的相关理论知识，特此总结一下！
&&&&对于这个问题用数学的语言来描述就是：
&&&&&&&&N = 2(mod 3) = 1(mod 5) = 6(mod 7);
&&&&求解最小N。
&&&&由一首诗可以轻易得出求解算法：
&&&“&三人同行七十稀，五树梅花甘一枝， 七子团圆正半月，除百零五便得知。”
&&&&即解为：N = 2*70+1*21+6*15-105*n.（n为使得N不为负的最大正整数，这里就是1了）
&&&&那么我们是怎么得到这个公式的呢？
&&&&其实早在几千年前中国的一本《孙子算经》就已经提及这个问题的解法了，原文为：
“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？”&&&&&答曰：“二十三”&&&&术曰：“三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。”
&&&&《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但由于题目比较简单，甚至用试猜的方法也能求得，所以尚没有上升到一套完整的计算程序和理论的高度。真正从完整的计算程序和理论上解决这个问题的，是南宋时期的数学家秦九韶。秦九韶在他的《数书九章》中提出了一个数学方法“大衍求一术”（其实就是后来数学王子高斯提出的解同余方程的方法），系统地论述了一次同余式组解法的基本原理和一般程序。
&&&&&秦九韶为什么要把他的这一套计算程序和基本原理称为“大衍求一术”呢？这是因为其计算程序的核心问题是要“求一”。所谓“求一”，通俗他说，就是求“一个数的多少倍除以另一个数，所得的余数为一”。那么为什么要“求一”呢？我们可以从“物不知数”题的几个关键数字70、21、15中找到规律。
&&&&我们可以看出解此题的关键在于如何确定70、21、15这3个数（105 = 3*5*7）。现简述如下：
&&&&归结为一句话就是求3、5、7三个数两两组合相乘的k倍模另外一个数而余1的数&。这样说可能有点抽象，下面具体讲解下大家就会明白了：
&&&&首先对于5、7两个数，即为：
&&&&&&&&&&&&70 = 2*5*7& = 1(mod 3)
&&&&其中k为2，所以很容易求出第一个70，同样的道理可以求出：
&&&&&&&&&&&&21 = 3*7 = 1(mod 5)
&&&&&&&&&&&&15 = 3*5 = 1(mod 7)
&&&&理解了上例解法，我们不难得出著名的中国剩余定理（孙子定理）的一般数学形式了：
&&&&一次同余方程组
&&&&&&&&&&&&&x = a1(mod m1)
&&&&&&&&&&&& x = a2(mod m2)
&&&&&&&&&&&& ...
&&&&&&&&&&&& x = ak(mod mk)
&&&&若m1,m2,......,mk这些数两两互质，且定义miMi =
m1m2......mk以及CiMi
= 1 (mod mi)。则此一次同余方程组的解为：
&&&&&&&&x = a1M1C1 +
......+akMkCk (mod m)。
&&&&所以我们可以很容易的把这个面试题推广为：
&&&&一堆鸡蛋，3个3个数余a1，5个5个数余a2，7个7个数余a3，问这堆鸡蛋最少有多少个？
&&&&甚至推广为：
&&&&一堆鸡蛋，n1个n1个数余a1，n2个n2个数余a2，n3个n3个数余
a3&,.....,
nm个nm个数余am，问这堆鸡蛋最少有多少个？（其中n1,n2,.....,
[转]&[转]&[转]&[转]&
喜欢该文的人也喜欢}