79^83 mod 89

$79^{83}$ を $89$ で割った余りを計算する。以下法 $89$ で考える。

$79^{83}=(-10)^{-5}=(100^2\times (-10))^{-1}=(121\times(-10))^{-1}$ が成り立つ。ここで、$44^{-1}=-2$ であることに注意すると、$(121\times 16)^{-1}=4$ が成り立つ。よって、$(-1210)^{-1}=(-121\times 16)^{-1}\times 5^{-1}\times 8=4\times 8\times 5^{-1}=4\times 8\times 18=30\times 18+36=6\times 90+36=6+36=42$ が成り立つ。従って $79^{83}=42$ である。