阶的性质-指数定理

应用广泛的重要定理和性质。

引入（可用于求余的技巧）：

$\mathbf{证明：a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \mathbf{若b<\phi(m)：显然成立}\newline \mathbf{若b>=\phi(m)：}\newline \mathbf{b=n\phi(m)+k}\newline \mathbf{k=b(mod(\phi(m)))}\newline \mathbf{a^b\equiv a^{n\phi(m)+k}\equiv a^{n\phi(m)}\times a^{k}\space (mod\space m)}\newline \mathbf{a^{\phi(m)}\equiv1 \space (mod\space m) \space\space[欧拉定理]}\newline \mathbf{a^{n\phi(m)}\equiv1 \space (mod\space m)}\newline \mathbf{\implies a^{b}\equiv a^k\space (mod\space m)}\newline \mathbf{\implies a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \space \newline$

这种方法可以简化计算类似$7^{7^{7}}\equiv ? \space (mod \space m)$这样的问题。

阶的基本性质

指数定理

证明

$\mathbf{充分性：}\newline \mathbf{假设x\equiv y\space(mod \space \phi(m)),则x=y+k\phi(m),k\in \Zeta\space所以，}\newline \mathbf{g^x\equiv g^{y+k\phi(m)}\space mod(\space m)}\newline \mathbf{\equiv g^y(g^{\phi(m)})^k}\newline \mathbf{k=b(mod(\phi(m)))}\newline \mathbf{g^y\space mod(\space m)}\newline \mathbf{必要性可由上述引例完成证明。}\newline$