0

モジュラス剰余で除算を行うにはどうすればよいですか?

例: 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) をしようとしています。これを行う方法はありますか?

4

1 に答える 1

1

この問題を解決するのに役立つ2つの重要な理論があります:-

  1. 累乗剰余
  2. フェルマーの小定理

剰余累乗 :- この単純な再帰式を理解してもらう:-

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

上記の式は、a^n が大きい場合に発生するオーバーフローを防ぐのに役立ちます。さらに、O(logn)を使用して高速指数を実行できます

フェルマーの小定理 :- p が素数の場合、11 が素数である場合、p に互いに素(a^(p-1))%p = 1な任意の 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  
于 2014-04-16T05:06:38.577 に答える