数IAIIB東京都立大高校数学の解法

東京都立大2017文系第4問 2 つの数が互いに素であることを背理法で証明する問題


数列 $\{a_n\}$ を次の条件によって定める。
$a_1=1$,$a_2=2$,$a_{n+2}=2a_{n+1}+a_n$ $(n=1,2,3,\cdots)$
以下の問いに答えなさい。(東京都立大2017)
(1) $a_3$,$a_4$,$a_5$ を求めなさい。
(2) $x,y$ についての 1 次不定方程式 $a_5x+a_4y=1$ の整数解をすべて求めなさい。
(3) すべての自然数 $n$ に対して,$a_n$ と $a_{n+1}$ が互いに素であることを示しなさい。

ad

式に代入する

(1)から始めます。ここは単に代入するだけです。
$a_{n+2}=2a_{n+1}+a_n$ より
$a_3=2a_2+a_1$
$=2\cdot2+1=5$
$a_4=2a_3+a_2$
$=2\cdot5+2=12$
$a_5=2a_4+a_3$
$=2\cdot12+5=29$
(答え)

ad

互除法で不定方程式を解く

(2)に進みます。
$a_5x+a_4y=1$
$29x+12y=1$
となるので,互除法を用いて不定方程式を解きます。
$29=12\cdot2+5$
$12=5\cdot2+2$
$5=2\cdot2+1$
辺々を移項して
$5=29-12\cdot2$
$2=12-5\cdot2$
$1=5-2\cdot2$
ここから下から上に向かって式を置き換えていきます。

互除法,途中で分からなくなる。

上の値で式を置き換えることを意識しながら整理するのがコツ。実際やり方見てみて。

$1=5-2\cdot2$
上の式の左辺が 2 なので,それで置き換えて整理します。
$=5-2(12-5\cdot2)$
カッコを展開します。このとき,もう一つ上の式の左辺は 5 だから,5 という数字を残すように式を整理します。
$=5-2\cdot12+5\cdot4$
$=5\cdot5-2\cdot12$
上の式で 5 を置き換えます。
$=5(29-12\cdot2)-2\cdot12$
ゴール地点は $29x+12y$ の係数,29 と 12 です。よって,29 と 12 を残すように式を整理します。
$=29\cdot5-12\cdot10-12\cdot2$
$=29\cdot5-12\cdot12$
式どうしを引き算すると
$\begin{aligned}29x&+12y&=1\\-)\space29\cdot5&+12\cdot(-12)&=1\\\hline29(x-5)&+12(y+12)&=0\end{aligned}$
$29(x-5)=-12(y+12)$ ・・・①
29 と 12 は互いに素だから,$x-5$ は 12 の倍数である。$k$ を整数として
$x-5=-12k$
$x=5-12k$
①に代入して
$29(5-12k-5)=-12(y+12)$
$-12\cdot29k=-12(y+12)$
$29k=y+12$
$y=29k-12$
したがって
$\begin{cases}x=5-12k\\y=29k-12\end{cases}$
(答え)

ad

背理法を用いる

(3)に進みます。
ここは背理法を用います。
いったん $a_n$ と $a_{n+1}$ が互いに素ではないと仮定して,それが矛盾することから,$a_n$ と $a_{n+1}$ が互いに素であることを証明します。
2 つの数が互いに素でないとき,その 2 つの数には共通して割ることのできる数があります。つまり,公約数が存在するということです。
たとえば,15 と 6 は互いに素ではありません。これは互いに 3 で割ることができるからです。言い換えれば 3 という公約数が存在するということです。
逆に,さきほど登場した 29 と 12 は互いに素です。これは,1 以外に共通して割ることのできる数は存在しません。このような 2 つの数を互いに素と呼びます。
背理法で証明してみましょう。
$a_n$ と $a_{n+1}$ が互いに素でないと仮定して,$a_n$ と $a_{n+1}$ の公約数を $c$ とすると
$a_n$ と $a_{n+1}$ は $c$ の倍数である。
$a_n=cp$,$a_{n+1}=cq$ とすると
問題文より $a_{n+2}=2a_{n+1}+a_n$ だから
$a_{n+2}=2cq+cp=c(2q+p)$
となり,$a_{n+2}$ も $c$ の倍数である。
よって,数学的帰納法より,$a_1$ と $a_2$ が互いに素ではないなら,すべての自然数 $n$ に対して,$a_n$ と $a_{n+1}$ は互いに素ではないことになり,矛盾する。
$a_1=1$,$a_2=2$ だから,これは互いに素になってる。だから矛盾する。
したがって,すべての自然数 $n$ に対して,$a_n$ と $a_{n+1}$ は互いに素である。(証明終わり)

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