模数为负数

Question

请考虑以下表达式:

(a - b) mod N

以下哪一项相当于上述表达式？

1) ((a mod N) + (-b mod N)) mod N

2) ((a mod N) - (b mod N)) mod N

另外,如何计算(-b mod N),即如何计算负数的mod？

谢谢.

Answer 1

我不想用一些复杂的数学概念来打扰你,所以我会尽量保持简单.当我们说a = b(mod c)时,我们只是说ab是c的倍数.这意味着当我们想要知道mod c的值是什么时,说它是a或ac或+ c或a + 1000*c是真的.因此,您的2个公式是有效的.

但你想要的是知道计算机给你的答案,对吧？嗯,这取决于您使用的语言.以Java为例,mod b的符号为a,其绝对值严格低于b.这意味着a = 7,b = 3且N = 5,(ab)%N = 4,但是你的两个表达式将返回-1.

如果你想用模数做算术,我建议你做的是创建你自己的mod函数,所以它总是给你一个正整数.这样,您的2个表达式将始终等于原始表达式.

这里以伪代码为例:

function mod (int a, int N)
  return (a%N+N)%N