【合同式】1997^1997を9で割った余り

久しぶりに数学の問題を解いてみた。

ネットで見つけた「1997^1997を9で割った余りを求めよ」という問題だ。

参照数2のに二項定理の問題です!1997^1997を9で割った余りを求めよ。（Yahoo!知恵袋）

上記の「Yahoo!知恵袋」では、二項定理を使った解法が紹介されていた。

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

答案

「1997の1997乗」は超巨大な数字だ。

「9で割った余り」なんて、まともに計算して解くことはできない。

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

まず、1997を9で割った余りをふつうに計算して求める。

余りは8なので、合同式で表すと、

1997 ≡ 8 (mod 9)

8を9で割った余りは「8」だが「-1」とも言えるので、

1997 ≡ -1 (mod 9)

これで9割は解けた。

最終解答

両辺を1997乗する。

1997¹⁹⁹⁷ ≡ -1¹⁹⁹⁷ = -1　

1997¹⁹⁹⁷ ≡ -1 ≡ 8 (mod 9)

よって、求める余りは8。