加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

中国剩余定理在数论题中的应用

(2012-06-22 21:13:08)
标签:

数论

整除

连接自然数

中国剩余定理

剩余定理

教育

分类: 杂谈

中国剩余定理在数论题中的应用
例题:
   在200至300之间,有三个连续的自然数a<b<c,3|a、7|b、13|c,即a,b,c分别能被3、7、13整除,问这三个数分别是多少?
分析:
   方法一:先找出200至300之间的能被13整除的数,然后看看比它小1的数能不能被7整除,比它小2的数能不能被3整除(想想为什么要先找能被13整除的?因为能被13整除的少,能被3整除的多)。200至300之间能被13整除的数有:208,221,234,247,260,273,286,299(注:想想怎么快速找出能被13整除的数?需不需要用200去除以13?其实不需要,因为每13个连续自然数里面就有一个能被13整除的数,所以可以先找出一个能被13整除的,然后不断加13和减13就行,比如:一眼看出260能被13整除,260不断加13得到:273,286,299;260不断减13得到:247,234,221,208,这样都找出来了,学数学需要不断动脑筋)然后先看他们减2能不能被3整除:206,219,232,245,258,271,284,297很容易判断:219,258,297能被3整除再最后判断219,258,297加1能不能被7整除,220,259,298中只有259能被7整除所以这三个数是:258,259,260(注:为什么要先检验能不能被3整除而不检验能不能被7整除?因为判断一个数能不能被3整除容易。)

   方法二:方法一比较简单,但是不通用,比如要找出1-1000之间满足条件的数就很困难了。我们可以用中国剩余定理来做(附后)。中国剩余定理解决的是一个数的问题,比如:一个数被3除余1,被4除余2,被5除余4,这个数最小是几?而本题涉及到三个数,怎么办呢?很容易,可以先转化为一个数,我们可以先算出最大的那个自然数,最大的数能被13整除,被7除余1,被3除余2(想想为什么?),那我们的问题就转化为:200-300之间的一个数满足:被13除余0,被7除余1,被3除余2,这个数是几?用中国剩余定理来解就很简单了题中3、7、13三个数两两互质。则〔3,7〕=21;〔3,13〕=39;〔7,13〕=91;〔3,7,13〕=273。为了使21被13除余1,用21×5=105;使39被7除余1,用39×2=78;使91被3除余1,用91×1=91。然后,105×0+78×1+91×2=260,因为,260<273,所以260就是所求的数。所以这三个数分别为:258,259,260

 方法三:假设这三个连续自然数分别为a-2,a-1,aa-2能被3整除,a-1能被7整除,a能被13整除考虑a+13这个数因为a能被13整除,所以a+13能被13整除因为a-1能被7整除,(a+13)-(a-1)=14,所以a+13能被7整除因为a-2能被3整除,(a+13)-(a-2)=15,所以a+13能被3整除这样a+13能同时被3,7,13整除,是他们的公倍数所以a+13=3*7*13=273,a=260所以所求的三个数分别为:258,259,260

 方法四:最大的数能被13整除,假设最大数为13k,那么这三个连续自然数就是13k-2,13k-1,13k那么我们的关键是求出一个k,使得13k-2能被3整除,而且13k-1能被7整除,我们利用整除的性质来做由(13k-1)能被7整除知,14k-(13k-1)=k+1也能被7整除(因为两个能被7整除的差也能被7整除),由(13k-2)能被3整除知,(13k-2)-12k=k-2也能被3整除,(k-2)+3=k+1也能被3整除得出k+1能同时被3和7整除,k+1=3*7=21,k=20所以所求的三个数分别为:258,259,260

 

中国剩余定理
    中国剩余定理是中国古代求解一次同余式组的方法。是数论中一个重要定理。


原文
    中国剩余定理我国古代数学名著《孙子算经》中,记载这样一个问题:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何。”用现在的话来说就是:“有一批物品,三个三个地数余二个,五个五个地数余三个,七个七个地数余二个,问这批物品最少有多少个。”这个问题的解题思路,被称为“孙子问题”“鬼谷算”“隔墙算”“韩信点兵”等、、、等。那么,这个问题怎么解呢?明朝数学家程大位把这一解法编成四句歌诀:三人同行七十(70)稀,五树梅花廿一(21)枝,七子团圆正月半(15),除百零五(105)便得知。
    歌诀中每一句话都是一步解法:第一句指除以3的余数用70去乘;第二句指除以5的余数用21去乘;第三句指除以7的余数用15去乘;第四句指上面乘得的三个积相加的和如超过105,就减去105的倍数,就得到答案了。即:70×2+21×3+15×2-105×2=23

 

算理
  为什么这样解呢?因为70是5和7的公倍数,且除以3余1。21是3和7的公倍数,且除以5余1。15是3和5的公倍数,且除以7余1。(任何一个一次同余式组,只要根据这个规律求出那几个关键数字,那么这个一次同余式组就不难解出了。)把70、21、15这三个数分别乘以它们的余数,再把三个积加起来是233,符合题意,但不是最小,而105又是3、5、7的最小公倍数,去掉105的倍数,剩下的差就是最小的一个答案。

 

