休校だからこそ重要な自宅学習

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

2017年 秋田大 余りに関する入試問題数学IAIIB
スポンサーリンク
自然数 $m$ の $n$ 乗を素数で割った余りに関する問題の説明をします。
 
余りを並べると周期性があることが分かりますが,フェルマーの定理を知っているとどの程度調べれば良いのかを予め把握することができます。
 
知識があることによって,問題を解くときの不安がなくなるため,他の受験生より有利になることは間違いないでしょう。

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

スポンサーリンク

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*}
ヒロ
ヒロ

次の記事でも触れているが,2桁の11倍の計算を素早くできるようにしておこう。

【2桁の11倍】
 例えば $43\times11$ を計算するときは間を空けて「4 3」と書いて,空けた間には4と3の和7を書いて
\begin{align*}
43\times11=473
\end{align*}
と計算することができる。
 各位の数の和が10以上になるときは,十の位に1を加えて書くようにしよう。例えば $58\times11$ を計算するときは「6 8」と書いて,空けた間には6と8の和13の一の位3を書いて
\begin{align*}
58\times11=638
\end{align*}
と計算することができる。

(3)の考え方と解答

ヒロ
ヒロ

(1)と(2)を解けた人へのボーナス問題になるね。

ヒロ
ヒロ

簡単な不定方程式だから,解き方を知っていれば,(1)(2)を解けなかった人との差を広げることができる。

【(3)の解答】
(1),(2)より,求める $n$ は $n=10k+6=16\ell+4$ を満たす $n$ である。
この関係式より
\begin{align*}
&8\ell-5k=1 \\[4pt]
&8(\ell-2)-5(k-3)=0
\end{align*}
8と5は互いに素であるから,$\ell-2$ は5の倍数で,$k-3$ は8の倍数である。よって
\begin{align*}
\ell-2=5m~(m~は0以上の整数)
\end{align*}
とすると
\begin{align*}
&8\Cdota5m=5(k-3) \\[4pt]
&k-3=8m \\[4pt]
&k=8m+3
\end{align*}
したがって,求める $n$ の値は次のようになる。
\begin{align*}
&n=10(8m+3)+6 \\[4pt]
&n=80m+36~(m~は0以上の整数)
\end{align*}

まとめ

ヒロ
ヒロ

余りを並べると周期数列になることを知っていたとしても,周期がどの程度なのかを知らずに,コツコツと調べるのは大変である。

ヒロ
ヒロ

フェルマーの小定理を知っておくことで「最悪ここまで調べれば大丈夫だ」と分かるため,どこまで調べれば良いのか分からない不安な状態は解消されるだろう。

ヒロ
ヒロ

とはいえ,頑張って計算しなければならない点は変わらないため,間違えないように落ち着いて計算できるようにしておこう。

タイトルとURLをコピーしました