2 つの数が互いに素であることを背理法で証明する問題(東京都立大2017文系第4問)
数列 $\{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}$ が互いに素であることを示しなさい。
式に代入する
(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$
（答え）
互除法で不定方程式を解く
(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}$
（答え）
背理法を用いる
(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}$ は互いに素である。（証明終わり）
SNSでシェア