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

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

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。

合同式とは

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

早期退職後にtwitterで「合同式」について学ぶ

SNSがあれば学校に行かなくても数学が学べるいい時代になった。 最近は「合同式」の知識を身につけた。 「合同式」は中学・高校の数...

soutai40.com