[高校数学]「互いに素」を示すには？2023年度早稲田理工[Ⅰ]を解説！

みなさんこんにちは、Yutaです。

これまで中学数学を中心に解説してきましたが、大学入試の数学について解説を始めることにしました。

ぜひ今後ともよろしくお願いいたします。

今回は、2023年度に早稲田理工で出題された[Ⅰ]を解説していきます。

この問題は東大でも類題が出題されるなど、有名な問題であります。

整数問題でよく用いられる考え方が詰まった良問ですので、ぜひ挑戦してみてください。

問題の概要
(1)の解説
(2)の解説
1. 実験して、規則性を見つけ出す
2. 仮説を証明する
(3)の解説
1. 問題の誘導に乗ってみる
2. 「互いに素」であることを示すには？
まとめ：[高校数学]「互いに素」を示すには？2023年度早稲田理工[Ⅰ]を解説！

問題の概要

問題の概要は以下の通りです。

\(n\)を自然数として, 整式\((3x+2)^n\)を\(x^2+x+1\)で割った余りを\(a_nx+b_n\)とおく。以下の問に答えよ。
(1)\(a_{n+1},b_{n+1}\)を\(a_n,b_n\)を用いて表せ。
(2)全ての\(n\)に対して, \(a_n,b_n\)は7で割り切れないことを示せ。
(3)\(a_n,b_n\)を\(a_{n+1},b_{n+1}\)で表し,全ての\(n\)に対して, 2つの整数\(a_n,b_n\)は互いに素であることを示せ。

(1)の解説

ひとまず、\((3x+2)^n\)を\(x^2+x+1\)で割ったときの商を\(Q_n(x)\)とおきます。

そうすると、\((3x+2)^n=(x^2+x+1)Q_n(x)+a_nx+b_n\)…①が成り立ちます。

いま、\(a_{n+1}x+b_{n+1}\)について考えたいわけなのですが、

これらは\((3x+2)^{n+1}\)を\(x^2+x+1\)を割ったときの余りとなります。

そこで、①を利用して無理やり\((3x+2)^{n+1}\)を作り出します。

①の両辺に\((3x+2)\)をかけることにより、

\begin{eqnarray}
(3x+2)^{n+1}&=&(3x+2)(x^2+x+1)Q_n(x)+(3x+2)(a_nx+b_n)\\
&=&(3x+2)(x^2+x+1)Q_n(x)+3a_nx^2+(2a_n+3b_n)x+2b_n…②
\end{eqnarray}

を得ます。

ところで、\(3a_nx^2+(2a_n+3b_n)x+2b_n\)は2次式なので、\(x^2+x+1\)で割ることができます。

実際に割り算を実行してみると、

\(3a_nx^2+(2a_n+3b_n)x+2b_n=3a_n(x^2+x+1)+(3b_n-a_n)x+2b_n-3a_n\)…③を得ます。

③を②に代入し、

\begin{eqnarray}
(3x+2)^{n+1}&=&(3x+2)(x^2+x+1)Q_n(x)+3a_nx^2+(2a_n+3b_n)x+2b_n\\
&=&(x^2+x+1)\{(3x+2)Q_n(x)+3a_n\}+(3b_n-a_n)x+2b_n-3a_n
\end{eqnarray}

となります。

\((3b_n-a_n)x+2b_n-3a_n\)こそが\(a_{n+1}x+b_{n+1}\)となるので、

\begin{cases}
a_{n+1}=-a_n+3b_n…③\\
b_{n+1}=-3a_n+2b_n…④
\end{cases}

が答えとなります。

(2)の解説

実験して、規則性を見つけ出す

整数問題で行き詰ったときは、

具体的な数値を代入して実験することによって、規則性を見つけ出す

ということを覚えておきましょう。

というわけで、\(a_2,b_2,a_3,b_3\)の値を(1)の結果を用いて求めてみましょう。

\((a_1,b_1)=(3,2)\)ですから、\((a_2,b_2)=(3,-5),(a_3,b_3)=(-18,-19)\)となります。

ところで、

\(K,M\)を整数、\(N\)を自然数、\(r\)を0以上\(N\)未満の整数とするとき、\(K=MN+r\)が成り立つとする。
このとき、\(r\)を\(K\)を\(N\)で割ったときの余りと定義する。

という「除法の原理」一般にが知られています。

いまの場合、まず\(b_2\)に関して、\(-5=7×(-1)+2\)となって、7で割った余りは2です。

\(a_3\)に関して、\(-18=7×(-3)+3\)となって、7で割った余りは3です。

\(b_3\)に関して、\(-19=7×(-3)+2\)となって、7で割った余りは2です。

以上から、何か規則性が見えてきませんか？

\(a_n\)を7で割った余りは3で、\(b_n\)を7で割った余りは2である

という仮説が立ちます。

これが正しいことを以下では証明していきましょう。

仮説を証明する

今回のような命題の証明については、

「すべての自然数\(n\)に対する」命題を証明したいときは、数学的帰納法を用いる

とよいことをぜひ覚えておきましょう。

この証明にあたっては、合同式を用いると便利なのでこれを利用してやっていきます。

