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

方針・初手

最大公約数 $D_n$ を直接求めるより、ユークリッドの互除法で $a_n$ と $b_n$ の共通約数が取り得る値を絞る。

特に $b_n=3n+24$ を使って $a_n$ から $n b_n$ を引くと、次数が下がる。そこから $D_n$ が $6$ の約数であることが分かるため、あとは $2$ と $3$ の倍数性を調べればよい。

解法1

$n$ は自然数とする。

$$ a_n=3n^2+28n+30,\qquad b_n=3n+24 $$

である。$D_n=\gcd(a_n,b_n)$ とおく。

まず、$a_n$ から $n b_n$ を引くと、

$$ \begin{aligned} a_n-nb_n &= (3n^2+28n+30)-n(3n+24) \\ 4n+30 \end{aligned} $$

である。したがって、$D_n$ は $b_n$ と $4n+30$ の公約数である。

さらに、

$$ \begin{aligned} 3(4n+30)-4(3n+24) &= 12n+90-12n-96 \\ -6 \end{aligned} $$

より、$D_n$ は $6$ の約数である。よって

$$ D_n\in{1,2,3,6} $$

である。

次に、$2$ と $3$ の因数を持つ条件を調べる。

まず $2$ について、$b_n=3n+24$ は $n$ が偶数のとき偶数であり、$n$ が奇数のとき奇数である。また、

$$ a_n=3n^2+28n+30 $$

について、$28n+30$ は常に偶数なので、$a_n$ の偶奇は $3n^2$、すなわち $n$ の偶奇と一致する。したがって、$D_n$ が $2$ を因数にもつのは、$n$ が偶数のときに限る。

次に $3$ について、$b_n=3n+24$ は常に $3$ の倍数である。一方、

$$ a_n=3n^2+28n+30\equiv n \pmod{3} $$

であるから、$a_n$ が $3$ の倍数となるのは $n$ が $3$ の倍数のときである。したがって、$D_n$ が $3$ を因数にもつのは、$n$ が $3$ の倍数のときに限る。

よって、

$$ D_n= \begin{cases} 6 & (n\text{ が }6\text{ の倍数})\\ 2 & (n\text{ が偶数で、}3\text{ の倍数でない})\\ 3 & (n\text{ が }3\text{ の倍数で、偶数でない})\\ 1 & (n\text{ が }2\text{ の倍数でも }3\text{ の倍数でもない}) \end{cases} $$

である。これは

$$ D_n=\gcd(n,6) $$

とまとめられる。

したがって、$D_n$ は周期 $6$ で

$$ \begin{aligned} D_1,D_2,D_3,D_4,D_5,D_6 &= 1,2,3,2,1,6 \end{aligned} $$

を繰り返す。

よって、

$$ D_1=1,\qquad D_2=2,\qquad D_3=3,\qquad D_6=6 $$

である。

また、1周期分の和は

$$ 1+2+3+2+1+6=15 $$

である。

したがって、

$$ S_{12}=2\cdot 15=30 $$

である。

また、$20=6\cdot 3+2$ より、

$$ S_{20}=3\cdot 15+(D_{19}+D_{20}) $$

である。$D_{19}=D_1=1,\ D_{20}=D_2=2$ だから、

$$ S_{20}=45+1+2=48 $$

である。

次に、$S_n$ が $60$ の倍数となる $100$ 以下の自然数 $n$ を求める。

$n=6q+r$ とおく。ただし、$q$ は $0$ 以上の整数、$r=0,1,2,3,4,5$ とする。

周期 $6$ の和が $15$ であるから、

$$ S_n=15q+P_r $$

と表せる。ただし、

$$ P_0=0,\quad P_1=1,\quad P_2=3,\quad P_3=6,\quad P_4=8,\quad P_5=9 $$

である。

$S_n$ が $60$ の倍数であるためには、

$$ 15q+P_r\equiv 0 \pmod{60} $$

でなければならない。

ここで $15q$ は $60$ を法として

$$ 0,\ 15,\ 30,\ 45 $$

のいずれかである。一方、$P_r$ は

$$ 0,\ 1,\ 3,\ 6,\ 8,\ 9 $$

のいずれかである。したがって、$15q+P_r$ が $60$ の倍数になるには $P_r=0$ でなければならない。

よって $r=0$、すなわち $n$ は $6$ の倍数である。このとき

$$ S_n=15q $$

であり、これが $60$ の倍数となる条件は

$$ 15q\equiv 0 \pmod{60} $$

すなわち

$$ q\equiv 0 \pmod{4} $$

である。

したがって、

$$ q=4m $$

と書けるので、

$$ n=6q=24m $$

である。

$100$ 以下の自然数だから、

$$ 24m\le 100 $$

より、

$$ m=1,2,3,4 $$

である。

よって求める $n$ は

$$ 24,\ 48,\ 72,\ 96 $$

である。

解説

この問題の中心は、$D_n$ を直接計算するのではなく、ユークリッドの互除法によって $D_n$ の候補を $6$ の約数に絞ることである。

$$ a_n-nb_n=4n+30 $$

からさらに $b_n$ と組み合わせて定数 $-6$ を作ることで、$D_n$ が $6$ の約数であることが分かる。ここまで来れば、$2$ で割れる条件と $3$ で割れる条件を調べるだけで

$$ D_n=\gcd(n,6) $$

が得られる。

その後は、$D_n$ が

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

を周期的に繰り返すことを利用する。周期和が $15$ であるため、$S_n$ の $60$ による割り切れは、$4$ 周期ごと、すなわち $24$ ごとに起こる。

答え

(1)

$$ D_1=1,\qquad D_2=2,\qquad D_3=3,\qquad D_6=6 $$

(2)

$$ S_{12}=30,\qquad S_{20}=48 $$

(3)

$$ n=24,\ 48,\ 72,\ 96 $$