math - モジュロ数学を剰余モジュロに還元

Question

モジュロについて助けが必要です。私は私の本でこの例を見ましたが、私の教授がどうやってそれを手に入れたのかわかりません。誰かがこれがどのように機能するかを私に説明できますか？

2 ^ 345 =（2 ^ 5）^ 69 = 32 ^ 69 = 1 ^ 69 = 1（mod 31）

=記号は合同記号です。

Answer 1

実際には、3 番目の符号のみが合同である必要があります。2^5 は確かに 32 です。すべての n に対して 1^n = 1 です。

では、なぜ 32^69 ~= 1^69 なのですか (~= を「合同」として使用)。

単純。

32 ~= 1 mod (31) =>
32 = (n*31)+1    =>
32^p = ((n*31)+1)^p
     = (n*31)^p + a*1*(n*31)^(p-1) + b*(1^2)*(n*31)^(p-1) + ... + 1^p for some a,b...
     = (n*31)*z + 1 for some z
    ~= 1 (mod 31)

したがって、一般にa ~= b (mod p)、a^n ~= b^n (mod p)