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

方針・初手

$3$ と $5$ の非負整数倍の和で表せる数を調べる問題である。小さい正の整数を直接確認したうえで、ある数以上はすべて表せることを合同式で示す。

解法1

まず、$1$ から $7$ までを確認する。

$$ \begin{aligned} 1&:\text{表せない}\\ 2&:\text{表せない}\\ 3&=3\cdot 1+5\cdot 0\\ 4&:\text{表せない}\\ 5&=3\cdot 0+5\cdot 1\\ 6&=3\cdot 2+5\cdot 0\\ 7&:\text{表せない} \end{aligned} $$

したがって、$1,2,4,7$ は表せない候補である。

次に、$8$ 以上のすべての整数が表せることを示す。

任意の整数 $x\geqq 8$ について、$x$ を $3$ で割った余りで場合分けする。

(i)

$x\equiv 0\pmod 3$ のとき

$$ x=3\cdot \frac{x}{3}+5\cdot 0 $$

と表せる。ここで $x\geqq 8$ なので $\frac{x}{3}$ は非負整数である。

(ii)

$x\equiv 2\pmod 3$ のとき

このとき $x-5\equiv 0\pmod 3$ であり、$x\geqq 8$ より $x-5\geqq 3$ である。よって

$$ x=3\cdot \frac{x-5}{3}+5\cdot 1 $$

と表せる。

(iii)

$x\equiv 1\pmod 3$ のとき

このとき $x-10\equiv 0\pmod 3$ である。また、$x\geqq 8$ かつ $x\equiv 1\pmod 3$ だから、この場合の最小値は $10$ である。したがって $x-10\geqq 0$ であり、

$$ x=3\cdot \frac{x-10}{3}+5\cdot 2 $$

と表せる。

以上より、$8$ 以上の正の整数はすべて $3m+5n$ の形で表すことができる。

したがって、表すことができない正の整数は、$1$ から $7$ までの確認で得られたものに限られる。

解説

この問題では、小さい整数を直接調べるだけでは不十分である。どこかの段階からすべて表せることを示す必要がある。

$3$ で割った余りに注目すると、$5\equiv 2\pmod 3$ であるため、$5$ を $0$ 個、$1$ 個、$2$ 個使うことで、それぞれ余り $0,2,1$ の数を作れる。あとは残りが $3$ の非負整数倍になっていることを確認すればよい。

答え

$$ \boxed{1,\ 2,\ 4,\ 7} $$