旺旺网 - Powered by Discuz! Board

标题: [求助] 请教奥数难题：同余问题 [打印本页]

作者: wikky 时间: 2008-11-18 19:14 标题: 请教奥数难题：同余问题

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

作者: litao 时间: 2008-11-19 08:32

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..

作者: echooooo 时间: 2008-11-19 09:55

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

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

作者: greenjyz 时间: 2008-11-19 09:58 标题: 回复 3#echooooo 的帖子

妙！.

作者: 一叶轻舟 时间: 2008-11-19 10:01 标题: 回复 3#echooooo 的帖子

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

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

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

作者: echooooo 时间: 2008-11-19 10:12 标题: 回复 5#一叶轻舟的帖子

"快乐老爸"的做法的确更具推广性
不过少了点趣味

而且说实话
俺没看懂

作者: 一叶轻舟 时间: 2008-11-19 10:27 标题: 回复 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 编辑 ].

作者: echooooo 时间: 2008-11-19 10:36

呵呵
巩固一下

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

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

作者: 一叶轻舟 时间: 2008-11-19 10:47

引用:

原帖由 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 编辑 ].

作者: echooooo 时间: 2008-11-19 10:52 标题: 回复 9#一叶轻舟的帖子

不好意思，俺题改过了

作者: 一叶轻舟 时间: 2008-11-19 10:57 标题: 回复 10#echooooo 的帖子

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

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

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

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

作者: echooooo 时间: 2008-11-19 10:57

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

作者: echooooo 时间: 2008-11-19 11:00 标题: 回复 11#一叶轻舟的帖子

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

作者: 一叶轻舟 时间: 2008-11-19 11:03 标题: 回复 13#echooooo 的帖子

我也是信口一说呢

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

作者: echooooo 时间: 2008-11-19 11:08

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

作者: greenjyz 时间: 2008-11-19 11:46

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

作者: yyf1023 时间: 2008-11-19 12:07 标题: 回复 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

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

作者: 一叶轻舟 时间: 2008-11-19 12:34

引用:

原帖由 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 编辑 ].

作者: wikky 时间: 2008-11-19 12:48

多谢楼上各位大师！

我基本上看懂了，已打印下来，再消化消化。.

作者: yyf1023 时间: 2008-11-19 12:53 标题: 回复 18#一叶轻舟的帖子

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

作者: wikky 时间: 2008-11-19 17:54

换个面孔，我又糊涂了

！继续请教——
一个正整数除以19余9，除以23余7，求满足条件的最小正整数是多少？.

作者: GerryBB 时间: 2008-11-19 18:27

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

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

作者: chin 时间: 2008-11-19 18:50 标题: 回复 21#wikky 的帖子

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

作者: litao 时间: 2008-11-20 08:35 标题: 回复 21#wikky 的帖子

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

作者: wikky 时间: 2008-11-20 08:58

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

作者: annazq 时间: 2008-11-21 08:29 标题: 回复 7#一叶轻舟的帖子

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

作者: 一叶轻舟 时间: 2008-11-21 08:38 标题: 回复 26#annazq 的帖子

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

作者: zhenai 时间: 2008-11-21 10:26

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

欢迎光临旺旺网 (http://ww123.net/)