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$ である。これくらいなら暗算でもできるようになる。