余りに関する入試問題【2017年 秋田大】

自然数 $m$ の $n$ 乗を素数で割った余りに関する問題の説明をします。

余りを並べると周期性があることが分かりますが，フェルマーの定理を知っているとどの程度調べれば良いのかを予め把握することができます。

知識があることによって，問題を解くときの不安がなくなるため，他の受験生より有利になることは間違いないでしょう。

ということで，今回扱う問題は2017年の秋田大の問題です。

Contents

1 2017年秋田大
2 まとめ

2017年秋田大

ヒロ

とりあえず解いてみよう。

2017年秋田大　$n$ を自然数とする。次の問いに答えよ。
(1) $8^n$ を11で割った余りが3となる $n$ をすべて求めよ。
(2) $11^n$ を17で割った余りが4となる $n$ をすべて求めよ。
(3) (1)の条件と(2)の条件を同時に満たす $n$ をすべて求めよ。

(1)の考え方と解答

ヒロ

2019年秋田大のような問題では，フェルマーの小定理を知っておくと，少しだけ気が休まる。

フェルマーの小定理$p$ が素数で，$a$ と $p$ 互いに素であるとき

\begin{align*}
a^{p-1}\equiv1\pmod{p}
\end{align*}

が成り立つ。

ヒロ

このフェルマーの小定理から分かることは，$a^p$ を $p$ で割ったときの余りは，$a$ を $p$ で割った余りに等しいということだね。

ヒロ

周期が $p-1$ ということは分かるけど，基本周期とは限らないことに注意しよう。

【$p-1$ が基本周期にならない例】
7は素数であり，2と7は互いに素であるから，フェルマーの小定理より

\begin{align*}
2^6\equiv1~\pmod{7}
\end{align*}

が成り立つ。6が周期であることが分かるが，それより小さい周期があるかもしれない。実際に2の累乗を7で割ったときの余りを調べると次のようになる。

\begin{align*}
&2\equiv2 \\[4pt]
&2^2\equiv4 \\[4pt]
&2^3=8\equiv1 \\[4pt]
\end{align*}

よって，この場合は周期は3である。
3つ調べて周期になってなければ，周期は6だなということも分かる。
そうならなければ途中の計算が間違っていることも分かる。

ヒロ

(1)では，11が素数で8と11が互いに素であるから，周期が10であることが分かる。

ヒロ

つまり，8と $8^{11}$ は11で割ったときの余りが等しいことが分かる。

【(1)の解答】
11を法とした合同式で考える。

\begin{align*}
&8\equiv8 \\[4pt]
&8^2=64\equiv9 \\[4pt]
&8^3\equiv72\equiv6 \\[4pt]
&8^4\equiv48\equiv4 \\[4pt]
&8^5\equiv32\equiv10 \\[4pt]
&8^6\equiv80\equiv3 \\[4pt]
&8^7\equiv24\equiv2 \\[4pt]
&8^8\equiv16\equiv5 \\[4pt]
&8^9\equiv40\equiv7 \\[4pt]
&8^{10}\equiv56\equiv1 \\[4pt]
\end{align*}

よって，余りの周期は10であり，余りが3になる $n$ の値は

\begin{align*}
n=10k+6~(k~は0以上の整数)
\end{align*}

(2)の考え方と解答

ヒロ

(1)と同じように考えると，17で割っているから周期は最長でも16だと分かる。

ヒロ

頑張って調べていこう。

【(2)の解答】
法を17とした合同式で考える。

\begin{align*}
&11\equiv11~~~11^2\equiv2~~11^3\equiv5~~11^4\equiv4 \\[4pt]
&11^5\equiv10~~11^6\equiv8~~11^7\equiv3~~11^8\equiv16 \\[4pt]
&11^9\equiv6~~~11^{10}\equiv15~~11^{11}\equiv12~~11^{12}\equiv13 \\[4pt]
&11^{13}\equiv7~~~11^{14}\equiv9~~11^{15}\equiv14~~11^{16}\equiv1
\end{align*}

よって，余りの周期は16であり，余りが4 $n$ の値は

\begin{align*}
n=16\ell+4~(\ell~は0以上の整数)
\end{align*}