数学A 整数問題 問題 75 解説

方針・初手

$3x+7y$ の形で表せるかどうかは、$3$ で割った余りに注目すると整理しやすい。

また、$2008=3x+7y$ の正の整数解の個数は、合同式で $y$ の形を決めてから、$x>0,\ y>0$ となる範囲を数える。

解法1

まず、$x,y$ は負でない整数とする。

$$ n=3x+7y $$

において、$7\equiv 1 \pmod 3$ であるから、

$$ n\equiv y \pmod 3 $$

である。

さらに、$y\geqq 3$ のとき、

$$ 3x+7y=3(x+7)+7(y-3) $$

と変形できるので、$y$ は $3$ 以上なら $3$ だけ減らしても、代わりに $x$ を $7$ 増やせば同じ $n$ を表せる。

したがって、$y$ は余りを代表する $0,1,2$ の場合だけを考えればよい。

(i)

$y=0$ のとき

$$ n=3x $$

であるから、$3,6,9,\dots$ は表せる。

(ii)

$y=1$ のとき

$$ n=3x+7 $$

であるから、$7,10,13,\dots$ は表せる。

(iii)

$y=2$ のとき

$$ n=3x+14 $$

であるから、$14,17,20,\dots$ は表せる。

よって、各余りについて最小の表せる数は次のようになる。

$$ \begin{array}{c|c} n \pmod 3 & \text{表せる最小の自然数} \\ \hline 0 & 3 \\ 1 & 7 \\ 2 & 14 \end{array} $$

したがって、表せない自然数は、それぞれの余りでこの最小値より小さいものを拾えばよい。

$3$ で割った余りが $1$ の自然数で $7$ より小さいものは

$$ 1,\ 4 $$

である。

$3$ で割った余りが $2$ の自然数で $14$ より小さいものは

$$ 2,\ 5,\ 8,\ 11 $$

である。

また、$3$ で割り切れる正の整数は $3,6,9,\dots$ とすべて表せるので、表せないものはない。

以上より、どのような負でない整数 $x,y$ を用いても $n=3x+7y$ の形で表せない自然数は

$$ 1,\ 2,\ 4,\ 5,\ 8,\ 11 $$

である。

次に、

$$ 2008=3x+7y $$

を満たす正の整数 $x,y$ の組を数える。

両辺を $3$ で割った余りで考えると、

$$ 2008\equiv 1 \pmod 3,\qquad 7y\equiv y \pmod 3 $$

より、

$$ y\equiv 1 \pmod 3 $$

である。

したがって、$y$ は正の整数なので、

$$ y=1+3k \qquad (k=0,1,2,\dots) $$

とおける。

これを $2008=3x+7y$ に代入すると、

$$ \begin{aligned} 2008&=3x+7(1+3k)\\ 2008&=3x+7+21k\\ 3x&=2001-21k\\ x&=667-7k \end{aligned} $$

となる。

$x$ も正の整数でなければならないから、

$$ 667-7k\geqq 1 $$

である。

これを解くと、

$$ 7k\leqq 666 $$

より、

$$ k\leqq 95 $$

である。

したがって、

$$ k=0,1,2,\dots,95 $$

の $96$ 個が対応する。

よって、$2008=3x+7y$ を満たす正の整数 $x,y$ の組は $96$ 個である。

解説

この問題の前半は、いわゆる「$3$ 円玉と $7$ 円玉で作れない金額」を調べる問題である。$3$ と $7$ は互いに素なので、ある程度大きい数はすべて表せる。実際には、$3$ で割った余りごとに、最小の表せる数を調べるのが簡潔である。

後半では、$x,y$ が正の整数である点に注意する。前半は負でない整数でよいが、後半は $x>0,\ y>0$ であるため、$k$ の範囲を決めるときに $x\geqq 1$ を使う必要がある。

答え

表せない自然数は

$$ 1,\ 2,\ 4,\ 5,\ 8,\ 11 $$

である。

また、$2008=3x+7y$ を満たす正の整数 $x,y$ の組は

$$ 96 $$

個である。