解释
  三数为a b c余数分别为 m1 m2 m3,%为求余计算,&&意为“且”
  1、分别找出能被两个数整除,而满足被第三个整除余一的最小的数。
  k1%b==k1%c==0 && k1%a==1;
  k2%a==k2%c==0 && k2%b==1;
  k3%a==k3%b==0 && k3%c==1;
  2、将三个未知数乘对应数字的余数再加起来,减去这三个数的最小公倍数的整数倍即得结果。
  Answer = k1×m1 + k2×m2 + k3×m3 - P×(a×b×c);
  P为满足Answer > 0的最大整数;
  或者 Answer = (k1×m1 + k2×m2 + k3×m3)%(a×b×c) ;


证明
  令T1=k1×m1,T2=k2×m2,T3=k3×m3;
  因为 k1%a==1 ;所以 T1%a==m1;
  对于 a,已知: T2%a==0,T3%a==0,T1%a==m1;
  所以: Answer%a==m1;
  因为:T1%b==0,T3%b==0,T2%b==m2 => Answer%b==m2
  同理:Answer%c==m3;
  又因为 a×b×c能同时整除 a b c,所以Answer ± P×(a×b×c)也是题目的解;
  所以Answer是题目的解,又Answer = Answer % (a×b×c),所以Answer为最小解.

 

推广
  中国剩余定理推广到一般情形:
  设m1,m2,…mk是两两互素的正整数,则对任意b1,b2,…,bk,同余方程组
  x mod m1=b1 mod m1,
  x mod m2=b2 mod m2,
  
  x mod mk=bk mod mk, 其解为: x=(M1’M1b1+M2’M2b2+…+M’kMkbk )mod m
  m=m1m2…mk,
  Mi=m/mi  MiMi’ mod mi=1 显然(Mi,mi)=1
  即Mi’是Mi的逆元或者可用辗转相除法求Mi’.


例1:一个数被3除余1,被4除余2,被5除余4,这个数最小是几?题中3、4、5三个数两两互质。则〔4,5〕=20;〔3,5〕=15;〔3,4〕=12;〔3,4,5〕=60。为了使20被3除余1,用20×2=40;使15被4除余1,用15×3=45;使12被5除余1,用12×3=36。然后,40×1+45×2+36×4=274,因为,274>60,所以,274-60×4=34,就是所求的数。

例2:一个数被3除余2,被7除余4,被8除余5,这个数最小是几?题中3、7、8三个数两两互质。则〔7,8〕=56;〔3,8〕=24;〔3,7〕=21;〔3,7,8〕=168。为了使56被3除余1,用56×2=112;使24被7除余1,用24×5=120。使21被8除余1,用21×5=105;然后,112×2+120×4+105×5=1229,因为,1229>168,所以,1229-168×7=53,就是所求的数。

例3:一个数除以5余4,除以8余3,除以11余2,求满足条件的最小的自然数。题中5、8、11三个数两两互质。则〔8,11〕=88;〔5,11〕=55;〔5,8〕=40;〔5,8,11〕=440。为了使88被5除余1,用88×2=176;使55被8除余1,用55×7=385;使40被11除余1,40×8=320。用然后,176×4+385×3+320×2=2499,因为,2499>440,所以,2499-440×5=299,就是所求的数。

例4:有一个年级的同学,每9人一排多5人,每7人一排多1人,每5人一排多2人,问这个年级至少有多少人?题中9、7、5三个数两两互质。则〔7,5〕=35;〔9,5〕=45;〔9,7〕=63;〔9,7,5〕=315。为了使35被9除余1,用35×8=280;使45被7除余1,用45×5=225;使63被5除余1,用63×2=126。然后,280×5+225×1+126×2=1877,因为,1877>315,所以,1877-315×5=302,就是所求的数。

例5:有一个年级的同学,每9人一排多6人,每7人一排多2人,每5人一排多3人,问这个年级至少有多少人?题中9、7、5三个数两两互质。则〔7,5〕=35;〔9,5〕=45;〔9,7〕=63;〔9,7,5〕=315。为了使35被9除余1,用35×8=280;使45被7除余1,用45×5=225;使63被5除余1,用63×2=126。然后,280×6+225×2+126×3=2508,因为,2508>315,所以,2508-315×7=303,就是所求的数。(例5与例4的除数相同,那么各个余数要乘的“数”也分别相同,所不同的就是最后两步。)

练习:
1、一个数除以7余1,除以8余2,除以9余3,求满足条件的最小的自然数。
2、在10000以内,除以3余2,除以7余3,除以11余4的数有多少个?
3、满足除以5余1,除以7余3,除以8余5的最小自然数。
4、求满足除以6余3,除以8余5,除以9余6的最小自然数。
5、在小于1000的自然数中,除以4余3,除以5余2,除以7余4的最大自然数是多少?
6、有一个两位数,除以2与除以3都余1,除以4与除以5都余3,求这个数。

 

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有