负数取模怎么算 - 简书
下载简书移动应用
写了27183字，被21人关注，获得了53个喜欢
负数取模怎么算
对于整数的取模运算，想必大家已经比较熟悉了，譬如说 7 对 3 取模，结果是多少，我们可以按照小学的公式：被除数÷除数=商……余数 来推算：7 ÷ 3 ＝ 2 ...... 1那么结果是 1。对于正整数来说，上面的计算没有问题。那么，下面的结果是多少，有人能马上回答出来吗？
在看结果之前，我们先看看整数除法的取整问题。
整数除法取整
考虑这样一个计算题：18 除以 5，要得到一个整数结果，究竟应该是 3 还是 4？这就是一个问题了。计算机上有几种对于结果取整的方法：
向上取整，向+∞方向取最接近精确值的整数，也就是取比实际结果稍大的最小整数，也叫 Ceiling 取整。这种取整方式下，17 / 10 == 2，5 / 2 == 3, -9 / 4 == -2。
向下取整，向-∞方向取最接近精确值的整数，也就是取比实际结果稍小的最大整数，也叫 Floor 取整。这种取整方式下，17 / 10 == 1，5 / 2 == 2, -9 / 4 == -3。
向零取整，向0方向取最接近精确值的整数，换言之就是舍去小数部分，因此又称截断取整（Truncate）。这种取整方式下，17 / 10 == 1，5 / 2 == 2, -9 / 4 == -2。
取模怎么算
取模运算实际上是计算两数相除以后的余数。假设 q 是 a、b 相除产生的商(quotient)，r 是相应的余数(remainder)，那么在几乎所有的计算系统中，都满足：a = b x q + r，其中 |r|&|a|。因此 r 有两个选择，一个为正，一个为负;相应的，q 也有两个选择。如果a、b 都是正数的话，那么一般的编程语言中，r 为正数；或者如果 a、b 都是负数的话，一般 r 为负数。但是如果 a、b 一正一负的话，不同的语言则会根据除法的不同结果而使得 r 的结果也不同，但是一般 r 的计算方法都会满足：r = a - (a / b) x
计算机怎么算
计算机怎么算，并不是一个好回答的问题，因为不同语言里面，对于整数除法取整的处理方式并不一样。
C/Java 的处理方式大多数语言的处理方式都与 C/Java 一致，采用了 truncate 除法。所以在 C/Java 语言中:-17 % 10 的计算结果如下：r = (-17) - (-17 / 10) x 10 = (-17) - (-1 x 10) = -717 % -10 的计算结果如下：r = 17 - (17 / -10) x (-10) = (17) - (-1 x -10) = 7-17 % -10 的计算结果如下：r = (-17) - (-17 / -10) x (-10) = (-17) - (1 x -10) = -7
Python 的处理方式Python 语言除法采用的是 floor 除法，所以对 Python 程序员来讲：-17 % 10 的计算结果如下：r = (-17) - (-17 / 10) x 10 = (-17) - (-2 x 10) = 317 % -10 的计算结果如下：r = 17 - (17 / -10) x (-10) = (17) - (-2 x -10) = －3-17 % -10 的计算结果如下：r = (-17) - (-17 / -10) x (-10) = (-17) - (1 x -10) = -7据说，Python 3.x 中「/」运算符的意义发生了变化，「/」产生的结果将不会再进行取整，相应的「//」运算符的结果才会进行取整。
Common Lisp 的处理方式Common Lisp 的特殊操作符「/」的结果是分数，因此不会存在截尾的问题。但是 Common Lisp 提供了 TRUNCATE 函数和 FLOOR 函数分别对应上述的两种除法。相应的，Common Lisp 的 REM 函数类似于 C/Java 语言中的取模运算；而 MOD 函数类似于 Python 语言中的取模运算。例如，在 Clojure 这门 Lisp 方言中，(rem -17 10) == -7，(mod -17 10) == 3
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮
被以下专题收入，发现更多相似内容：
· 0人关注
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
选择支付方式：负数究竟是如何取模的？
能不能按照正数的规则运算？如果是负数对负数取模呢
按投票排序
对于a mod b1. a mod b = a mod (-b)2. a mod b = - (-a mod b)谢邀
希望对你有帮助！！负数取模运算转自:最近带的助教班中，有人问 负数怎么取模，故上网搜了一下，感觉下面这篇帖子写得很不错，故拷过来借鉴下，原文：最近在一道 Java 习题中，看到这样的一道题：What is the output when this statement executed:
System.out.printf(-7 % 3);正整数的取余运算大家都很熟悉，但是对于负数、实数的取余运算，确实给人很新鲜的感觉。于是我对此进行了一些探索。我发现，这里面还是颇有一点可以探索的东西的。自然数的取模运算的定义是这样的（定义1）：如果a和d是两个自然数，d非零，可以证明存在两个唯一的整数 q 和 r，满足 a = qd+ r 且0 ≤ r & d。其中，q 被称为商，r 被称为余数。那么对于负数，是否可以沿用这样的定义呢？我们发现，假如我们按照正数求余的规则求 (-7) mod 3 的结果，就可以表示 -7 为 (-3)* 3 +2。其中，2是余数，-3是商。那么，各种编程语言和计算器是否是按照这样理解的呢？下面是几种软件中对此的理解。C++（G++ 编译）： cout && (-7) % 3; // 输出 -1Java（1.6）： System.out.println((-7) % 3); // 输出 -1Python 2.6：&&&
(-7) % 3 // 输出 2：(-7) mod 3 = 2：(-7) mod 3 = 2：(-7) mod 3 = -1可以看到，结果特别有意思。这个问题是百家争鸣的。看来我们不能直接把正数的法则加在负数上。实际上，在整数范围内，自然数的求余法则并不被很多人所接受，大家大多认可的是下面的这个定义2。如果a 与d 是整数，d 非零，那么余数r 满足这样的关系：a = qd + r , q 为整数，且0 ≤ |r| & |d|。可以看到，这个定义导致了有负数的求余并不是我们想象的那么简单，比如，-1 和 2 都是 (-7) mod 3 正确的结果，因为这两个数都符合定义。这种情况下，对于取模运算，可能有两个数都可以符合要求。我们把 -1 和 2 分别叫做正余数和负余数。通常，当除以d 时，如果正余数为r1，负余数为r2，那么有r1 = r2 + d对负数余数不明确的定义可能导致严重的计算问题，对于处理关键任务的系统，错误的选择会导致严重的后果。看完了 (-7) mod 3，下面我们来看一看 7 mod (-3) 的情况（看清楚，前面是 7 带负号，现在是 3 带负号）。根据定义2，7 = (-3) * (-2) + 1 或7 = (-3) * (-3) -2，所以余数为 1 或 -2。C++（G++ 编译）： cout && 7 % (-3); // 输出 1Java（1.6）： System.out.println(7 % (-3)); // 输出 1Python 2.6：&&&
输出 -2：7 mod (-3) = -2： 7 mod (-3) = -2：不支持从中我们看到几个很有意思的现象：Java 紧随 C++ 的步伐，而 Python、Google、百度步调一致。难道真是物以类聚？联想一下，Google 一直支持 Python，Python 也颇有 Web 特色的感觉，而且 Google Application Engine 也用的 Python，国内的搜索引擎也不约而同地按照 Google 的定义进行运算。可以推断，C++ 和 Java 通常会尽量让商更大一些。比如在 (-7) mod 3中，他们以 -2 为商，余数为 -1。在 Python 和 Google 计算器中，尽量让商更小，所以以 -3 为商。在 7 mod (-3) 中效果相同：C++ 选择了 3 作为商，Python 选择了 2 作为商。但是在正整数运算中，所有语言和计算器都遵循了尽量让商小的原则，因此 7 mod 3 结果为 1 不存在争议，不会有人说它的余数是-2。如果按照第二点的推断，我们测试一下 (-7) mod (-3)，结果应该是前一组语言（C++，Java）返回 2，后一组返回 -1。（请注意这只是假设）于是我做了实际测试：C++（G++ 编译）： cout && (-7) % (-3); // 输出 -1Java（1.6）： System.out.println((-7) % (-3)); // 输出 -1Python 2.6：&&&
输出 -1：-7 mod (-3) = -1： -7 mod (-3) = -1结果让人大跌眼镜，所有语言和计算机返回结果完全一致。总结时间到我们由此可以总结出下面两个结论：对于任何同号的两个整数，其取余结果没有争议，所有语言的运算原则都是使商尽可能小。对于异号的两个整数，C++/Java语言的原则是使商尽可能大，很多新型语言和网页计算器的原则是使商尽可能小。最后是拓展时间。对于实数，我们也可以定义取模运算（定义3）。当a 和 d 是实数，且d 非零, a 除以 d 会得到另一个实数（商），没有所谓的剩余的数。但如果要求商为一个整数，则余数的概念还是有必要的。可以证明：存在唯一的整数商 q 和唯一的实数 r 使得: a = qd + r, 0 ≤ r & |d|.（转自维基百科）如上在实数范围内扩展余数的定义在数学理论中并不重要，尽管如此，很多程序语言都实现了这个定义。至于哪些程序语言实现了这个定义，就留给大家自己探究吧！
已有帐号？
无法登录？
社交帐号登录mod 模运算到底是什么？
mod 模运算到底是什么？
09-03-09 &
模p运算 给定一个正整数p，任意一个整数n，一定存在等式 n = kp + r 其中k、r是整数，且 0 ≤ r & p，称呼k为n除以p的商，r为n除以p的余数。 对于正整数p和整数a,b，定义如下运算： 取模运算：a mod p 表示a除以p的余数。 模p加法：(a + b) mod p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则 (a+b) mod p = r。 模p减法：(a-b) mod p ，其结果是a-b算术差除以p的余数。 模p乘法：(a × b) mod p，其结果是 a × b算术乘法除以p的余数。 可以发现,模p运算和普通的四则运算有很多类似的规律，如： 规律 公式 结合率 ((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p ((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p 交换率 (a + b) mod p = (b+a) mod p (a × b) mod p = (b × a) mod p 分配率 ((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p 简单的证明其中第一个公式： ((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p 假设 a = k1 p + r1 b = k2 p + r2 c = k3 p + r3 a+b = (k1 + k2) p + (r1 + r2) 如果(r1 + r2) &= p ，则 (a+b) mod p = (r1 + r2) -p 否则 (a+b) mod p = (r1 + r2) 再和c进行模p和运算，得到 结果为 r1 ＋ r2 + r3的算术和除以p的余数。 对右侧进行计算可以得到同样的结果，得证。 模p相等 如果两个数a、b满足a mod p = b mod p，则称他们模p相等，记做 a ≡ b mod p可以证明，此时a、b满足 a = kp + b，其中k是某个整数。 对于模p相等和模p乘法来说，有一个和四则运算中迥然不同得规则。在四则运算中，如果c是一个非0整数，则 ac = bc 可以得出 a =b 但是在模p运算中，这种关系不存在，例如： (3 x 3) mod 9 = 0 (6 x 3) mod 9 = 0 但是 3 mod 9 = 3 6 mod 9 =6 定理（消去律）：如果gcd(c,p) ＝ 1 ，则 ac ≡ bc mod p 可以推出 a ≡ b mod p 证明： 因为ac ≡ bc mod p 所以ac = bc + kp，也就是c(a-b) = kp 因为c和p没有除1以外的公因子，因此上式要成立必须满足下面两个条件中的一个 1) c能整除k 2) a = b 如果2不成立，则c|kp 因为c和p没有公因子，因此显然c|k，所以k = ck' 因此c(a-b)kp可以表示为c(a-b) =ck'p 因此a-b = k'p，得出a ≡ b mod p 如果a = b，则a ≡ b mod p 显然成立 得证 欧拉函数 欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数的个数，记做：φ(n)，其中φ(1)被定义为1，但是并没有任何实质的意义。 定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。 显然，对于素数p，φ(p)= p -1.对于两个素数p、q，他们的乘积n = pq 满足φ(n) =(p-1)(q-1) 证明：对于质数p,q，满足φ(n) =(p-1)(q-1) 考虑n的完全余数集Zn = { 1,2,....,pq -1} 而不和n互质的集合由下面三个集合的并构成： 1) 能够被p整除的集合{p,2p,3p,....,(q-1)p} 共计q-1个 2) 能够被q整除的集合{q,2q,3q,....,(p-1)q} 共计p-1个 3) {0} 很显然，1、2集合中没有共同的元素，因此Zn中元素个数 ＝ pq - (p-1 + q- 1 + 1) = (p-1)(q-1) 欧拉定理 对于互质的整数a和n，有aφ(n) ≡ 1 mod n 证明： 首先证明下面这个命题： 对于集合Zn={x1,x2,...,xφ(n)}，考虑集合 S = {ax1 mod n,ax2mod n,...,axφ(n)mod n} 则S = Zn 1) 由于a,n互质，xi也与n互质，则axi也一定于p互质，因此 任意xi，axi mod n 必然是Zn的一个元素 2) 对于Zn中两个元素xi和xj，如果xi ≠ xj 则axi mod n ≠ axi mod n，这个由a、p互质和消去律可以得出。 所以，很明显，S=Zn 既然这样，那么 （ax1 × ax2×...×axφ(n)）mod n = （ax1 mod n × ax2mod n × ... × axφ(n)mod n）mod n = （x1 × x2 × ... × xφ(n)）mod n 考虑上面等式左边和右边 左边等于(aφ(n) × （x1 × x2 × ... × xφ(n)）mod n) mod n 右边等于x1 × x2 × ... × xφ(n)）mod n 而x1 × x2 × ... × xφ(n)）mod n和p互质 根据消去律，可以从等式两边约去，就得到： aφ(n) ≡ 1 mod n 推论：对于互质的数a、n，满足aφ(n)+1 ≡ a mod n 费马定理a是不能被质数p整除的正整数，则有ap-1 ≡ 1 mod p证明这个定理非常简单，由于φ(p) = p-1，代入欧拉定理即可证明。同样有推论：对于不能被质数p整除的正整数a，有ap ≡ a mod p 参考资料：
请登录后再发表评论!
模p运算 给定一个正整数p，任意一个整数n，一定存在等式 n = kp + r 其中k、r是整数，且 0 ≤ r & p，称呼k为n除以p的商，r为n除以p的余数。 对于正整数p和整数a,b，定义如下运算： 取模运算：a mod p 表示a除以p的余数。 模p加法：(a + b) mod p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则 (a+b) mod p = r。 模p减法：(a-b) mod p ，其结果是a-b算术差除以p的余数。 模p乘法：(a × b) mod p，其结果是 a × b算术乘法除以p的余数。 可以发现,模p运算和普通的四则运算有很多类似的规律，如： 规律 公式 结合率 ((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p ((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p 交换率 (a + b) mod p = (b+a) mod p (a × b) mod p = (b × a) mod p 分配率 ((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p 简单的证明其中第一个公式： ((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p 假设 a = k1 p + r1 b = k2 p + r2 c = k3 p + r3 a+b = (k1 + k2) p + (r1 + r2) 如果(r1 + r2) &= p ，则 (a+b) mod p = (r1 + r2) -p 否则 (a+b) mod p = (r1 + r2) 再和c进行模p和运算，得到 结果为 r1 ＋ r2 + r3的算术和除以p的余数。 对右侧进行计算可以得到同样的结果，得证。 模p相等 如果两个数a、b满足a mod p = b mod p，则称他们模p相等，记做 a ≡ b mod p可以证明，此时a、b满足 a = kp + b，其中k是某个整数。 对于模p相等和模p乘法来说，有一个和四则运算中迥然不同得规则。在四则运算中，如果c是一个非0整数，则 ac = bc 可以得出 a =b 但是在模p运算中，这种关系不存在，例如： (3 x 3) mod 9 = 0 (6 x 3) mod 9 = 0 但是 3 mod 9 = 3 6 mod 9 =6 定理（消去律）：如果gcd(c,p) ＝ 1 ，则 ac ≡ bc mod p 可以推出 a ≡ b mod p 证明： 因为ac ≡ bc mod p 所以ac = bc + kp，也就是c(a-b) = kp 因为c和p没有除1以外的公因子，因此上式要成立必须满足下面两个条件中的一个 1) c能整除k 2) a = b 如果2不成立，则c|kp 因为c和p没有公因子，因此显然c|k，所以k = ck' 因此c(a-b)kp可以表示为c(a-b) =ck'p 因此a-b = k'p，得出a ≡ b mod p 如果a = b，则a ≡ b mod p 显然成立 得证 欧拉函数 欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数的个数，记做：φ(n)，其中φ(1)被定义为1，但是并没有任何实质的意义。 定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。 显然，对于素数p，φ(p)= p -1.对于两个素数p、q，他们的乘积n = pq 满足φ(n) =(p-1)(q-1) 证明：对于质数p,q，满足φ(n) =(p-1)(q-1) 考虑n的完全余数集Zn = { 1,2,....,pq -1} 而不和n互质的集合由下面三个集合的并构成： 1) 能够被p整除的集合{p,2p,3p,....,(q-1)p} 共计q-1个 2) 能够被q整除的集合{q,2q,3q,....,(p-1)q} 共计p-1个 3) {0} 很显然，1、2集合中没有共同的元素，因此Zn中元素个数 ＝ pq - (p-1 + q- 1 + 1) = (p-1)(q-1) 欧拉定理 对于互质的整数a和n，有aφ(n) ≡ 1 mod n 证明： 首先证明下面这个命题： 对于集合Zn={x1,x2,...,xφ(n)}，考虑集合 S = {ax1 mod n,ax2mod n,...,axφ(n)mod n} 则S = Zn 1) 由于a,n互质，xi也与n互质，则axi也一定于p互质，因此 任意xi，axi mod n 必然是Zn的一个元素 2) 对于Zn中两个元素xi和xj，如果xi ≠ xj 则axi mod n ≠ axi mod n，这个由a、p互质和消去律可以得出。 所以，很明显，S=Zn 既然这样，那么 （ax1 × ax2×...×axφ(n)）mod n = （ax1 mod n × ax2mod n × ... × axφ(n)mod n）mod n = （x1 × x2 × ... × xφ(n)）mod n 考虑上面等式左边和右边 左边等于(aφ(n) × （x1 × x2 × ... × xφ(n)）mod n) mod n 右边等于x1 × x2 × ... × xφ(n)）mod n 而x1 × x2 × ... × xφ(n)）mod n和p互质 根据消去律，可以从等式两边约去，就得到： aφ(n) ≡ 1 mod n 推论：对于互质的数a、n，满足aφ(n)+1 ≡ a mod n 费马定理a是不能被质数p整除的正整数，则有ap-1 ≡ 1 mod p证明这个定理非常简单，由于φ(p) = p-1，代入欧拉定理即可证明。同样有推论：对于不能被质数p整除的正整数a，有ap ≡ a mod p
请登录后再发表评论!
MOD是取模运算，例如求8的模运算，所得的结果就可看作八进制数的基类数字0-7， 如:6mod8=6,9mod8=1,8mod8=0    也就是取余运算
请登录后再发表评论!
请登录后再发表评论!&&&&大数取模运算y=g^a mod n 其中n为不小于1024比特的整数
大数取模运算y=g^a mod n 其中n为不小于1024比特的整数
给出一个高效程序计算模指数运算y=g^a mod n，其中n为不小于1024比特的整数
若举报审核通过，可奖励20下载分
被举报人：
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：
VIP下载&&免积分60元/年（1200次）
您可能还需要
课程资源下载排行