【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《关于求余数问题的一个简单方法》，欢迎阅读！
WORD格式 关于求余数问题的一个简单方法-增强版 个人建议：在您看这份文档的同时，准备一支笔，一 张草稿纸。如果看到例题，跟我的步骤，一步一步地 同时写下来，这样比光看屏幕，要理解得更快！ 我在自己的讨论稿文档里，求余的时候，都会用到mod这个运算符。 mod：模。意思就是求余数。 比如说：5mod3=2，100mod11=1 读作：五模三余二，一百模十一余一 这是标准的公式化写法，大家可能不太熟悉，但是知道意思了，其实也很简单。 引入Mod，主要是可以用数学公式来写，而且可以把求余数的问题化简成为普通 的四则运算的问题，也比较容易表达。 在讲如何求余之前，先来普及一下余数的一些性质。 首先就是余数的加减法：比如说100除以7余2，36除以7余1。那么100+36 除以7余几呢？或者100-36除以7余几呢？很显然，只要用100除以7的余数 2与36除以7的余数1进行加减就可以得到答案。通过这个例子可以很明显的 看出来，余数之间是可以加减的。 总结写成书面的公式的话，就是：(M＋N)modq=(（Mmodq）+（Nmodq）)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^4mod9=?11^4mod9=(9+2)^4mod9=2^4mod9=16mod9=7 于是我们可以总结出这样的公式：专业资料整理 WORD格式 M*Nmodq=（Mmodq）*（Nmodq）modq （M^nmodq=（Mmodq）^nmodq） 那么，我们知道了这些性质之后对解题又有什么帮助呢？ Asweallknow，如果一个数乘以1，还是等于原数；而1的任意次方，还是等 于1。 所以在解答这一类的问题的时候，只要我们尽量把计算中的余数凑成与1相关的 乘式，结果显然会好算很多的。（或者-1，2之类的比较容易进行计算的数字都 可以，因题而异。） 举例说明：求3^11除以8的余数。题目即是：3^11mod8=? 3^11mod8 =3^10*3^1（mod8） =(3^2)^5*(3^1)（mod8） =9^5*3（mod8） =(8+1)^5*3（mod8） =1^5*3（mod8）=3 发现没有，甚至没有去计算什么尾数的规律，答案就算出来了，而且只用了加减 乘除。 那么再来看一道题目：求（2^100）*（3^200）除以7的余数 先化成计算公式： (2^100)*(3^200)mod7 =[2^(3*33+1)]*[3^(3*66+2)]mod7=[(2^3)^33*2]*[(3^3)^66*3^2]mod7 =(8^33*2)*(27^66*9)mod7=[(7+1)^33*2]*[(28-1)^66*9]mod7=(1^33*2)*[(-1)^66*9]mod7 =2*9mod7 =4 注意：如果余数有负号，就当做负数一样计算。 我步骤写得很详细，但其实只要是熟练了，基本上只要三四步答案一定就出来了， 有没有觉得很简单呢？赶紧找一两题来练练手吧，甚至随便写几个数字来做做试 试看，像我上面的例题都是临时编的。 相信只要练习了三四道题目，以后再碰到这样的余数题，就会会心地一笑：小 样，秒掉你！ 专业资料整理 本文来源：https://www.dywdw.cn/b051f7f830d4b14e852458fb770bf78a64293a52.html
下载此文档
搜索文档
阅读：
文档下载
2023-01-19
