模量餘量分區

Question

如何分配餘量模數？

例如：查找餘量時9^2012由11

使用模算術劃分，9 == 1（mod 4）時，那麼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很大。如果p是你的情況主要11是素數，那麼(a^(p-1))%p = 1任何一個是互質數，爲P，因此(a^n)%p = (a^(n%(p-1)))%p

- ： 而且快速exponention可以使用O（LOGN）

費馬小定理來完成你的例子： -

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