math - 模数学减少到余数模

Question

我需要一些关于模数的帮助。我在我的书中看到了这个例子，但不明白我的教授是如何得到它的。有人可以向我解释这是如何工作的吗？

2^345 = (2^5)^69 = 32^69 = 1^69 = 1 (mod 31)

= 符号是全等符号。

Answer 1

只有第三个符号需要全等，实际上：2^345 = (2^5)^69 (因为 n^(a*b) == (n^a)^b); 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)