【合同式】7の123乗を100で割った余り

「7の123乗を100で割った余りは？」という慶應義塾高校の入試問題を解いてみた。

「7の123乗」といえば7を123回掛けないといけないので、まともに計算するのは不可能。

合同式を使えば、簡単に解ける。

答案

mod 100で考える。

7²≡49

7³≡343≡43

7⁴≡43 × 7 = 301 ≡ 1

これで、7⁴を100で割った余りが1であることがわかった。

余りを求める

7¹²³=(7⁴)³⁰×7³≡1³⁰×43≡43

よって、7の123乗を100で割った余りは43。