163^57 mod 97

${163}^{57}$ を $97$ で割った余りを計算する。

$163$ は $97$ を法として、$-128$ と合同である。よって、${163}^{57}$ は $(-128{)}^{57}=(-2{)}^{399}$ と $97$ を法として合同である。このとき、Fermatの小定理より、$(-2{)}^{96}$ は $97$ を法として $1$ と合同であるため、$(-2{)}^{399}$ は $97$ を法として $(-2{)}^{15}$ と合同である。ここで、$(-2{)}^{10}=1024$ は $97$ を法として $54=3\times 18$ と合同である。したがって $(-2{)}^{15}$ は $-32\times 3\times 18=(-96)\times 18$ と法 $97$ で合同であり、したがって $18$ と合同である。

よって ${163}^{57}$ を $97$ で割った余りは $18$ である。これくらいなら暗算でもできるようになる。