合同式の定義および性質については、こちらのページで解説しております。

(証明)
すべての正の整数\(n\)に対して,\(\mod 7\)として,
\begin{cases}
a_{n}\equiv 3\\
b_{n}\equiv 2
\end{cases}
となることを数学的帰納法を用いて示す。なお,以下合同式はすべて\(\mod 7\)である。
(Ⅰ)\(n=1\)のとき,\((a_1,b_1)=(3,2)\)となるため, 成立。
(Ⅱ)\(n=k\)(\(k\):正の整数)のとき,成立を仮定すると,
\begin{cases}
a_{k+1}\equiv -a_k+3b_k \equiv 3\\
b_{k+1}\equiv -3a_k+2b_k \equiv -5 \equiv 2
\end{cases}
となって,\(n=k+1\)のときも成立。
以上より, すべての正の整数\(n\)に対して,\(a_{n}\equiv 3,b_{n}\equiv 2\)が成り立つ。
よって, \(a_{n},b_{n}\)は7で割り切れない。
(Q.E.D.)

(3)の解説

問題の誘導に乗ってみる

いよいよ、本題である(3)の解説に入ります。

問題文に「\(a_n,b_n\)を\(a_{n+1},b_{n+1}\)で表せ」とあるので、実際にやってみます。

③・④を\(a_n,b_n\)に関する連立方程式だとみなして解いてみると、

\begin{cases}
a_{n}=\dfrac{2a_{n+1}-3b_{n+1}}{7}…⑤\\
b_{n}=\dfrac{3a_{n+1}-b_{n+1}}{7}…⑥
\end{cases}

となります。

ここまではすんなりといけますが、ここからどのようにして証明をしていけばよいのでしょうか。

「互いに素」であることを示すには？

ここでポイントです。

2つの整数が「互いに素」であることを示すには、背理法を用いる
→2つの整数が素因数\(p\)を持つことを仮定して、矛盾を導く

ことが基本です。

今回は、先ほどの⑤・⑥を利用したいので、「\(a_{n+1},b_{n+1}\)が素因数\(p\)を持つこと」を仮定します。

そうすると、整数\(x_{n+1},y_{n+1}\)を用いて、

\begin{cases}
a_{n+1}=px_{n+1}\\
b_{n+1}=py_{n+1}
\end{cases}

と表すことができます。

これらを⑤・⑥に代入して、

\begin{cases}
a_{n}=\dfrac{2px_{n+1}-3py_{n+1}}{7}=\dfrac{2x_{n+1}-3y_{n+1}}{7}p…⑦\\
b_{n}=\dfrac{3px_{n+1}-py_{n+1}}{7}=\dfrac{3x_{n+1}-y_{n+1}}{7}p…⑧
\end{cases}

となります。

ここで(2)の結果を用いると、\(p\neq7\)であり、\(a_n,b_n\)は整数ですから、

\(\displaystyle \frac{2x_{n+1}-3y_{n+1}}{7},\frac{3x_{n+1}-y_{n+1}}{7}\)も整数となります。

よって、\(a_n,b_n\)も素因数\(p\)を持つことになります。

同様の操作を繰り返し行ってゆくと、\((a_{n-1},b_{n-1}),(a_{n-2},b_{n-2}),…(a_2,b_2),(a_1,b_1)\)いずれの2つの整数の組についても素因数\(p\)をもつことになります。

しかし、\((a_1,b_1)=(3,2)\)は互いに素なので、矛盾します。

よって、背理法によって命題が正しいことが証明できます。

以下、解答例です。

(証明)
\(a_{n+1},b_{n+1}\)が素因数\(p\)を持つことを仮定する。
このとき,整数\(x_{n+1},y_{n+1}\)を用いて,

\begin{cases}
a_{n+1}=px_{n+1}\\
b_{n+1}=py_{n+1}
\end{cases}

と表すことができる。
そうすると,
\begin{cases}
a_{n}=\dfrac{2px_{n+1}-3py_{n+1}}{7}=\dfrac{2x_{n+1}-3y_{n+1}}{7}p\\
b_{n}=\dfrac{3px_{n+1}-py_{n+1}}{7}=\dfrac{3x_{n+1}-y_{n+1}}{7}p
\end{cases}
となる。
(2)より\(p\neq7\)であり,\(a_n,b_n\)は整数であるから,\(\displaystyle \frac{2x_{n+1}-3y_{n+1}}{7},\frac{3x_{n+1}-y_{n+1}}{7}\)も整数となる。
よって, \(a_n,b_n\)も素因数\(p\)を持つことが分かる。
同様の操作を繰り返してゆくと,\((a_{n-1},b_{n-1}),(a_{n-2},b_{n-2}),…(a_2,b_2),(a_1,b_1)\)いずれの2つの整数の組についても素因数\(p\)をもつことがいえる。
しかし,\((a_1,b_1)=(3,2)\)が互いに素であることに矛盾する。
よって,\(a_{n+1},b_{n+1}\)は互いに素である。
したがって,\(a_n,b_n\)も互いに素であるといえる。
(Q.E.D.)

このように、整数列に関する整数問題では、