フェルマーのリトル定理

Fermat's Little Theoremを使って、以下をどのように計算しますか？フェルマーのリトル定理

2^1,000,006 mod 101 
2^-1,000,005 mod 11

2009-05-19 jinsungy

普通の宿題の質問を投稿するのではなく、これを解決しようとした方法と問題がどこにあるのか、いくつかの情報を追加することができます。 – sth

質問の妥当性についてUpvoted。コアプロセスを理解できない場合、この問題を「開始」する方法はありません。おおよそ2つのステップですから、どうやって「開始」するのか説明してください。 –

2番目の式に負の符号があるのはなぜですか？誰か説明してください、それは私には意味がありません。 – Unknown

は、あなたが知っている^（P-1）=== 1のmod P、そう...

2^10 === 1つのmod 11
2 ^（ - 1000005）= 2 ^（ - 1,000,000）* 2 ^（ - 5）= 1 * 2 ^（-5）= 2 ^（-5）* 2 ^（10）= 32 mod 11 = -1 = 10

大きな数字をどうやって使うのが見えますか？プロセスは同じです。

これはすべてFLTです。混乱した。（それぞれ）を

2009-05-19 23:36:21

2^-5 === 2^6（mod 11）。 –

ええ、間違いなくこの（または少なくとも悪い記法）のいくつかのエラーがあります。修正する必要がありますが、どこから始めるべきかわかりません。 – Noldorin

したがって2^1,000,006 mod 101 ... 2^1,000,000 * 2^6 = 1 * 32 = 32 mod 101 = -5？ – jinsungy

101及び11が素数であるので、^ 100 2及び2^10は1 MOD 101に合同であり、11

2^100及び2 ^換算で2^1000006を表現しようとし2^10の点で-1000005です。それぞれの問題を簡単に計算できるものに減らすことができるはずです。

2009-05-19 23:37:18

これは行く方法と思われる。加えて、OPだけをガイドするので、良い答えです。 – Noldorin

答えて