模余数除法

Question

你怎么能用模余数除法？

例如:当9^2012除以11时，查找剩余部分。

采用模块化算法，9 == 1(mod 4)，so 9^2012 == 1^2012(mod 4)。因此，9^2012 == 1(mod 4)。11 == 3(mod 4)。为了回答这个问题，我尝试做1(mod 4)/3(mod 4)。有办法这样做吗？

Answer 1

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

1. 模指数
2. 费马小定理

模幂:-这个简单的递归公式让你明白:-

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

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

费马的小定理:-如果p是素数在你的例子中11是素数，那么对于对p是次素数的任意a，(a^(p-1))%p = 1，(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