【合同式】nを5で割った余りが3であるとき、n^30を5で割った余り

数学

2022.08.24

ネットでこんな問題を見つけた。

nは整数とする。nを5で割った余りが3であるとき、n^30を5で割った余りを求めよ。

出典Clearnote「n^30を5で割ったあまりは3^30を5で割った余りに等しいとなるのはなぜですか？」

わたしは「合同式」で解いてみた。

答案

「nを5で割った余りが3」なので、合同式で表すと、

n ≡ 3 (mod 5)

合同式の法則より、両辺を30乗すると、

n³⁰ ≡ 3³⁰ (mod 5)　

ここで、3の何とか乗の余りが1であるケースを探す。

3⁴ = 81 を5で割ると1余る。

つまり、

3⁴ ≡ 1 (mod 5)

よって、

n³⁰ ≡ 3³⁰ = (3⁴)⁷ × 3²　≡ 1⁷ × 3² ≡ 9

となる。

n³⁰を5で割った余りは9を5で割った余りと等しいので、

答えは4。

合同式については次の記事を参照してほしい。