ChaseDream
标题: 关于GMAT数学中求余数问题的一个简单方法-增强版 [打印本页]
作者: 知之为之之 时间: 2010-2-4 12:57
标题: 关于GMAT数学中求余数问题的一个简单方法-增强版
个人建议：在您看这份文档的同时，准备一支笔，一张草稿纸。如果看到例题，跟我的步骤，一步一步地同时写下来，这样比光看屏幕，要理解得更快！
我在自己的讨论稿文档里，求余的时候，都会用到mod这个运算符。
mod：模。意思就是求余数。
比如说：5 mod 3=2， 100 mod 11=1
读作：五模三余二，一百模十一余一
这是标准的公式化写法，大家可能不太熟悉，但是知道意思了，其实也很简单。引入Mod，主要是可以用数学公式来写，而且可以把求余数的问题化简成为普通的四则运算的问题，也比较容易表达。
在讲如何求余之前，先来普及一下余数的一些性质。
首先就是余数的加减法：比如说100除以7余2，36除以7余1。那么100+36除以7余几呢？或者100-36除以7余几呢？很显然，只要用100除以7的余数2与36除以7的余数1进行加减就可以得到答案。通过这个例子可以很明显的看出来，余数之间是可以加减的。
总结写成书面的公式的话，就是：(M＋N) mod q=(（M mod q）+（N mod q）) mod q
然后我们再看余数的乘法：我们继续来看上面这个例子，如果要求100*36除以7的余数是多少，该怎么求呢？
我们不妨来这样做：
100=98+2=7*14+2，36=35+1=7*5+1；
这时100*36=（7*14+2）（7*5+1）=7*14*7*5 + 2*7*5 + 7*14*1 + 2*1
很明显，100*36除以7的余数就等于2*1=2
于是我们可以得出这样的一个结论：求M*N除以q的余数，就等于M除以q的余数 乘以 N除以q的余数。
类似的，如果是求N^m 除以q的余数呢？只要我们将N^m=N*N*N*...*N，也就是说分别地用每个N除以q的余数相乘，一共m个，得出的结果再对q求余数，即可求出结果。
举例来说：求11^4除以9的余数。化成公式即是：11^4 mod 9=?
11^4 mod 9 = (9+2)^4 mod 9 = 2^4 mod 9 =16 mod 9 = 7
于是我们可以总结出这样的公式：
M*N mod q=（M mod q）*（N mod q） mod q
（ M^n mod q = （M mod q）^n mod q ）
那么，我们知道了这些性质之后对解题又有什么帮助呢？
As we all know，如果一个数乘以1，还是等于原数；而1的任意次方，还是等于1。
所以在解答这一类的问题的时候，只要我们尽量把计算中的余数凑成与1相关的乘式，结果显然会好算很多的。（或者-1，2之类的比较容易进行计算的数字都可以，因题而异。）
举例说明：求3^11除以8的余数。题目即是：3^11 mod 8=?
3^11 mod 8
=3^10 * 3^1 （mod 8）
=(3^2)^5*(3^1) （mod 8）
=9^5 * 3 （mod 8）
=(8+1)^5 * 3 （mod 8）
=1^5 *3 （mod 8）
=3
发现没有，甚至没有去计算什么尾数的规律，答案就算出来了，而且只用了加减乘除。
那么再来看一道题目：求 （2^100）*（3^200） 除以7的余数
先化成计算公式：
(2^100)*(3^200) mod 7
=[2^(3*33 + 1)] * [3^(3*66 + 2)] mod 7
=[(2^3)^33 * 2] * [(3^3)^66 * 3^2] mod 7
=(8^33 * 2) * (27^66 * 9) mod 7
=[(7+1)^33 * 2] * [(28-1)^66 * 9] mod 7
=(1^33 * 2)* [(-1)^66 * 9] mod 7
=2*9 mod 7
=4
注意：如果余数有负号，就当做负数一样计算。
我步骤写得很详细，但其实只要是熟练了，基本上只要三四步答案一定就出来了，有没有觉得很简单呢？赶紧找一两题来练练手吧，甚至随便写几个数字来做做试试看，像我上面的例题都是临时编的。
相信只要练习了三四道题目，以后再碰到这样的余数题，就会 会心地一笑：小样
，秒掉你！
我的语文不是太好，表达上可能有很多不清楚，但是大概就是这个意思，大家看看，讨论讨论...
作者: chicago328 时间: 2010-2-4 13:23
这是LZ自创的吗？ MOD。^_^
作者: 知之为之之 时间: 2010-2-4 13:24
这是LZ自创的吗？ MOD。^_^
-- by 会员 chicago328 (2010/2/4 13:23:08)
当然不是……
这是国际通用的运算符……
只不过不是数学系的学生，一般不熟悉
作者: ctscts1985 时间: 2010-2-4 13:49
好贴，虽说有点没太看懂！呵呵！
顶一下，有点沉！
作者: adelemao 时间: 2010-2-4 13:54
仔细看还成要是远观很吓人~~嘻嘻，还是谢谢楼主@@
作者: 知之为之之 时间: 2010-2-4 14:09
仔细看还成要是远观很吓人~~嘻嘻，还是谢谢楼主@@
-- by 会员 adelemao (2010/2/4 13:54:11)
那就仔细看吧...有什么问题写下来，我改改。表达能力不是很强……
作者: 知之为之之 时间: 2010-2-5 01:11
5555……表达能力太差了，貌似大家没怎么看懂……
作者: huzhongyan 时间: 2010-2-5 01:22
很实用啊！多谢
作者: JNash 时间: 2010-2-5 08:54
谢谢楼主，不过怎么感觉实际解题了冷咖啡的差不多呢？
是我理解错误么？可否在解释解释？
作者: tibet 时间: 2010-2-5 09:38
哈哈，刚做到这题
实用
谢谢
作者: tibet 时间: 2010-2-5 10:29
lz 有个问题
(M＋N) mod q=(（M mod q）+（N mod q）) mod q
这样对的么
作者: yuling526 时间: 2010-2-5 13:27
标题: 还是不懂，能不能解释一下下面的过程阿
39. 2^90+3^90 dividable by 5, remainder?
2^90 + 3^90 (mod 5)
= 4^45 + (-2)^90 (mod 5)
=(-1)^45 + 4^45 (mod 5)
=2 * (-1)^45 (mod 5)
= -2 (mod 5)
= 3
作者: tibet 时间: 2010-2-5 13:52
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
=16^22*4+16^22*4 (mod 5)
= 4+4 (mod 5)
= 3
作者: 知之为之之 时间: 2010-2-5 14:42
谢谢楼主，不过怎么感觉实际解题了冷咖啡的差不多呢？
是我理解错误么？可否在解释解释？
-- by 会员 JNash (2010/2/5 8:54:32)
原理上来说确实是一样的……
我引入mod这个概念，其实是为了让大家做题的时候更便于写公式，以及检验。
作者: Sherry_Wong 时间: 2010-2-5 14:55
谢谢楼主，费心啦~~
作者: kingapple25 时间: 2010-2-5 16:28
lz强的，赞！
作者: 知之为之之 时间: 2010-2-5 17:12
修改了一下...觉得这样似乎更通俗易懂了……
作者: 知之为之之 时间: 2010-2-5 17:32
编辑了半天...确认发送之后，文档总是与我排版的不一样……我恨啊……
作者: 记忆钢琴 时间: 2010-2-5 18:55
lz新改的贴表达很清晰~~终于把我看懂了。。。顶~！
作者: 记忆钢琴 时间: 2010-2-5 19:01
我想知道有什么方法能检验我算的对不对。。。计算器能吗
作者: 知之为之之 时间: 2010-2-5 19:05
我想知道有什么方法能检验我算的对不对。。。计算器能吗
-- by 会员 记忆钢琴 (2010/2/5 19:01:05)
如果严格按照我的方法来做应该不会错，不过要是你不放心，可以用比如说...呃...貌似指数太大，计算器一般也很难算哦...
你跟这个贴，我帮你检验吧……
作者: 记忆钢琴 时间: 2010-2-5 19:11
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
做到这里，然后为什么
（5-1）^45+(5-1)^45 (mod 5)
=1^45+1^45 (mod 5)
=2
这样做怎么错了？
作者: 知之为之之 时间: 2010-2-5 19:14
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
做到这里，然后为什么
（5-1）^45+(5-1)^45 (mod 5)
=1^45+1^45 (mod 5)
=2
这样做怎么错了？
-- by 会员 记忆钢琴 (2010/2/5 19:11:48)
5-1的话，应该余数就是-1了，（-1）^45=-1
懂了吗？
作者: dugujianzp 时间: 2010-2-5 19:22
计算机里貌似见过呢，传说中的机器语言吗，楼主很好很强大，看懂了
作者: 知之为之之 时间: 2010-2-5 19:29
计算机里貌似见过呢，传说中的机器语言吗，楼主很好很强大，看懂了
-- by 会员 dugujianzp (2010/2/5 19:22:35)
这个mod其实就是跟加减乘除一样的，呵呵，计算机里面好像也有。。。
我个人更喜欢称之为数学语言，呵呵
作者: junjun_Q 时间: 2010-2-5 19:40
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
做到这里，然后为什么
（5-1）^45+(5-1)^45 (mod 5)
=1^45+1^45 (mod 5)
=2
这样做怎么错了？
-- by 会员 记忆钢琴 (2010/2/5 19:11:48)
5-1的话，应该余数就是-1了，（-1）^45=-1
懂了吗？
-- by 会员 知之为之之 (2010/2/5 19:14:26)
那这题最后答案是多少? -2?
作者: 记忆钢琴 时间: 2010-2-5 19:55
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
做到这里，然后为什么
（5-1）^45+(5-1)^45 (mod 5)
=1^45+1^45 (mod 5)
=2
这样做怎么错了？
-- by 会员 记忆钢琴 (2010/2/5 19:11:48)
5-1的话，应该余数就是-1了，（-1）^45=-1
懂了吗？
-- by 会员 知之为之之 (2010/2/5 19:14:26)
就是说最后得-2吗？ 可是应该得3吧，我也不知道这答案对不对， 这是前面ls的题
作者: 知之为之之 时间: 2010-2-5 21:23
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
做到这里，然后为什么
（5-1）^45+(5-1)^45 (mod 5)
=1^45+1^45 (mod 5)
=2
这样做怎么错了？
-- by 会员 记忆钢琴 (2010/2/5 19:11:48)
5-1的话，应该余数就是-1了，（-1）^45=-1
懂了吗？
-- by 会员 知之为之之 (2010/2/5 19:14:26)
就是说最后得-2吗？ 可是应该得3吧，我也不知道这答案对不对， 这是前面ls的题
-- by 会员 记忆钢琴 (2010/2/5 19:55:58)
如果5的余数是-2，那不就是3吗？你再想想……
作者: 知之为之之 时间: 2010-2-5 21:24
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
做到这里，然后为什么
（5-1）^45+(5-1)^45 (mod 5)
=1^45+1^45 (mod 5)
=2
这样做怎么错了？
-- by 会员 记忆钢琴 (2010/2/5 19:11:48)
5-1的话，应该余数就是-1了，（-1）^45=-1
懂了吗？
-- by 会员 知之为之之 (2010/2/5 19:14:26)
那这题最后答案是多少? -2?
-- by 会员 junjun_Q (2010/2/5 19:40:27)
见楼上
作者: 大荣 时间: 2010-2-5 21:58
计算机里貌似见过呢，传说中的机器语言吗，楼主很好很强大，看懂了
-- by 会员 dugujianzp (2010/2/5 19:22:35)
是的，计算机的hash算法中，一种最简单的hash函数就是对质数取模得到散列值。
作者: 知之为之之 时间: 2010-2-5 22:02
计算机里貌似见过呢，传说中的机器语言吗，楼主很好很强大，看懂了
-- by 会员 dugujianzp (2010/2/5 19:22:35)
是的，计算机的hash算法中，一种最简单的hash函数就是对质数取模得到散列值。
-- by 会员 大荣 (2010/2/5 21:58:31)
嗯 嗯 嗯，数据结构里面貌似也用到挺多的，特别是在排序问题上
作者: 大荣 时间: 2010-2-5 22:23
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
做到这里，然后为什么
（5-1）^45+(5-1)^45 (mod 5)
=1^45+1^45 (mod 5)
=2
这样做怎么错了？
-- by 会员 记忆钢琴 (2010/2/5 19:11:48)
5-1的话，应该余数就是-1了，（-1）^45=-1
懂了吗？
-- by 会员 知之为之之 (2010/2/5 19:14:26)
LZ和各位tx，提个建议，是不是最好不要拆分成两数想减的形式，比如2^10=(5-3)^10.
请仔细阅读http://forum.chasedream.com/GMAT_Math/thread-403174-1-1.html，里面也强调分解成两个正整数相加的形式。
假设求j^n除以k的余数，j^n=(mk+q)^n, 利用二项式定理展开，之所以可以舍弃前n项，只考虑q^n，有个前提q是非负整数，且0=<q<k.
如果q是个负数，那么前面n项展开就要考虑正负号。根据OG12的定义，“If x and y are positive integers, there exist unique integers q and r, called the quotient and remainder, respectively, such that y = xq + r and 0 ≤ r < x.”。只有正整数才有资格讨论商和余数。举个例子，-5+4除以5的余数是多少，是4还是-1？而且-5余数是0的提法也似乎不符合定义。
一起讨论哦。
作者: lw666777 时间: 2010-2-5 22:31
楼主牛气...
作者: 知之为之之 时间: 2010-2-5 22:43
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
做到这里，然后为什么
（5-1）^45+(5-1)^45 (mod 5)
=1^45+1^45 (mod 5)
=2
这样做怎么错了？
-- by 会员 记忆钢琴 (2010/2/5 19:11:48)
5-1的话，应该余数就是-1了，（-1）^45=-1
懂了吗？
-- by 会员 知之为之之 (2010/2/5 19:14:26)
LZ和各位tx，提个建议，是不是最好不要拆分成两数想减的形式，比如2^10=(5-3)^10.假设求j^n除以k的余数，之所以j^n=(mk+q)^n, 可以利用二项式定理展开，可以舍弃q^n，有个前提，q是非负整数，且0=<q<k. 如果q是个负数，那么前面n项展开就要考虑正负号。根据OG12的定义，“If x and y are positive integers, there exist unique integers q and r, called the quotient and remainder, respectively, such that y = xq + r and 0 ≤ r < x.”。只有正整数才有资格讨论商和余数。举个例子，-5+4的余数是多少，4还是-1，而且-5余数是0的提法是不符合定义的，不严密的。请仔细阅读http://forum.chasedream.com/GMAT_Math/thread-403174-1-1.html，里面也强调分解成两个正整数相加的形式。一起讨论哦。-- by 会员 大荣 (2010/2/5 22:23:03)
嗯，你有这个想法挺好的，不过我在这里引入负数，主要是为了让计算更简便，最终的结果的话肯定还是要用正数来表达。
引入负数的话，在对那些比如说：2^100 mod 9这样的题目尤其方便，如果一定要用正数，那么2^4=16=9+7，于是题目就变成 7^25 mod 9。。。还需要继续变化。但是如果用负数呢，2^3=8=9-1,于是题目就变成 (2^3)^33 * 2 mod 9=(-1)^33 *2 mod 9=-2 mod 9 =7
您看是不是方便很多呢？
而且你提到那个二项式的展开，其实你自己想想，其实不用考虑前面的正负号，而只用关心最后那个数字的正负号就行了，对不对？因为前面的数都是你要除的那个数的倍数，所以无论是加是减，结果一定还是除数的倍数，对吧。所以最终还是化到最后那个余数上面来了。您可以试试展开看看。
对于我们学数学的同学，余数概念大概要要比GMAT上定义的要广义一点。
作者: 大荣 时间: 2010-2-5 23:08
2^90 + 3^90 (mod 5)
= 4^45 + (9)^45 (mod 5)
=4^45 + 4^45 (mod 5)
做到这里，然后为什么
（5-1）^45+(5-1)^45 (mod 5)
=1^45+1^45 (mod 5)
=2
这样做怎么错了？
-- by 会员 记忆钢琴 (2010/2/5 19:11:48)
5-1的话，应该余数就是-1了，（-1）^45=-1
懂了吗？
-- by 会员 知之为之之 (2010/2/5 19:14:26)
LZ和各位tx，提个建议，是不是最好不要拆分成两数想减的形式，比如2^10=(5-3)^10.假设求j^n除以k的余数，之所以j^n=(mk+q)^n, 可以利用二项式定理展开，可以舍弃q^n，有个前提，q是非负整数，且0=<q<k. 如果q是个负数，那么前面n项展开就要考虑正负号。根据OG12的定义，“If x and y are positive integers, there exist unique integers q and r, called the quotient and remainder, respectively, such that y = xq + r and 0 ≤ r < x.”。只有正整数才有资格讨论商和余数。举个例子，-5+4的余数是多少，4还是-1，而且-5余数是0的提法是不符合定义的，不严密的。请仔细阅读http://forum.chasedream.com/GMAT_Math/thread-403174-1-1.html，里面也强调分解成两个正整数相加的形式。一起讨论哦。-- by 会员 大荣 (2010/2/5 22:23:03)
嗯，你有这个想法挺好的，不过我在这里引入负数，主要是为了让计算更简便，最终的结果的话肯定还是要用正数来表达。
引入负数的话，在对那些比如说：2^100 mod 9这样的题目尤其方便，如果一定要用正数，那么2^4=16=9+7，于是题目就变成 7^25 mod 9。。。还需要继续变化。但是如果用负数呢，2^3=8=9-1,于是题目就变成 (2^3)^33 * 2 mod 9=(-1)^33 *2 mod 9=-2 mod 9 =7
您看是不是方便很多呢？
而且你提到那个二项式的展开，其实你自己想想，其实不用考虑前面的正负号，而只用关心最后那个数字的正负号就行了，对不对？因为前面的数都是你要除的那个数的倍数，所以无论是加是减，结果一定还是除数的倍数，对吧。所以最终还是化到最后那个余数上面来了。您可以试试展开看看。
对于我们学数学的同学，余数概念大概要要比GMAT上定义的要广义一点。
-- by 会员 知之为之之 (2010/2/5 22:43:42)
恩，确实某些情况拆成减1的形式可以算得快。其实，2^100 mod 9还可以看成[(63+1)^16]*[2^4] mod 9也很快的,呵呵。
我仔细再想了一下，j^n=(mk+q)^n，GMAT题不讨论负数的余数问题，所以GAMT题中j总是正整数，这个正数保证q^n以外的n项和一定是个正整数，这就和定义match上了。
LZ看怎么算的快就怎么算吧。
作者: dabenfang 时间: 2010-2-5 23:46
爱死楼主了 终于会了 就是负数除正数 小数除大数 这些余数是多少啊
举个例子 -5除以9 5除以9
作者: dabenfang 时间: 2010-2-5 23:48
亲爱的楼主 您还有类似的文章么 我数学超烂 求其它类似文章链接 谢谢！！
作者: 大荣 时间: 2010-2-5 23:49
爱死楼主了 终于会了 就是负数除正数 小数除大数 这些余数是多少啊
举个例子 -5除以9 5除以9
-- by 会员 dabenfang (2010/2/5 23:46:09)
帮楼主顶一下。
GMAC只讨论正数的余数，不考虑-5.
5除9余5. 看如下OG12的说明。
”Also, note that when a smaller integer is divided by a larger integer, the quotient is 0 and the
remainder is the smaller integer. For example, 5 divided by 7 has the quotient 0 and the remainder 5
since 5 = (7)(0) + 5.“
作者: 知之为之之 时间: 2010-2-5 23:58
亲爱的楼主 您还有类似的文章么 我数学超烂 求其它类似文章链接 谢谢！！
-- by 会员 dabenfang (2010/2/5 23:48:11)
其他文章...我没有啊，就写了这一篇……
你在精华里找找吧……
作者: 知之为之之 时间: 2010-2-6 00:02
爱死楼主了 终于会了 就是负数除正数 小数除大数 这些余数是多少啊
举个例子 -5除以9 5除以9
-- by 会员 dabenfang (2010/2/5 23:46:09)
呃...如果你问的是负数的多少次方除以正数，那就像正数一样来做，只是千万不要忘了要带上负号一起计算……
小数除大数...也是指小数的多少次方除以大数吧……文中的例子都是……
如果 只是-5除以9的话，先考虑余数是-5，然后因为最终余数应该是一个正数，那么-5=4-9，于是余数就是4了。。。呵呵
5除以9的话，就看你楼下那个同学的，就是5
作者: kingapple25 时间: 2010-2-6 10:34
方法巧妙，讲解透彻，非常棒！
作者: girlwithwings 时间: 2010-2-6 14:06
谢谢LZ的启发。
我根据LZ的列示简化了一下运算过程，试验了一下都对。
2^100 * 3^200 mod 7
2^100*3^200
= [(2^3)^33*2] * [(3^2)^100] 取2^3 & 3^2 是因为他们刚刚比7多一点, -7后剩下的余数好算
= [1^33 *2 ]* [2^100] 2^3 -7 =1 3^2 - 7 = 2 [2^100] :如前面计算得出余数2
=2 * 2
=4
11^4 mod 9
=2^4 11-9
=16-9
=7
3^11 mod 8
= (3^2)^5*3 9-8=1
=1^5 *3
=3
100*36 mod 7
= (14*7+2) * (5*7+1)
=2 * 1
=2
2^90+3^90 dividable by 5, remainder?
2^90 +3^90
=(2^2)^45 +(3^2)^45
= 4^45 + 9 ^45 9-5=4 比5大的数-5
= 4^45 + 4^45 4-5=-1
= 2* (-1)^45
= 2* (-1) -2+5 =3 负数+5
=5
-2除以5 ，除数-1， 余数3 即5*（-1）+3 = -2
再比如-6除以5 ，除数-1 ，余数-1， 即5×（-1）+（-1）=-6
作者: girlwithwings 时间: 2010-2-6 14:20
-2除以5 ，除数-1， 余数3 即5*（-1）+3 = -2
再比如-6除以5 ，除数-1 ，余数-1， 即5×（-1）+（-1）=-6
作者: crazy0412 时间: 2010-2-6 15:57
实用 顶一下 ！！
作者: littlecloud 时间: 2010-2-6 18:16
增强版非常清楚，谢谢！！
作者: 知之为之之 时间: 2010-2-6 19:30
-2除以5 ，除数-1， 余数3 即5*（-1）+3 = -2
再比如-6除以5 ，除数-1 ，余数-1， 即5×（-1）+（-1）=-6
-- by 会员 girlwithwings (2010/2/6 14:20:59)
看来你已经完全贯通了……
不过一般我们给出最终的答案的时候还是喜欢用正数。
比如说-2 mod 5=3
-6 mod 5 =4
作者: dabenfang 时间: 2010-2-6 21:51
是不是负数这样算：-9除以5=-9+5=-4 -4+5=1 所以余数为1
而5除以9 余数为5
作者: 知之为之之 时间: 2010-2-6 21:59
是不是负数这样算：-9除以5=-9+5=-4 -4+5=1 所以余数为1
而5除以9 余数为5
-- by 会员 dabenfang (2010/2/6 21:51:53)
u got it
作者: dabenfang 时间: 2010-2-6 22:11
楼主 太神速了 呼呼！！
还有个题外问题 ： 那个数学鸡精置顶的贴 是每次修改都重新更新？ 还是要到下面新发的帖子去下更新后版本呢？
PS LOVE U
作者: 知之为之之 时间: 2010-2-6 22:24
楼主 太神速了 呼呼！！
还有个题外问题 ： 那个数学鸡精置顶的贴 是每次修改都重新更新？ 还是要到下面新发的帖子去下更新后版本呢？
PS LOVE U
-- by 会员 dabenfang (2010/2/6 22:11:39)
就在首页更新的。
PS love me? if you r girl 那就更好了...haha
作者: pammy0926 时间: 2010-2-8 11:23
太牛拜了，简直无往不胜嘛，楼主，膜拜您!
作者: Avène 时间: 2010-2-8 22:55
果然好用！！！谢谢楼主
作者: zx1988626 时间: 2010-2-9 20:59
写的很好 比gwd的好
作者: stephywu 时间: 2010-2-9 21:13
很有用，谢谢楼主
作者: sjmdlyc 时间: 2010-2-9 22:18
谢谢~
作者: 知之为之之 时间: 2010-2-9 22:21
1897年的mm……膜拜一下……
作者: zhackhame 时间: 2010-2-9 23:49
3Q~~~~~~~~~~
作者: adelemao 时间: 2010-2-10 01:03
个人建议：在您看这份文档的同时，准备一支笔，一张草稿纸。如果看到例题，跟我的步骤，一地同时写下来，这样比光看屏幕，要理解得更快！
我在自己的讨论稿文档里，求余的时候，都会用到
mod这个运算符。
mod：模。意思就是求余数。
比如说：5 mod 3=2， 100 mod 11=1
读作：五模三余二，一百模十一余一
这是标准的公式化写法，大家可能不太熟悉，但是知道意思了，其实也很简单。引入Mod，主要是可以用数学公式来写，而且可以把求余数的问题化简成为普通的四则运算的问题，也比较容易表达。
在讲如何求余之前，先来普及一下余数的一些性质。
首先就是余数的加减法：比如说100除以7余2，36除以7余1。那么100+36除以7余几呢？或者100-36除以7余几呢？很显然，只要用100除以7的余数2与36除以7的余数1进行加减就可以得到答案。通过这个例子可以很明显的看出来，余数之间是可以加减的。
总结写成书面的公式的话，就是：(M＋N) mod q=(（M mod q）+（N mod q）) mod q
然后我们再看余数的乘法：我们继续来看上面这个例子，如果要求100*36除以7的余数是多少，该怎么求呢？
我们不妨来这样做：
100=98+2=7*14+2，36=35+1=7*5+1；
这时100*36=（7*14+2）（7*5+1）=7*14*7*5 + 2*7*5 + 7*14*1 + 2*1
很明显，100*36除以7的余数就等于2*1=2
于是我们可以得出这样的一个结论：求M*N除以q的余数，就等于M除以q的余数 乘以 N除以q的余数。
类似的，如果是求N^m 除以q的余数呢？只要我们将N^m=N*N*N*...*N，也就是说分别地用每个N除以q的余数相乘，一共m个，得出的结果再对q求余数，即可求出结果。
举例来说：求11^4除以9的余数。化成公式即是：11^4 mod 9=?
11^4 mod 9 = (9+2)^4 mod 9 = 2^4 mod 9 =16 mod 9 = 7
于是我们可以总结出这样的公式：
M*N mod q=（M mod q）*（N mod q） mod q
（ M^n mod q = （M mod q）^n mod q ）
那么，我们知道了这些性质之后对解题又有什么帮助呢？
As we all know，如果一个数乘以1，还是等于原数；而1的任意次方，还是等于1。
所以在解答这一类的问题的时候，只要我们尽量把计算中的余数凑成与1相关的乘式，结果显然会好算很多的。（或者-1，2之类的比较容易进行计算的数字都可以，因题而异。）举例说明：求3^11除以8的余数。题目即是：3^11 mod 8=?
3^11 mod 8
=3^10 * 3^1 （mod 8）
=(3^2)^5*(3^1) （mod 8）
=9^5 * 3 （mod 8）
=(8+1)^5 * 3 （mod 8）
=1^5 *3 （mod 8）
=3
发现没有，甚至没有去计算什么尾数的规律，答案就算出来了，而且只用了加减乘除。
那么再来看一道题目：求 （2^100）*（3^200） 除以7的余数
先化成计算公式： (2^100)*(3^200) mod 7
=[2^(3*33 + 1)] * [3^(3*66 + 2)] mod 7
=[(2^3)^33 * 2] * [(3^3)^66 * 3^2] mod 7
=(8^33 * 2) * (27^66 * 9) mod 7
=[(7+1)^33 * 2] * [(28-1)^66 * 9] mod 7
=(1^33 * 2)* [(-1)^66 * 9] mod 7
=2*9 mod 7
=4
注意：如果余数有负号，就当做负数一样计算。
我步骤写得很详细，但其实只要是熟练了，基本上只要三四步答案一定就出来了，有没有觉得很简单呢？赶紧找一两题来练练手吧，甚至随便写几个数字来做做试试看，像我上面的例题都是临时编的。
相信只要练习了三四道题目，以后再碰到这样的余数题，就会 会心地一笑：小样，秒掉你！我的语文不是太好，表达上可能有很多不清楚，但是大概就是这个意思，大家看看，讨论讨论...-- by 会员 知之为之之 (2010/2/4 12:57:39)
知之老师你太太可爱了！
作者: 知之为之之 时间: 2010-2-10 01:10
... ...
不过你引用之后，这个排版才是我排的版啊……
不过貌似有的颜色还是不对……
作者: dontwannalose 时间: 2010-2-12 00:08
speechless...
作者: 紫苏0709 时间: 2010-2-12 00:42
谢谢楼主~~~~
作者: chantelle 时间: 2010-2-12 02:58
景仰知之为知之余数大法！太N 了！ 写得很好，通俗易懂！
作者: vosges 时间: 2010-2-12 04:21
\(^o^)/~ 太感谢了！！！
雪中送炭！！！
作者: stephywu 时间: 2010-2-12 16:53
弱弱地请教大家3^89mod7的余数到底是2呢还是5呢~~GWD的书上写5，但按照LZ的方法我算的2，是不是我计算错了~~~~~
作者: kingapple25 时间: 2010-2-12 17:19
弱弱地请教大家3^89mod7的余数到底是2呢还是5呢~~GWD的书上写5，但按照LZ的方法我算的2，是不是我计算错了~~~~~
-- by 会员 stephywu (2010/2/12 16:53:12)
你把你的过程写下，我按lz的方法算得也是5
作者: stephywu 时间: 2010-2-12 18:13
正确的算法是这样吗
3^89
=3^（3*29+2) mod7
=27^29 * 9 mod7
=(-1)^29*2 mod7
=(-2) mod7
=5
???请指导~~三克u~~
作者: prayer 时间: 2010-2-12 18:52
正确的算法是这样吗
3^89
=3^（3*29+2) mod7
=27^29 * 9 mod7
=(-1)^29*2 mod7
=(-2) mod7
=5
???请指导~~三克u~~
-- by 会员 stephywu (2010/2/12 18:13:01)
看起来好像对，呵呵
---------------------------------------------------------------------------------------
作者: true 时间: 2010-2-13 09:44
顶
好文
作者: 小薇姐姐 时间: 2010-2-14 12:55
LZ 真棒，赞一个！
作者: ggmaltose 时间: 2010-2-16 23:52
太牛了，超赞！
作者: cty8910 时间: 2010-2-17 01:17
很棒啊～～谢谢楼主！
作者: lisaijia526 时间: 2010-2-17 10:24
ding ni~
作者: 银灵 时间: 2010-2-18 15:34
顶LZ，好帖啊，一贴解决了一类题，多谢
作者: lisalidai 时间: 2010-2-18 17:37
请楼主多教一些GMAT 里面这样的窍门。
作者: simisaga 时间: 2010-2-18 21:30
非常有用!谢谢楼主！
作者: Iljiajia 时间: 2010-2-18 23:53
楼主写的很不错了，大家别对做奉献的人太挑剔了，这样不好，楼主不可能满足每一个看贴人的阅读习惯的，自己多多理解下我觉得没有任何问题！！
辛苦了楼主，非常感谢，祝新年旺运...
作者: niubirs 时间: 2010-2-19 03:15
楼上说的没错。非常感谢楼主！！我们应该对所有无私奉献的同学表示感谢~
作者: niubirs 时间: 2010-2-19 03:36
请问LZ，机经39题讨论稿的最后一步是: -2 mod 5,最后等于3是怎么来的？
作者: bbcxd 时间: 2010-2-19 06:15
太好用了这个！ 之之童靴灰肠厉害鸭
作者: wendy1989 时间: 2010-2-19 11:33
感谢楼主~！伟大~！撒花~！！
作者: blvicky 时间: 2010-2-20 10:45
好帖！不能沉！
作者: salina0806 时间: 2010-2-20 11:09
很好 谢谢
作者: issa35 时间: 2010-2-20 14:07
练习中
作者: 落卡落尘 时间: 2010-2-21 12:49
这贴超好，顶上去！
谢谢楼主！
作者: 落卡落尘 时间: 2010-2-21 12:57
LZ能帮我看下这样做对吗？
3^2006 mod 5
=(3^2)^1003 mod 5
=9^1003 mod 5
=(5+4)^1003 mod 5
=4^1003 mod 5
=(4^2)^501*4 mod 5
=16^501*4 mod 5
=16^501 mod 5 * 4 mod 5
=1*4=4
这样结果对么？
作者: lipsilon 时间: 2010-2-21 15:27
如果大家理解不了，mode这个感念，还想办法拆分为（x+1)^n or (x-1)^n, x是multiple哪个被除数, 最后只要求1^n or (-1)^n除哪个数余几久可以。
作者: yangyuxiao 时间: 2010-2-21 17:44
我觉得LZ表达的相当清楚啊~看了一遍就明白了
就是可惜例题少了点~~呵呵~~
真的是太感谢太及时了~
LZ辛苦了哈~！！！！
作者: infinitegrav 时间: 2010-2-21 17:57
这个好 能解决不少问题
作者: 知之为之之 时间: 2010-2-21 19:31
我觉得LZ表达的相当清楚啊~看了一遍就明白了
就是可惜例题少了点~~呵呵~~
真的是太感谢太及时了~
LZ辛苦了哈~！！！！
-- by 会员 yangyuxiao (2010/2/21 17:44:13)
例题你自己编……随便写几个数...方法都一样的，所以随便写点数字就行
作者: frankie0927 时间: 2010-2-22 04:52
很实用啊！多谢
作者: parris 时间: 2010-2-22 14:47
楼主 这方法太好了 终于解决这个难题了
作者: 明心瑶 时间: 2010-2-23 22:53
谢谢楼主，非常感谢！
作者: vontobe 时间: 2010-2-23 23:58
LL，用了你的方法，秒了不少余数题，谢谢分享！mua
作者: monwangmy 时间: 2010-2-24 15:32
louzi你太牛了！！
正烦恼这种题目呢
作者: louyuchen 时间: 2010-2-24 15:59
本来看寂静里面MOD还一头雾水呢~~看了这分析豁然开朗~~感谢楼主！
作者: chasedreamcc 时间: 2010-2-24 23:05
不愧是高手啊！！！
作者: dadongxiong 时间: 2010-2-25 16:13
我也曾经是数学系的啊，怎么就全都还给老师了呢。。。哎
作者: oatmas 时间: 2010-2-27 08:13
非常非常感谢呢， 赞RP
作者: xscapeout 时间: 2010-2-27 10:34
极赞 lz威武！！
作者: 纱砂美 时间: 2010-2-27 13:45
很不错，谢了～～
| 欢迎光临 ChaseDream (https://forum.chasedream.com/) |
Powered by Discuz! X3.3 |