$3n + 16$ と $4n + 18$ の最大公約数が 5 となるような、50以下の自然数 $n$ をすべて求めよ。

1. 問題の内容

$3n + 16$ と $4n + 18$ の最大公約数が 5 となるような、50以下の自然数 $n$ をすべて求めよ。

2. 解き方の手順

ユークリッドの互除法を用いて、$3n+16$ と $4n+18$ の最大公約数を求める。

$4n+18 = 1(3n+16) + (n+2)$

$3n+16 = 3(n+2) + 10$

したがって、$3n+16$ と $4n+18$ の最大公約数は、$n+2$ と 10 の最大公約数と等しい。これが 5 であるためには、$n+2$ が 5 の倍数であり、かつ 10 の倍数ではない必要がある。

$n+2 = 5k$ と表せる。ここで $k$ は整数。

$n = 5k - 2$

$n \le 50$ より、 $5k - 2 \le 50$

$5k \le 52$

$k \le 10.4$

$k$ は整数なので、$k \le 10$ である。

$n+2$ と 10 の最大公約数が 5 であるためには、$n+2$ は 10 の倍数であってはならない。

つまり、$5k$ が 10 の倍数であってはならないので、$k$ は偶数であってはならない。

よって、$k$ は奇数で $1 \le k \le 10$ であるから、$k = 1, 3, 5, 7, 9$ である。

$n = 5k - 2$ にそれぞれ代入すると、

$k=1$ のとき、$n = 5(1)-2 = 3$

$k=3$ のとき、$n = 5(3)-2 = 13$

$k=5$ のとき、$n = 5(5)-2 = 23$

$k=7$ のとき、$n = 5(7)-2 = 33$

$k=9$ のとき、$n = 5(9)-2 = 43$

3. 最終的な答え

$n = 3, 13, 23, 33, 43$