作整除题有没有通用的方法
本帖最后由 jiahongyuan 于 2010-5-20 18:45 编辑when n is divided by 3, the remainder is 2. When n is divided by 4, the remainder is 1. When n is divided by 12, what is the remainder? 请善用谷歌搜索。
“Well, I personally would go for a numerical approach for this one, but here's a way to work it algebraically:
Let n = 3j + 2, where j is a positive integer
Let t = 5k + 3, where k is a positive integer
nt = (3j+2)(5k+3) = 15jk + 9j + 10k + 6
So the question is: what is the remainder after 15jk + 9j + 10k + 6 is divided by 15? Well, 15jk is clearly divisible by 15. If we show that 9j and 10k are divisible by 15 as well, then we can determine the remainder (6).
(1) The fact that n - 2 is divisible by 5 means that 3j is divisible by 5. So j can be written as 5x, where x is a positive integer. That means we can rewrite 9j (in the question) as 45x, which is divisible by 15. But we don't know whether 10k is divisible by 15. Insufficient.
(2) That t is divisible by 3 means that 5k + 3 is divisible by 3, and therefore 5k is divisible by 3. So k can be written as 3y, where y is a positive integer. That means we can rewrite 10k (in the question) as 30y, which is divisible by 15. But we don't know whether 9j is divisible by 15. Insufficient.
(1&2) nt = 15jk + 9j + 10k + 6 = 15jk + 45x + 30y + 6. The remainder must be 6. Sufficient.” 本帖最后由 jiahongyuan 于 2010-5-20 18:46 编辑
2# 江雪 本帖最后由 jiahongyuan 于 2010-5-20 20:49 编辑
上面的方法有点复杂,我怕真正考试时出错,琢磨半天,想用这下面这个方法,不知怎样
用从小到大的方法测试,但此方法仅对右项(即要求的数)为左边两项的公倍数时计算比较方便.http://sns.gter.net/attachment/201005/20/2709285_1274359709jpHR.png
file:///Users/jhy/Library/Caches/TemporaryItems/moz-screenshot.pngfile:///Users/jhy/Library/Caches/TemporaryItems/moz-screenshot-1.png 本帖最后由 tony0411 于 2010-5-20 22:11 编辑
3a +2 = 4b+1 ==> 4b - 3a = 1, 快速找到任意一组解满足这个方程且a,b均为整数, 例如a=1 b=1 a=5 b=4 然后a或b任意带回原方程求得一个数. 然后再用那个数除12..... 我觉得这样可能会快一些. 2楼的回答很强大,不过题目问的是除12后的余数而不是15
对于GRE来说,直接带数字进去更简单吧
5/3余2, 5/4余1, 5/12余5 => 5就是答案了 2楼写了一堆,结果错了。
随便代数即可,如楼上。
页:
[1]