modulus - 带模余数的除法

Question

你怎么能用模余数做除法？

例如：求 9^2012 除以 11 的余数。

使用模运算，9 == 1(mod 4)，所以 9^2012 == 1^2012(mod 4)。因此，9^2012 == 1(mod 4)。此外，11 == 3（模 4）。为了回答这个问题，我正在尝试做 1(mod 4)/3(mod 4)。有没有办法做到这一点？

Answer 1

有两个重要的理论可以帮助您解决这个问题：-

1. 模幂
2. 费马小定理

模幂：- 这个简单的递归公式让您理解：-

(a^n)%p = ((a^(n-1))%p*a)%p

上面的公式可以帮助您防止 a^n 很大时发生的溢出。此外，可以使用 O(logn) 完成快速指数运算

费马小定理：- 如果在你的情况下 p 是素数 11 是素数，那么(a^(p-1))%p = 1对于任何与 p 互素的 a 因此(a^n)%p = (a^(n%(p-1)))%p

你的例子： -

9^2012 % 11 = ?

11 is prime and 9 is co-prime to 11 then using fermat's theorem

9^2012 % 11 = (9^(2012%10)) % 11
2012%10 = 2

9^2012 % 11 = 9^2 % 11 = 4