发新话题
打印【有0个人次参与评价】

[求助] 请教奥数难题:同余问题

请教奥数难题:同余问题

1、有一个整数,用它去除63,91,129所得到的三个余数的和是25,求这个整数。
2、已知一个整数被7除余2,被9除余4,又恰好能被5整除,求这样的最小整数。
   (注:这题我用笨办法做,得出答案是310。但如何用“同余”的方法巧算呢?)
请教高手了!.

TOP

1、63+91+129-25=258=2*129=2*3*43
      这个整数为43.
2、7*9=63 除以5余3
      7*5=35 除以9余8
      5*9=45 除以7余3
      45*3+35*5+63*5=625
      625/(7*9*5)=1。。。。。。310
     最小整数310..

TOP

2、已知一个整数被7除余2,被9除余4,又恰好能被5整除,求这样的最小整数。

被7除余2——即+5能被7整除
被9除余4——即+5能被9整除
被5整除——即+5能被5整除
5x7x9-5=310.

TOP

回复 3#echooooo 的帖子

妙!.

TOP

回复 3#echooooo 的帖子

你的方法就本题而言是最简单快捷的!

但从掌握方法的角度另论,  "快乐老爸"的做法是普遍适用的通法 (虽然用于本题略有牛刀杀鸡的感觉)

[ 本帖最后由 一叶轻舟 于 2008-11-19 10:16 编辑 ].

TOP

回复 5#一叶轻舟 的帖子

"快乐老爸"的做法的确更具推广性
不过少了点趣味
而且说实话
俺没看懂.

TOP

回复 6#echooooo 的帖子

没错, 是少了点趣味, 但你的做法仅适用于本题, 因为正好找到了都加5这个规律

快乐老爸的思路大致是这样的 (注: 以下也是我刚刚揣摩的,不一定正确) :
(1) 找出满足 "被7整除,被9整除,且又恰好除以5余0" 的数
      鉴于 7*9=63  能被7和9整除, 且除以5余3
      所以 63*5      能被7和9整除, 且又恰好除以5余0

(2) 找出满足 "被5整除,被7整除,且又恰好除以9余4" 的数
      鉴于 7*5=35 能被5和7整除, 且除以9余8,
      所以 35*5     能被5和7整除, 且除以9余4

(3) 找出满足 "被9整除,被5整除,且又恰好除以7余2" 的数
      鉴于 5*9=45 能被9和5整除, 且除以7余3,
      所以 45*3     能被9和5整除, 且除以7余2

所以, 63*5+ 35*5+45*3=625 必满足被7除余2,被9除余4,又恰好能被5整除
然后求最小的解, 625 可以减去一个 (7*9*5)=315  得到310

[ 本帖最后由 一叶轻舟 于 2008-11-19 10:33 编辑 ].

TOP

呵呵
巩固一下

已知一个整数被7除余2,被9除余3,被5除余4,求这样的最小整数。

[ 本帖最后由 echooooo 于 2008-11-19 10:38 编辑 ].

TOP

引用:
原帖由 echooooo 于 2008-11-19 10:36 发表
呵呵
巩固一下

已知一个整数被7除余2,被9除余3,被5除余4,求这样的最小整数。
好的, 实战一下, 俺先试试

(1) 7*9=63, 63 mod 5 = 3 ∴63*3 mod 5 = 4

(2) 7*5=35, 35 mod 9 = 8 ∴35*6 mod 9 = 3
   
(3) 5*9=45, 45 mod 7 = 3 ∴45*3 mod 7 = 2

∴ 63*3 + 35*6 + 45*3 = 534
    534 - 5*7*9 = 219

[ 本帖最后由 一叶轻舟 于 2008-11-19 10:53 编辑 ].

TOP

回复 9#一叶轻舟 的帖子

不好意思,俺题改过了.

TOP

回复 10#echooooo 的帖子

不好意思, 俺也跟着改了, 其实这种题数字越大越能显示优越性

俺在想, 还可以继续推广, 如被7除余a1,被9除余a2,被5除余a3,被11除余a4......求这样的最小整数

今朝跟快乐老爸学了一招, 蛮不错的

[ 本帖最后由 一叶轻舟 于 2008-11-19 11:02 编辑 ].

TOP

要是实在掌握不了
那就穷举吧
从1算到最小公倍数
有且只有一个数是符合的.

TOP

回复 11#一叶轻舟 的帖子

吼吼
那计算量就有点大了.

TOP

回复 13#echooooo 的帖子

我也是信口一说呢

不过, 原本我的孩子碰到这种慧眼找不出规律的题, 往往是只好"枚举"的, 现在好歹有"武器"了.

TOP

实际上,
从+n能被a、b、c...整除这种思路来枚举
做题的速度也蛮快的了.

TOP

哈!两位大师的交流碰撞出智慧的火花了!.

TOP

回复 7#一叶轻舟 的帖子

鉴于 7*9=63  能被7和9整除, 且除以5余3
      所以 63*5      能被7和9整除, 且又恰好除以5余0
鉴于 7*5=35 能被5和7整除, 且除以9余8,
      所以 35*5     能被5和7整除, 且除以9余4
鉴于 5*9=45 能被9和5整除, 且除以7余3,
      所以 45*3     能被9和5整除, 且除以7余2

请教这个因果关系如何得出?.

TOP

引用:
原帖由 yyf1023 于 2008-11-19 12:07 发表
鉴于 5*9=45 能被9和5整除, 且除以7余3,
所以 45*3   能被9和5整除, 且除以7余2
请教这个因果关系如何得出?
首先, 5 | 45, 9 | 45   ==>  5 | 45*n,  9 | 45*n
其次, 45 mod 7 = 3  ==>  45*n mod 7 = 3*n   ==>   当n=3时, 45*n mod 7 = 9 mod 7 = 2

[ 本帖最后由 一叶轻舟 于 2008-11-19 12:45 编辑 ].

TOP

多谢楼上各位大师!
我基本上看懂了,已打印下来,再消化消化。.

TOP

回复 18#一叶轻舟 的帖子

谢谢,明白了.看来自己还需要学习.

TOP

换个面孔,我又糊涂了!继续请教——
一个正整数除以19余9,除以23余7,求满足条件的最小正整数是多少?.

TOP

237?   “此”题不是“那”题,小舟老师继续上来

[ 本帖最后由 GerryBB 于 2008-11-19 18:36 编辑 ].

TOP

回复 21#wikky 的帖子

19-9=10
23-7=16
19(n+a)+10=23n+16
n=8
a=2
23x8+16=200
19x23-200=237.

TOP

回复 21#wikky 的帖子

19a+9=23b+7
23b-19a=2
19(a-b)=4b-2
b=10,a=12
23*10+7=237.

TOP

感谢chin老师和litao老师!原来换个格式,解题思路就不一样了!.

TOP

回复 7#一叶轻舟 的帖子

女儿昨天正好做到类似题目,您用的方法就是剩余定理吧?.

TOP

回复 26#annazq 的帖子

您太客气了
此方法版权属于快乐老爸, 俺只是概括说明了一下
说实在的, 我真不知道是不是叫"剩余定理", 应该属于同余类的吧.

TOP

就是所谓的“中国剩余定理”。还有那个韩信点兵的故事。.

TOP

发新话题