数学A ユークリッドの互除法 問題 1 解説

方針・初手

(1)は、$a=pb+c$ から

$$ c=a-pb $$

も成り立つことに注目する。したがって、$a$ と $b$ をともに割る整数は、$b$ と $c$ もともに割る。逆も同様である。

(2)は、漸化式

$$ a_{n+2}=6a_{n+1}+a_n $$

を最大公約数に関する関係として見る。特に、$a_{n+2}$ と $a_{n+1}$ の最大公約数は、$a_{n+1}$ と $a_n$ の最大公約数に等しい。

解法1

以下では、公約数は正の公約数として扱う。整数全体で公約数を考える場合は、各集合に負の公約数も加えればよい。

(1)(i)

$a=18,\ b=30$ であるから、$18$ と $30$ の正の公約数は

$$ 1,\ 2,\ 3,\ 6 $$

である。よって

$$ S={1,2,3,6} $$

である。

また、$b=30,\ c=-42$ である。$30$ と $-42$ の正の公約数は、$30$ と $42$ の正の公約数と同じなので、

$$ T={1,2,3,6} $$

である。

したがって

$$ S=T={1,2,3,6} $$

である。

整数の公約数を符号付きで考えるなら、

$$ S=T={-6,-3,-2,-1,1,2,3,6} $$

となる。

(1)(ii)

$a=pb+c$ とする。

$d$ を $a$ と $b$ の公約数とする。このとき

$$ d\mid a,\qquad d\mid b $$

である。

また、

$$ c=a-pb $$

であるから、$d\mid a$ かつ $d\mid b$ より

$$ d\mid c $$

が成り立つ。したがって、$d$ は $b$ と $c$ の公約数である。

逆に、$d$ を $b$ と $c$ の公約数とする。このとき

$$ d\mid b,\qquad d\mid c $$

である。

$a=pb+c$ だから、$d\mid b$ かつ $d\mid c$ より

$$ d\mid a $$

が成り立つ。したがって、$d$ は $a$ と $b$ の公約数である。

以上より、$a$ と $b$ の公約数全体と、$b$ と $c$ の公約数全体は一致する。したがって、それらの中で最大の正の整数も等しいので、

$$ M=N $$

である。

(2)(i)

漸化式より

$$ a_{n+2}=6a_{n+1}+a_n $$

である。

(1)(ii)を

$$ a=a_{n+2},\qquad b=a_{n+1},\qquad c=a_n,\qquad p=6 $$

として用いると、

$$ \gcd(a_{n+2},a_{n+1})=\gcd(a_{n+1},a_n) $$

である。

よって、最大公約数は隣り合う項を1つずつ前にずらしても変わらない。したがって

$$ \gcd(a_{n+1},a_n)=\gcd(a_2,a_1) $$

である。

$a_1=3,\ a_2=4$ だから、

$$ \gcd(a_2,a_1)=\gcd(4,3)=1 $$

である。

ゆえに

$$ \gcd(a_{n+1},a_n)=1 $$

である。

(2)(ii)

漸化式から

$$ a_{n+3}=6a_{n+2}+a_{n+1} $$

である。したがって

$$ \begin{aligned} a_{n+4} &=6a_{n+3}+a_{n+2} \\ &=6(6a_{n+2}+a_{n+1})+a_{n+2} \\ &=37a_{n+2}+6a_{n+1} \end{aligned} $$

となる。

また、

$$ a_{n+2}=6a_{n+1}+a_n $$

より

$$ 6a_{n+1}=a_{n+2}-a_n $$

である。これを代入すると、

$$ \begin{aligned} a_{n+4} &=37a_{n+2}+a_{n+2}-a_n \\ &=38a_{n+2}-a_n \end{aligned} $$

である。

よって

$$ a_{n+4}=38a_{n+2}-a_n $$

と表せる。

(2)(iii)

(2)(ii)より

$$ a_{n+4}=38a_{n+2}-a_n $$

である。

これを

$$ a= a_{n+4},\qquad b=a_{n+2},\qquad c=-a_n,\qquad p=38 $$

と見ると、

$$ a=pb+c $$

の形になっている。

したがって、(1)(ii)より

$$ \gcd(a_{n+4},a_{n+2})=\gcd(a_{n+2},a_n) $$

である。

つまり、

$$ \gcd(a_{n+2},a_n) $$

は $n$ を $2$ 増やしても変わらない。よって、$n$ の偶奇によって値が決まる。

まず、

$$ a_1=3,\qquad a_2=4 $$

であり、

$$ a_3=6a_2+a_1=6\cdot 4+3=27 $$

だから、

$$ \gcd(a_3,a_1)=\gcd(27,3)=3 $$

である。

また、

$$ a_4=6a_3+a_2=6\cdot 27+4=166 $$

だから、

$$ \gcd(a_4,a_2)=\gcd(166,4)=2 $$

である。

したがって、

$$ \gcd(a_{n+2},a_n)= \begin{cases} 3 & (n \text{ が奇数のとき}),\\ 2 & (n \text{ が偶数のとき}) \end{cases} $$

である。

解説

この問題の中心は、$a=pb+c$ の形が最大公約数を変えないという事実である。これはユークリッドの互除法の基本原理と同じである。

(1)では、$a$ と $b$ の公約数が $c=a-pb$ も割ること、逆に $b$ と $c$ の公約数が $a=pb+c$ も割ることを示せばよい。

(2)では、漸化式をそのまま最大公約数の関係に使う。(i)では隣り合う項の最大公約数が一定であることが分かる。(iii)では、(ii)で得た

$$ a_{n+4}=38a_{n+2}-a_n $$

を用いることで、2つ飛ばしの最大公約数が周期 $2$ で繰り返すことが分かる。

答え

(1)(i)

$$ S=T={1,2,3,6} $$

整数の公約数を符号付きで考えるなら、

$$ S=T={-6,-3,-2,-1,1,2,3,6} $$

(1)(ii)

$$ M=N $$

(2)(i)

$$ \gcd(a_{n+1},a_n)=1 $$

(2)(ii)

$$ a_{n+4}=38a_{n+2}-a_n $$

(2)(iii)

$$ \gcd(a_{n+2},a_n)= \begin{cases} 3 & (n \text{ が奇数のとき}),\\ 2 & (n \text{ が偶数のとき}) \end{cases} $$