modulus - 合同な整数と法

Question

私はここのトピックに不慣れです：/誰かが以下を解決する方法を教えてもらえますか？36 ^ 2004 + 17 ^ 768 x 27 ^ 412が19で割り切れることを示します。ありがとう！

Answer 1

単純なIDを使用して上記を解決できますが、重要なのは次のとおりです。

(a + b) mod c = a mod c + b mod c

また、

ab mod c = (a mod c)*(b mod c)

これは、たとえば次のように解く場合にも、非常に大きな指数を解くために使用できます。

24^3100 mod 19

あなたはおそらくそれを次のように分割することができます：

24^(310*100) mod 19

これはさらに次のように書くことができます：

24^310 mod 19 x 24^100 mod 19

さらに、実際に計算して解決できる値に分解できます。たとえば、100を分解し続けると、解決する可能性があります

(24^4 mod 19)^25

などなど。これは宿題の質問なので、私はヒントを提供することしかできず、完全な解決策を提供することはできません。

また、指数が2の累乗で表される高速べき乗法でも実行できます。